In the PHP kernel, one of the very important data structures is HashTable. The arrays we commonly use are implemented in the kernel using HashTable. So, how is PHP's HashTable implemented? I have been reading the data structure of HashTable recently, but there is no specific implementation algorithm in the algorithm books. I happened to be reading the source code of PHP recently, so I implemented one by referring to the implementation of PHP's HashTable. The simple version of HashTable summarizes some experiences and will be shared with you below.
The author has a simple version of HashTable implementation on github: HashTable implementation
In addition, I have a more detailed version of the PHP source code on github annotation. If you are interested, you can take a look and give it a star. PHP5.4 source code annotations. You can view the added annotations through the commit record.
Introduction to HashTable
The hash table is an effective data structure that implements dictionary operations.
Definition
Simply put, HashTable (hash table) is a data structure of key-value pairs. Supports operations such as insertion, search, and deletion. Under some reasonable assumptions, the time complexity of all operations in the hash table is O(1) (if you are interested in the relevant proof, you can check it out by yourself).
The key to implementing a hash table
In the hash table, instead of using keywords as subscripts, the hash function is used Calculate the hash value of the key as a subscript, and then calculate the hash value of the key when searching/deleting, so as to quickly locate the location where the element is saved.
In a hash table, different keys may calculate the same hash value. This is called a "hash conflict", which is to deal with two or more keys. The hash values are the same. There are many ways to resolve hash conflicts, such as open addressing, zippering, etc.
Therefore, the key to implementing a good hash table is a good hash function and a method of handling hash conflicts.
Hash function
There are four definitions to judge the quality of a hash algorithm: > * Consistency, equivalent keys Must produce equal hash values; > * Efficient and easy to calculate; > * Uniformity, hashes all keys evenly.
The hash function establishes the corresponding relationship between the key value and the hash value, that is: h = hash_func(key). The corresponding relationship is shown in the figure below:
Let us leave it to the experts to design a perfect hash function. Just use an existing more mature hash function. The hash function used by the PHP kernel is the time33 function, also called DJBX33A. Its implementation is as follows:
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;
}Note: The function uses a Implemented by 8 loops + switch, it is an optimization of the for loop, reducing the number of loop runs, and then executing the remaining elements that have not been traversed in the switch.
Zipper method
The method of storing all elements with the same hash value in a linked list is called the zipper method. When searching, first calculate the hash value corresponding to the key, then find the corresponding linked list based on the hash value, and finally search for the corresponding value sequentially along the linked list. The specific saved structure diagram is as follows:
PHP’s HashTable structure
After briefly introducing the data structure of the hash table, let's continue to see how the hash table is implemented in PHP.
(The picture comes from the Internet, any infringement will be deleted)
Definition of PHP kernel 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, the size of the HashTable, increases by a multiple of 2
nTableMask, used to perform an AND operation with the hash value to obtain the index value of the hash value, after arBuckets is initialized It is always nTableSize-1
nNumOfElements, the number of elements currently owned by the HashTable. The count function directly returns this value
nNextFreeElement, which represents a numeric key The position of the next numeric index in the value array
pInternalPointer, internal pointer, pointing to the current member, used to traverse the elements
pListHead, pointing to the HashTable The first element of is also the first element of the array
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的属性值，然后添加到哈希表中
如果哈希表空间满了，则重新调整哈希表的大小
函数执行流程图
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需要额外分配内存，因此导致占用了很多内存空间及查找时多出了不少时间的消耗。
后续
上面提到的不足，在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的性能提高了这么多，值得继续深究。
最后，笔者github上有一个简易版的HashTable的实现：HashTable实现
另外，我在github有对PHP源码更详细的注解。感兴趣的可以围观一下，给个star。PHP5.4源码注解。可以通过commit记录查看已添加的注解。
The above is the detailed content of Detailed explanation of hash tables in PHP. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
