熟悉PHP的同学都知道PHP的数组使用Hash表来实现的，究竟Hash表的结构具体是什么样子的呢？不一定每个人都很清楚，这里详细介绍一下：
HashTable结构说明：
- uint nTableSize
- 指定了HashTable的大小，同时它限定了HashTable中能保存Bucket的最大数量此数越大，系统为HashTable分配的内存就越多。为了提高计算效率，系统自动会将nTableSize调整到最小一个不小于nTableSize的2 的整数次方
- 该值限制的是桶链表的个数，而不是桶的最大个数
- uint nTableMask
- nTableMask的值永远是nTableSize – 1，引入这个字段的主要目的是为了提高计算效率
- 写入hash表的数据都需要先通过hash函数将key哈希为一个无符号整数，通过该无符号整数与nTableMask做“按位与”操作，得出应该放到哪个链表中；
- uint nNumOfElements
- 记录HashTable当前保存的数据元素的个数
- ulong nNextFreeElement
- 记录HashTable中下一个可用于插入数据元素的arBuckets的索引
- ？？？
- Bucket *pInternalPointer
- 用于遍历hash表
- Bucket *pListHead
- Hash表中所有元素的一个双向链表的表头
- 不同于桶链表，桶链表靠的是Bucket中的，pNext 和 pLast；该整个链表中的是pListNext和pListLast；
- Bucket *pListTail
- Bucket双向链表的最后一元素
- Bucket **arBuckets
- 一个Bucket指针数组，其大小就是nTableSize决定的，初始化hash表时，数组元素都为空
- dtor_func_t pDestructor
- 函数指针，在HashTable的增加、修改、删除Bucket时自动调用，用于处理相关数据的清理工作
- zend_bool persistent
- 指出了Bucket内存分配的方式。如果persisient为TRUE，则使用操作系统本身的内存分配函数为Bucket分配内存，否则使用PHP的内存分配函数。
- unsigned char nApplyCount
- nApplyCount与bApplyProtection结合提供了一个防止在遍历HashTable时进入递归循环时的一种机制
- zend_bool bApplyProtection
- ？？？
|
1 |
<font size="3"><span style="color: rgb(0, 0, 0);">Bucket</span><span style="color: rgb(51, 153, 51);"><span style="color: rgb(0, 0, 0);">结构说明：</span><br style="color: rgb(0, 0, 0);" /></span></font> |
|
1 |
<span style="color: rgb(153, 51, 51);">typedef</span> <span style="color: rgb(153, 51, 51);">struct</span> bucket <span style="color: rgb(0, 153, 0);">{</span><br /> ulong h<span style="color: rgb(51, 153, 51);">;</span> <span style="color: rgb(128, 128, 128);">/* Used for numeric indexing */</span><br /> uint nKeyLength<span style="color: rgb(51, 153, 51);">;</span> <span style="color: rgb(128, 128, 128);">/* key 长度 */</span><br /> <span style="color: rgb(153, 51, 51);">void</span> <span style="color: rgb(51, 153, 51);">*</span>pData<span style="color: rgb(51, 153, 51);">;</span> <span style="color: rgb(128, 128, 128);">/* 指向Bucket中保存的数据的指针 */</span><br /> <span style="color: rgb(153, 51, 51);">void</span> <span style="color: rgb(51, 153, 51);">*</span>pDataPtr<span style="color: rgb(51, 153, 51);">;</span> <span style="color: rgb(128, 128, 128);">/* 指针数据 */</span><br /> <span style="color: rgb(153, 51, 51);">struct</span> bucket <span style="color: rgb(51, 153, 51);">*</span>pListNext<span style="color: rgb(51, 153, 51);">;</span> <span style="color: rgb(128, 128, 128);">/* 指向HashTable桶列中下一个元素 */</span><br /> <span style="color: rgb(153, 51, 51);">struct</span> bucket <span style="color: rgb(51, 153, 51);">*</span>pListLast<span style="color: rgb(51, 153, 51);">;</span> <span style="color: rgb(128, 128, 128);">/* 指向HashTable桶列中前一个元素 */</span><br /> <span style="color: rgb(153, 51, 51);">struct</span> bucket <span style="color: rgb(51, 153, 51);">*</span>pNext<span style="color: rgb(51, 153, 51);">;</span> <span style="color: rgb(128, 128, 128);">/* 指向具有同一个hash值的桶列的后一个元素 */</span><br /> <span style="color: rgb(153, 51, 51);">struct</span> bucket <span style="color: rgb(51, 153, 51);">*</span>pLast<span style="color: rgb(51, 153, 51);">;</span> <span style="color: rgb(128, 128, 128);">/* 指向具有同一个hash值的桶列的前一个元素 */</span><br /> <span style="color: rgb(153, 51, 51);">char</span> arKey<span style="color: rgb(0, 153, 0);">[</span><span style="color: rgb(0, 0, 221);">1</span><span style="color: rgb(0, 153, 0);">]</span><span style="color: rgb(51, 153, 51);">;</span> <span style="color: rgb(128, 128, 128);">/* 必须是最后一个成员，key名称*/</span><br /><span style="color: rgb(0, 153, 0);">}</span> Bucket<span style="color: rgb(51, 153, 51);">;</span><br /><br />其中：<br />h 就是通过hash函数计算出来的一个无符号长整型，查找元素时，先通过“按位与”操作确定链表，再遍历链表，比较h的值是否相同，再比较key的长度是否形同就行了，并不去比较key是否相同。<br />arKey 就是key的指针，虽然比较的时候不适用key，但是key还是要保存的<br />pData和pDataPtr的关系还没太明白。<br /><br /><br />=======================<br /><br />1。 在桶链表中，后插入的Bucket总是在链表的头部的。<br /><br /><br />=======================<br />参考资料： http://www.phppan.com/2009/12/php-hashtable-demo/ |