在 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 的性能进步了这么多，值得持续深究。