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