深入PHP中的HashTable结构详解

HashTable是Zend引擎中最重要、使用最广泛的数据结构，它被用来存储几乎所有的东西。
1.2.1 数据结构
HashTable数据结构定义如下：
代码如下:
typedef struct bucket {
 ulong h;    // 存放hash
 uint nKeyLength;
 void *pData;   // 指向value，是用户数据的副本
 void *pDataPtr;
 struct bucket *pListNext; // pListNext和pListLast组成
 struct bucket *pListLast; // 整个HashTable的双链表
 struct bucket *pNext;  // pNext和pLast用于组成某个hash对应
 struct bucket *pLast;  // 的双链表
 char arKey[1];    // key
} Bucket;

typedef struct _hashtable {
 uint nTableSize;
 uint nTableMask;
 uint nNumOfElements;
 ulong nNextFreeElement;
 Bucket *pInternalPointer; /* Used for element traversal */
 Bucket *pListHead;
 Bucket *pListTail;
 Bucket **arBuckets;   // hash数组
 dtor_func_t pDestructor; // HashTable初始化时指定，销毁Bucket时调用
 zend_bool persistent;  // 是否采用C的内存分配例程
 unsigned char nApplyCount;
 zend_bool bApplyProtection;
#if ZEND_DEBUG
 int inconsistent;
#endif
} HashTable;

HashTable中包含两种数据结构，一个链表散列和一个双向链表，前者用于进行快速键-值查询，后者方便线性遍历和排序，一个Bucket同时存在于这两个数据结构中。
关于该数据结构的几点解释：
链表散列中为什么使用双向链表？
一般的链表散列只需要按key进行操作，只需要单链表就够了。但是，Zend有时需要从链表散列中删除给定的Bucket，使用双链表可以非常高效的实现。
nTableMask是干什么的？
这个值用于hash值到arBuckets数组下标的转换。当初始化一个HashTable，Zend首先为arBuckets数组分配nTableSize大小的内存，nTableSize取不小于用户指定大小的最小的2^n，即二进制的10*。nTableMask = nTableSize – 1，即二进制的01*，此时h & nTableMask就恰好落在 [0, nTableSize – 1] 里，Zend就以其为index来访问arBuckets数组。
pDataPtr是干什么的？
通常情况下，当用户插入一个键值对时，Zend会将value复制一份，并将pData指向value副本。复制操作需要调用Zend内部例程 emalloc来分配内存，这是个非常耗时的操作，并且会消耗比value大的一块内存（多出的内存用于存放cookie），如果value很小的话，将会造成较大的浪费。考虑到HashTable多用于存放指针值，于是Zend引入pDataPtr，当value小到和指针一样长时，Zend就直接将其复制到pDataPtr里，并且将pData指向pDataPtr。这就避免了emalloc操作，同时也有利于提高Cache命中率。