在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的性能进步了这么多，值得持续深究。
转载请注明原文链接：PHP内核探索PHP中的哈希表
