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

函数执行流程图

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结构体内存

详细代码和注解请点击：zend_hash_del_key_or_index代码注解。

性能分析

PHP的哈希表的优点：PHP的HashTable为数组的操作提供了很大的方便，无论是数组的创建和新增元素或删除元素等操作，哈希表都提供了很好的性能，但其不足在数据量大的时候比较明显，从时间复杂度和空间复杂度看看其不足。

不足如下：

• 保存数据的结构体zval需要单独分配内存，需要管理这个额外的内存，每个zval占用了16bytes的内存；
• 在新增bucket时，bucket也是额外分配，也需要16bytes的内存；
• 为了能进行顺序遍历，使用双向链表连接整个HashTable，多出了很多的指针，每个指针也要16bytes的内存；
• 在遍历时，如果元素位于bucket链表的尾部，也需要遍历完整个bucket链表才能找到所要查找的值

PHP的HashTable的不足主要是其双向链表多出的指针及zval和bucket需要额外分配内存，因此导致占用了很多内存空间及查找时多出了不少时间的消耗。

后续

（编辑：江门站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!