在 PHP 内核中，其中一个很重要的数据结构就是 HashTable 。我们常用的数组，在内核中就是用 HashTable 来实现。那么， PHP 的 HashTable 是怎么实现的呢？最近在看 HashTable 的数据结构，但是算法书籍里面没有具体的实现算法，刚好最近也在阅读 PHP 的源码，于是参考 PHP 的 HashTable 的实现，自己实现了一个简易版的 HashTable ，总结了一些心得，下面给大家分享一下。
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_DEBUG
int inconsistent;
#endif
} HashTable;
· nTableSize ， HashTable 的大小，以 2 的倍数增长
· nTableMask ，用在与哈希值做与运算获得该哈希值的索引取值， arBuckets 初始化后永远是 nTableSize-1
· nNumOfElements ， HashTable 当前拥有的元素个数， count 函数直接返回这个值
· nNextFreeElement ，表示数字键值数组中下一个数字索引的位置
· pInternalPointer ，内部指针，指向当前成员，用于遍历元素
· pListHead ，指向 HashTable 的第一个元素，也是数组的第一个元素
· pListTail ，指向 HashTable 的最后一个元素，也是数组的最后一个元素。与上面的指针结合，在遍历数组时非常方便，比如 reset 和 endAPI
· arBuckets ，包含 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 ，哈希值（或数字键值的 key
· nKeyLength ， key 的长度
· pData ，指向数据的指针
· pDataPtr ，指针数据
· pListNext ，指向 HashTable 中的 arBuckets 链表中的下一个元素
· pListLast ，指向 HashTable 中的 arBuckets 链表中的上一个元素
· pNext ，指向具有相同 hash 值的 bucket 链表中的下一个元素
· pLast ，指向具有相同 hash 值的 bucket 链表中的上一个元素
· arKey ， key 的名称
PHP 中的 HashTable 是采用了向量加双向链表的实现方式，向量在 arBuckets 变量保存，向量包含多个 bucket 的指针，每个指针指向由多个 bucket 组成的双向链表，新元素的加入使用前插法，即新元素总是在 bucket 的第一个位置。由上面可以看到， PHP 的哈希表实现相当复杂。这是它使用超灵活的数组类型要付出的代价。
HashTable 相关 API
· zend_hash_init
· zend_hash_add_or_update
· zend_hash_find
· zend_hash_del_key_or_index
zend_hash_init
函数执行步骤
· 设置哈希表大小
· 设置结构体其他成员变量的初始值 ( 包括释放内存用的析构函数 pDescructor)
注：
1 、 pHashFunction 在此处并没有用到， php 的哈希函数使用的是内部的 zend_inline_hash_func
2 、 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
函数执行步骤
· 计算 key 的哈希值和下标
· 遍历哈希值所在的 bucket ，如果找到 key 所在的 bucket ，则进行第三步，否则，指向下一个 bucket ，直到指向 bucket 链表中的最后一个位置
· 如果要删除的是第一个元素，直接将 arBucket[nIndex] 指向第二个元素；其余的操作是将当前指针的 last 的 next 执行当前的 next
· 调整相关指针
· 释放数据内存和 bucket 结构体内存
性能分析
PHP 的哈希表的优点： PHP 的 HashTable 为数组的操作提供了很大的方便，无论是数组的创建和新增元素或删除元素等操作，哈希表都提供了很好的性能，但其不足在数据量大的时候比较明显，从时间复杂度和空间复杂度看看其不足。
不足如下：
· 保存数据的结构体 zval 需要单独分配内存，需要管理这个额外的内存，每个 zval 占用了 16bytes 的内存；
· 在新增 bucket 时， bucket 也是额外分配，也需要 16bytes 的内存；
· 为了能进行顺序遍历，使用双向链表连接整个 HashTable ，多出了很多的指针，每个指针也要 16bytes 的内存；
· 在遍历时，如果元素位于 bucket 链表的尾部，也需要遍历完整个 bucket 链表才能找到所要查找的值
PHP 的 HashTable 的不足主要是其双向链表多出的指针及 zval 和 bucket 需要额外分配内存，因此导致占用了很多内存空间及查找时多出了不少时间的消耗。
后续
上面提到的不足，在 PHP7 中都很好地解决了， PHP7 对内核中的数据结构做了一个大改造，使得 PHP 的效率高了很多，因此，推荐 PHP 开发者都将开发和部署版本更新吧。看看下面这段 PHP 代码：
<?php
$size = pow(2, 16);
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = ($size - 1) * $size; $key <= $maxKey; $key += $size) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 个恶意的元素需要 ', $endTime - $startTime, ' 秒', "\n";
$startTime = microtime(true);
$array = array();
for ($key = 0, $maxKey = $size - 1; $key <= $maxKey; ++$key) {
$array[$key] = 0;
}
$endTime = microtime(true);
echo '插入 ', $size, ' 个普通元素需要 ', $endTime - $startTime, ' 秒', "\n";
上面这个 demo 是有多个 hash 冲突时和无冲突时的时间消耗比较。笔者在 PHP5.4 下运行这段代码，结果如下
插入 65536 个恶意的元素需要 43.72204709053 秒
插入 65536 个普通元素需要 0.009843111038208 秒
而在 PHP7 上运行的结果：
插入 65536 个恶意的元素需要 4.4028408527374 秒
插入 65536 个普通元素需要 0.0018510818481445 秒
可见不论在有冲突和无冲突的数组操作， PHP7 的性能都提升了不少，当然，有冲突的性能提升更为明显。至于为什么 PHP7 的性能提高了这么多，值得继续深究。
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/69992957/viewspace-2755603/ ，如需转载，请注明出处，否则将追究法律责任。
