PHP 源代码分析 Zend HashTable详解第1/3页

hashtable在通常的数据结构教材中也称作散列表，哈希表。其基本原理比较简单(如果你对其不熟悉，请查阅随便一本数据结构教材或在网上搜索)，但php的实现有其独特的地方。理解了hashtable的数据存储结构，对我们分析php的源代码，特别是zend engine中的虚拟机的实现时，有很重要的帮助。它可以帮助我们在大脑中模拟一个完整的虚拟机的形象。它也是php中其它一些数据结构如数组实现的基础。
zend hashtable的实现结合了双向链表和向量（数组）两种数据结构的优点，为php提供了非常高效的数据存储和查询机制。
let's begin!
一、 hashtable的数据结构
在zend engine中的hashtable的实现代码主要包括zend_hash.h, zend_hash.c这两个文件中。zend hashtable包括两个主要的数据结构，其一是bucket（桶）结构，另一个是hashtable结构。bucket结构是用于保存数据的容器，而hashtable结构则提供了对所有这些bucket(或桶列)进行管理的机制。

typedef struct bucket {
ulong h; /* used for numeric indexing */
uint nkeylength; /* key 长度 */
void *pdata; /* 指向bucket中保存的数据的指针 */
void *pdataptr; /* 指针数据 */
struct bucket *plistnext; /* 指向hashtable桶列中下一个元素 */
struct bucket *plistlast; /* 指向hashtable桶列中前一个元素 */
struct bucket *pnext; /* 指向具有同一个hash值的桶列的后一个元素 */
struct bucket *plast; /* 指向具有同一个hash值的桶列的前一个元素 */
char arkey[1]; /* 必须是最后一个成员，key名称*/
} bucket;

在zend hashtable中，每个数据元素(bucket)有一个键名(key)，它在整个hashtable中是唯一的，不能重复。根据键名可以唯一确定hashtable中的数据元素。键名有两种表示方式。第一种方式使用字符串arkey作为键名，该字符串的长度为nkeylength。注意到在上面的数据结构中arkey虽然只是一个长度为1的字符数组，但它并不意味着key只能是一个字符。实际上bucket是一个可变长的结构体，由于arkey是bucket的最后一个成员变量，通过arkey与nkeylength结合可确定一个长度为nkeylength的key。这是c语言编程中的一个比较常用的技巧。另一种键名的表示方式是索引方式，这时nkeylength总是0，长整型字段h就表示该数据元素的键名。简单的来说，即如果nkeylength=0，则键名为h；否则键名为arkey, 键名的长度为nkeylength。
当nkeylength > 0时，并不表示这时的h值就没有意义。事实上，此时它保存的是arkey对应的hash值。不管hash函数怎么设计，冲突都是不可避免的，也就是说不同的arkey可能有相同的hash值。具有相同hash值的bucket保存在hashtable的arbuckets数组(参考下面的解释)的同一个索引对应的桶列中。这个桶列是一个双向链表，其前向元素，后向元素分别用plast, pnext来表示。新插入的bucket放在该桶列的最前面。
在bucket中，实际的数据是保存在pdata指针指向的内存块中，通常这个内存块是系统另外分配的。但有一种情况例外，就是当bucket保存的数据是一个指针时，hashtable将不会另外请求系统分配空间来保存这个指针，而是直接将该指针保存到pdataptr中，然后再将pdata指向本结构成员的地址。这样可以提高效率，减少内存碎片。由此我们可以看到php hashtable设计的精妙之处。如果bucket中的数据不是一个指针，pdataptr为null。
hashtable中所有的bucket通过plistnext, plistlast构成了一个双向链表。最新插入的bucket放在这个双向链表的最后。
注意在一般情况下，bucket并不能提供它所存储的数据大小的信息。所以在php的实现中，bucket中保存的数据必须具有管理自身大小的能力。

typedef struct _hashtable {
uint ntablesize;
uint ntablemask;
uint nnumofelements;
ulong nnextfreeelement;
bucket *pinternalpointer;
bucket *plisthead;
bucket *plisttail;
bucket **arbuckets;
dtor_func_t pdestructor;
zend_bool persistent;
unsigned char napplycount;
zend_bool bapplyprotection;
#if zend_debug
int inconsistent;
#endif
} hashtable;

1