php Hash Table(一) Hash Table的结构

Hash Table的结构图：

在上图中发现：Bucket1和Bucket2是hash冲突的双向链表，但是后添加的Bucket2是添加到头部的，可以看到Bucket2的pListLast和pNext指向Bucket1。

对HashTable结构体的字段解释：

1.nTableSize。顾名思义这个是整个哈希表分配的大小（在内部实现的C中分配的数组大小，PHP是动态的但到底层数组是有大小的是静态的），他的大小有一个固定的申请算法，一般是最接近并且大于当前这个数值的2的乘方，描述的可能有点模糊，举个例子来看，如果PHP数组存储32个整形数据，那么底层申请的nTableSize应该等于32个元素，如果33呢，那么取最近且大于这个数的一个数64，那么分配的大小是64个元素。这样分配的原因是为了能分配足够的内存同样又不会浪费太多的内存。基于哈希的效率考虑，太小那么势必造成哈希之后太多的碰撞查找，如果分配太大那么必然浪费太多内存，这样分配经过实践证明相对在空间和时间上可以获得一个平衡。

2.nTableMask。哈希表的掩码数值等于nTableSize-1，他的作用是什么？用来纠正通过DBJ算法计算的哈希值在当前nTableSize大小的哈希表中的正确的索引值。比如"foo"通过固定算法之后得出的哈希值是193491849，如果表的大小为64，很明显已经超过了最大索引值，这时候就需要运用哈希表的掩码对其进行矫正实际采用的方法就是与掩码进行位与运算，这样做是为了把哈希值大的一样映射到nTalbeSize空间内。

   hash  |   193491849 |   0b1011100010000111001110001001
 & mask  | &        63 | & 0b0000000000000000000000111111
---------------------------------------------------------
 = index | =         9 | = 0b0000000000000000000000001001

3.nNumOfElements。是PHP数组中实际存储元素的个数，我们使用count,sizeof计算的就是获取的这个值。

4.nNextFreeElement。下一个空闲的元素空间，当我们申请一个空下标元素的时候就需要用到此项，比如$ret[] = ‘apple‘。

5.pInternalPointer。存储了内部当前执行的元素的指针，当我们使用一些内部循环函数的时候会用到这个指针比如reset(), current(), prev(), next(), foreach(), end()。

6.pListHead和pListTail则具体指向了该哈希表的第一个和最后一个元素，对应就是数组的起始和结束元素。

7.arBuckets。这个就是实际存储的C的内部数组。这里记录的是一个指向指针的指针Bucket **。即指向一个指针数组，其中每个元素是一个指向Bucket链表的头指针。

8.pDestructor 是一个析构函数，当某个值被从哈希表删除的时候会触发此函数。他还有一个主要作用是用于变量的GC回收。在PHP里面GC是通过引用计数实现的，当一个变量的引用计数变为0，就会被PHP的GC回收。

9.persistent 定义了hashtable是否能在多次request中获得持久存在。

10.nApplyCount 和 bApplyProtection 是用来防止无限递归的。

11.inconsistent 是在调试模式下捕获对HT不正确的使用。

在zend/Zend_hash.h中对hashtable的定义：

typedef struct _hashtable { 
    uint nTableSize;        // hash Bucket的大小，最小为8，以2x增长。uint nTableMask;        // nTableSize-1 ， 掩码，用于根据hash值计算存储位置。uint nNumOfElements;    // hash Bucket中当前存在的元素个数，count()函数会直接返回此值 ulong nNextFreeElement; // 下一个数字索引的位置，$arr[] = "hello"时会用到
    Bucket *pInternalPointer;   // 当前遍历的指针（foreach比for快的原因之一）
    Bucket *pListHead;          // 存储数组头元素指针
    Bucket *pListTail;          // 存储数组尾元素指针
    Bucket **arBuckets;         // 存储hash数组    dtor_func_t pDestructor;
    zend_bool persistent;
    unsigned char nApplyCount; // 标记当前hash Bucket被递归访问的次数（防止多次递归）
    zend_bool bApplyProtection;// 标记当前hash桶允许不允许多次访问，不允许时，最多只能递归3次#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

 对Bucket结构体字段的解释：

1.h是一个哈希值，未经过掩码矫正的哈希DBJ算出来的原始值。

2.arKey，用来记录作为哈希计算的字符串，nKeyLength是哈希字符串的长度，对于整形键值是用不到这两项的。

3.pData以及pDataPtr是实际存储数据的指针，在PHP里面他们通常是指向一个zval结构（该结构广泛被PHP用来内部存储各种变量以及对象）。

4.pListNext, pListLast 指定了整个数组的顺序，PHP中的遍历就是通过哈希结构体中的pListHead bucket依次遍历pNext直到数组结束。

5.pNext和pLast 这两个指针是用来解决哈希冲突的，这个在下面哈希冲突中详细介绍，在PHP的哈希表冲突的处理采用的是拉链法也就是在每个可能冲突的键值位置拉出一个链表来存储对应的键值数据。

在zend/Zend_hash.h中对bucket的定义：

typedef struct bucket {
    /* Used for numeric indexing */ulong h;            // 对char *key进行hash后的值，或者是用户指定的数字索引值uint nKeyLength;    // hash关键字的长度，如果数组索引为数字，此值为0void *pData;        // 指向value，一般是用户数据的副本，如果是指针数据，则指向pDataPtrvoid *pDataPtr;     //如果是指针数据，此值会指向真正的value，同时上面pData会指向此值struct bucket *pListNext;   // 整个hash表的下一元素struct bucket *pListLast;   // 整个哈希表该元素的上一个元素struct bucket *pNext;       // 存放在同一个hash Bucket内的下一个元素struct bucket *pLast;       // 同一个哈希bucket的上一个元素char arKey[1];  
    /*存储字符索引，此项必须放在最未尾，因为此处只字义了1个字节，存储的实际上是指向char *key的值，
    这就意味着可以省去再赋值一次的消耗，而且，有时此值并不需要，所以同时还节省了空间。
    */
} Bucket;

原文：http://www.cnblogs.com/leezhxing/p/4823631.html