[PHP内核探索]PHP中的哈希表-开发者社区

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的哈希表实现相当复杂。这是它使用超灵活的数组类型要付出的代价。

一个PHP中的HashTable的示例图如下所示：

(图片源自网络，侵权即删)

HashTable相关API

zend_hash_init
zend_hash_add_or_update
zend_hash_find
zend_hash_del_key_or_index

zend_hash_init

函数执行步骤

设置哈希表大小
设置结构体其他成员变量的初始值 (包括释放内存用的析构函数pDescructor)

详细代码注解点击：zend_hash_init源码

注：
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的属性值，然后添加到哈希表中
如果哈希表空间满了，则重新调整哈希表的大小