在PHP内核中，最重要的数据结构之一就是HashTable。我们常用的数组是在内核中用HashTable实现的。那么，PHP的HashTable是如何实现的呢？最近在看HashTable的数据结构，但是算法书上并没有具体的实现算法。最近刚看了PHP的源码，所以参考了PHP中HashTable的实现，自己实现了一个简单版的HashTable，总结了一些经验。下面就和大家分享一下。HashTable简介哈希表是一种实现字典操作的有效数据结构。定义简单地说，HashTable（哈希表）是一种键值对的数据结构。支持插入、查找、删除等操作。在一些合理的假设下，哈希表所有操作的时间复杂度为O(1)（对相关证明感兴趣的可以自行查看）。实现哈希表的关键是在哈希表中，而不是使用关键字作为下标，而是通过哈希函数计算出键的哈希值作为下标，然后在查找/删除时计算键的哈希值,从而快速定位到元素保存的位置。在哈希表中，不同的关键字可能会计算出相同的哈希值，这种情况称为“哈希碰撞”，即处理两个或多个键的哈希值相同的情况。解决哈希冲突的方法有很多，比如开放寻址、压缩等。因此，实现一个好的哈希表的关键是一个好的哈希函数和处理哈希冲突的方法。哈希函数有以下四种定义来判断一个哈希算法的优劣：·一致性，等价的键必须产生相等的哈希值；·效率，易于计算；哈希。哈希函数建立键值与哈希值之间的对应关系，即：h=hash_func(key)。设计一个完美的散列函数留给专家，我们只是使用已经可用的更成熟的散列函数。PHP内核使用的哈希函数是time33函数，又名DJBX33A，其实现如下：staticinlineulongzend_inline_hash_func(constchar*arKey,uintnKeyLength){`registerulong`hash`=5381;``/*`hash`展开八次`*/`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...*/case6:hash=((hash<<5)+hash)+*arKey++;/*fallthrough...*/case`5:`hash`=((`hash`<<`5)+hash)+*arKey++;/*fallthrough...*/case4:hash=((hash<<5)+hash)+*arKey++;/*失败。..*/case`3:`hash`=((`hash`<<`5)+hash)+*arKey++;/*fallthrough...*/case2:hash=((hash<<`5)+hash)+*arKey++;/*fallthrough...*/case`1:`hash`=((`hash`<<`5)+hash)+*arKey++;break;case0:break;EMPTY_SWITCH_DEFAULT_CASE()}returnhash;}注：该功能使用8次循环+switch实现，是for循环的优化，减少循环运行次数，并且然后执行switch中剩下的没有遍历的元素。将散列值的元素存储在链表中的方法称为拉链法。查找时，先计算key对应的hash值，然后根据hash值找到对应的链表，最后顺着链表顺序查找对应的value。具体保存的结构图如下：PHP的HashTable结构简单介绍了哈希表的数据结构后，继续看哈希表在PHP中是如何实现的。PHP内核哈希表的定义：typedefstruct_hashtable{uintnTableSize;uintnTableMask；uintnNumOfElements；ulongnNextFreeElement；桶*pInternalPointer;桶*pListHead;桶*pListTail;桶**arBuckets；bApplyProtection;#ifZEND_DEBUGintinconsistent;#endif}HashTable;nTableSize，HashTable的大小，以2的倍数递增。nTableMask，用于与哈希值AND运算得到哈希值的索引值，arBuckets初始化后总是nTableSize-1·nNumOfElements，当前元素个数HashTable所拥有，count函数直接返回这个值·nNextFreeElement，表示数字键值数组中下一个数字索引的位置·pInternalPointer，内部指针，指向当前成员，用于遍历Elements·pListHead，指向指向哈希表的第一个元素，也是数组的第一个元素·pListTail，指向哈希表的最后一个元素，也是数组的最后一个元素。结合上面的指针，在遍历数组的时候非常方便，比如reset，endAPI。arBuckets，包含buckets的双向链表数组，索引由key和nTableMask的哈希值AND运算生成。pDestructor，删除哈希表元素使用的析构函数·persistent，标识内存分配函数。如果为TRUE，则使用操作系统本身的内存分配函数，否则使用PHP的内存分配函数·nApplyCount，保存当前bucket被递归访问的次数，防止多次递归·bApplyProtection，这标识哈希表是否要使用递归保护，默认为1，要使用举个哈希和掩码组合的例子：比如“foo”的真实哈希值（使用DJBX33A哈希函数）是193491849。如果我们现在有一个容量为64的哈希表，我们显然不能把它作为数组下标。相反，通过应用哈希表的掩码，然后只取哈希表的低位。散列|193491849|0b101110001100111111001001&面具|&63|&0B0000000000000000000000000011111=索引|=9|=0B0000000000000000001001001是哈希表中的低至-9出价。bucket结构定义typedefstructbucket{ulongh;uintnKeyLength；void`*pData;`void`*pDataPtr;`structbucket*pListNext;结构桶*pListLast;结构桶*pNext;结构桶*pLast;constchar`*arKey;`}桶；h，哈希值（或数字键值）nKeyLength，键长pData，指向数据的指针pDataPtr，指针数据pListNext，指向HashTable中arBuckets链表的下一项元素pListLast，指向arBuckets链表中的前一个元素HashTable中的pNext，指向桶链表中具有相同哈希值的下一个元素pLast，指向桶链表中具有相同哈希值的前一个元素arKey，key的名称PHP中的HashTable是通过以下方式实现的添加一个vector和一个双向链表，vector保存在arBuckets变量中，vector包含指向多个buckets的指针，每个指针指向一个由多个buckets组成的双向链表，添加新元素使用前向插值法，也就是新元素总是在桶的第一个位置。从上面可以看出，PHP的哈希表实现是相当复杂的。这就是它要为我们付出的代价ing一个超灵活的数组类型。HashTable相关API·zend_hash_init·zend_hash_add_or_update·zend_hash_find·zend_hash_del_key_or_indexZend_hash_init函数执行步骤·设置哈希表的大小·设置结构体其他成员变量的初始值（包括释放内存的析构函数pDescructor）注：1.pHashFunction是这里没有使用，PHP的hash函数使用的是内部的zend_inline_hash_func2，zend_hash_init在zend_hash_init执行后并没有真正为arBuckets分配内存和计算源码事务nTableMask的大小，真正分配内存和计算nTableMask是在元素的时候进行的被插入并检查并初始化CHECK_INIT。zend_hash_add_or_update函数执行步骤检查key的长度检查初始化计算hash值和下标遍历hash值所在的bucket，如果找到相同的key需要更新value，则更新数据，否则继续指向下一个桶元素，直到它指向桶的最后一个位置。为新添加的元素分配一个桶，设置新桶的属性值，然后添加到哈希表中。如果哈希表空间已满，则重新调整哈希表的大小函数执行流程图CONNECT_TO_BUCKET_DLLIST是向桶列表中添加具有相同哈希值的新元素。CONNECT_TO_GLOBAL_DLLIST是一个向哈希表添加新元素的双向链表。详细代码和注释请点击：zend_hash_add_or_update代码注释。zend_hash_find函数执行步骤计算hash值和下标遍历hash值所在的bucket，如果是key所在的bucket，返回值，否则，指向下一个bucket，直到指向bucketlist中的最后一个位置详细代码评论评论请点击：zend_hash_find代码评论。zend_hash_del_key_or_index函数执行步骤计算key的hash值和下标遍历hash值所在的bucket，如果找到key所在的bucket，则进入第三步，否则，指向下一个bucket，直到指向bucketlist中最后一个位置如果要删除第一个元素，直接将arBucket[nIndex]指向第二个元素；剩下的操作就是执行当前指针的最后一个当前下一个调整相关指针释放数据内存和桶结构内存性能分析PHP的哈希表的优点：PHP的HashTable为数组操作提供了极大的方便。无论是创建数组，添加元素还是删除元素等等，哈希表都提供了很好的性能，但是当数据量大的时候它的缺点就更加明显，从时间复杂度上就可以看出它的缺点和空间复杂度。缺点如下：存储数据的结构体zval需要单独分配内存，需要对这块额外的内存进行管理。每个zval占用16字节内存；为了进行顺序遍历，使用双向链表连接整个HashTable，并加入了很多指针，每个指针需要16字节的内存；遍历时，如果元素在bucketlist的末尾，也需要遍历整个bucketlist。找到您正在寻找的价值。PHP的HashTable的主要缺点是双向链表中多余的指针、zvals和buckets需要分配额外的内存，占用大量内存空间，查找时消耗大量时间。上面提到的不足在PHP7中得到了很好的解决。PHP7在内核中对数据结构进行了重大改造，使得PHP的效率大大提高。因此，建议PHP开发人员将开发和部署版本更新它。看看下面的PHP代码：
