[PHP内核探索]PHP中的哈希表

HashTable的介绍哈希表是实现字典操作的一种有效数据结构。定义简单地说HashTable(哈希表)就是一种键值对的数据结构。支持插入查找删除等操作。在一些合理的假设下在哈希表中的所有操作的时间复杂度是O(1)(对相关证明感兴趣的可以自行查阅)。实现哈希表的关键在哈希表中不是使用关键字做下标而是通过哈希函数计算出key的哈希值作为下标然后查找/删除时再计算出key的哈希值从而快速定位元素保存的位置。在一个哈希表中不同的关键字可能会计算得到相同的哈希值这叫做“哈希冲突”就是处理两个或多个键的哈希值相同的情况。解决哈希冲突的方法有很多开放寻址法拉链法等等。因此实现一个好的哈希表的关键就是一个好的哈希函数和处理哈希冲突的方法。Hash函数判断一个哈希算法的好坏有以下四个定义一致性等价的键必然产生相等的哈希值高效性计算简便均匀性均匀地对所有的键进行哈希。哈希函数建立了关键值与哈希值的对应关系即h hash_func(key)。对应关系见下图设计一个完美的哈希函数就交由专家去做吧我们只管用已有的较成熟的哈希函数就好了。PHP内核使用的哈希函数是time33函数又叫DJBX33A其实现如下static inline ulong zend_inline_hash_func(const char *arKey, uint nKeyLength){register ulong hash 5381;/* variant with the hash unrolled eight times */for (; nKeyLength 8; nKeyLength - 8) {hash ((hash 5) hash) *arKey;hash ((hash 5) hash) *arKey;hash ((hash 5) hash) *arKey;hash ((hash 5) hash) *arKey;hash ((hash 5) hash) *arKey;hash ((hash 5) hash) *arKey;hash ((hash 5) hash) *arKey;hash ((hash 5) hash) *arKey;}switch (nKeyLength) {case 7: hash ((hash 5) hash) arKey; /fallthrough... */case 6: hash ((hash 5) hash) arKey; /fallthrough... */case 5: hash ((hash 5) hash) arKey; /fallthrough... */case 4: hash ((hash 5) hash) arKey; /fallthrough... */case 3: hash ((hash 5) hash) arKey; /fallthrough... */case 2: hash ((hash 5) hash) arKey; /fallthrough... */case 1: hash ((hash 5) hash) *arKey; break;case 0: break;EMPTY_SWITCH_DEFAULT_CASE()}return hash;}注函数使用了一个8次循环switch来实现是对for循环的优化减少循环的运行次数然后在switch里面执行剩下的没有遍历到的元素。拉链法将所有具有相同哈希值的元素都保存在一条链表中的方法叫拉链法。查找的时候通过先计算key对应的哈希值然后根据哈希值找到对应的链表最后沿着链表顺序查找相应的值。具体保存后的结构图如下PHP的HashTable结构简单地介绍了哈希表的数据结构之后继续看看PHP中是如何实现哈希表的。PHP内核hashtable的定义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_DEBUGint inconsistent;#endif} HashTable;nTableSizeHashTable的大小以2的倍数增长nTableMask用在与哈希值做与运算获得该哈希值的索引取值arBuckets初始化后永远是nTableSize-1nNumOfElementsHashTable当前拥有的元素个数count函数直接返回这个值nNextFreeElement表示数字键值数组中下一个数字索引的位置pInternalPointer内部指针指向当前成员用于遍历元素pListHead指向HashTable的第一个元素也是数组的第一个元素pListTail指向HashTable的最后一个元素也是数组的最后一个元素。与上面的指针结合在遍历数组时非常方便比如reset和endAPIarBuckets包含bucket组成的双向链表的数组索引用key的哈希值和nTableMask做与运算生成pDestructor删除哈希表中的元素使用的析构函数persistent标识内存分配函数如果是TRUE则使用操作系统本身的内存分配函数否则使用PHP的内存分配函数nApplyCount保存当前bucket被递归访问的次数防止多次递归bApplyProtection标识哈希表是否要使用递归保护默认是1要使用举一个哈希与mask结合的例子例如”foo”真正的哈希值使用DJBX33A哈希函数是193491849。如果我们现在有64容量的哈希表我们明显不能使用它作为数组的下标。取而代之的是通过应用哈希表的mask然后只取哈希表的低位。hash | 193491849 | 0b1011100010000111001110001001 mask | 63 | 0b0000000000000000000000111111---------------------------------------------------------------------- index | 9 | 0b0000000000000000000000001001因此在哈希表中foo是保存在arBuckets中下标为9的bucket向量中。bucket结构体的定义typedef struct bucket {ulong h;uint nKeyLength;void *pData;void *pDataPtr;struct bucket *pListNext;struct bucket *pListLast;struct bucket *pNext;struct bucket *pLast;const char *arKey;} Bucket;h哈希值或数字键值的keynKeyLengthkey的长度pData指向数据的指针pDataPtr指针数据pListNext指向HashTable中的arBuckets链表中的下一个元素pListLast指向HashTable中的arBuckets链表中的上一个元素pNext指向具有相同hash值的bucket链表中的下一个元素pLast指向具有相同hash值的bucket链表中的上一个元素arKeykey的名称PHP中的HashTable是采用了向量加双向链表的实现方式向量在arBuckets变量保存向量包含多个bucket的指针每个指针指向由多个bucket组成的双向链表新元素的加入使用前插法即新元素总是在bucket的第一个位置。由上面可以看到PHP的哈希表实现相当复杂。这是它使用超灵活的数组类型要付出的代价。一个PHP中的HashTable的示例图如下所示(图片源自网络侵权即删)HashTable相关APIzend_hash_initzend_hash_add_or_updatezend_hash_findzend_hash_del_key_or_indexzend_hash_init函数执行步骤设置哈希表大小设置结构体其他成员变量的初始值 (包括释放内存用的析构函数pDescructor)详细代码注解点击zend_hash_init源码注1、pHashFunction在此处并没有用到php的哈希函数使用的是内部的zend_inline_hash_func2、zend_hash_init执行之后并没有真正地为arBuckets分配内存和计算出nTableMask的大小真正分配内存和计算nTableMask是在插入元素时进行CHECK_INIT检查初始化时进行。zend_hash_add_or_update函数执行步骤检查键的长度检查初始化计算哈希值和下标遍历哈希值所在的bucket如果找到相同的key且值需要更新则更新数据否则继续指向bucket的下一个元素直到指向bucket的最后一个位置为新加入的元素分配bucket设置新的bucket的属性值然后添加到哈希表中如果哈希表空间满了则重新调整哈希表的大小函数执行流程图CONNECT_TO_BUCKET_DLLIST是将新元素添加到具有相同hash值的bucket链表。CONNECT_TO_GLOBAL_DLLIST是将新元素添加到HashTable的双向链表。详细代码和注解请点击zend_hash_add_or_update代码注解。zend_hash_find函数执行步骤计算哈希值和下标遍历哈希值所在的bucket如果找到key所在的bucket则返回值否则指向下一个bucket直到指向bucket链表中的最后一个位置详细代码和注解请点击zend_hash_find代码注解。zend_hash_del_key_or_index