单击此处进行编辑.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;
PHP中的HashTable是采用了向量加双向链表的实现方式,向量在arBuckets变量保存,向量包含多个bucket的指针,每个指针指向由多个bucket组成的双向链表,新元素的加入使用前插法,即新元素总是在bucket的第一个位置。由上面可以看到,PHP的哈希表实现相当复杂。这是它使用超灵活的数组类型要付出的代价。
一个PHP中的HashTable的示例图如下所示:
HashTable相关API
zend_hash_init
函数执行步骤
详细代码注解点击:zend_hash_init源码(https://github.com/hoohack/read-php-src/blob/master/Zend/zend_hash.c#L175)
注:
1、pHashFunction在此处并没有用到,php的哈希函数使用的是内部的zend_inline_hash_func
2、zend_hash_init执行之后并没有真正地为arBuckets分配内存和计算出nTableMask的大小,真正分配内存和计算nTableMask是在插入元素时进行CHECK_INIT检查初始化时进行。
zend_hash_add_or_update
函数执行步骤
函数执行流程图
CONNECT_TO_BUCKET_DLLIST是将新元素添加到具有相同hash值的bucket链表。
CONNECT_TO_GLOBAL_DLLIST是将新元素添加到HashTable的双向链表。
详细代码和注解请点击:zend_hash_add_or_update代码注解。
zend_hash_find
函数执行步骤
详细代码和注解请点击:zend_hash_find代码注解(https://github.com/hoohack/read-php-src/blob/master/Zend/zend_hash.c#L1033)。
zend_hash_del_key_or_index
函数执行步骤
详细代码和注解请点击:zend_hash_del_key_or_index代码注解。
性能分析
PHP的哈希表的优点:PHP的HashTable为数组的操作提供了很大的方便,无论是数组的创建和新增元素或删除元素等操作,哈希表都提供了很好的性能,但其不足在数据量大的时候比较明显,从时间复杂度和空间复杂度看看其不足。
不足如下:
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的性能提高了这么多,值得继续深究。
原创文章,文笔有限,才疏学浅,文中若有不正之处,万望告知。
如果本文对你有帮助,请点下推荐吧,谢谢^_^
参考文章:
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源码(https://github.com/hoohack/read-php-src/blob/master/Zend/zend_hash.c#L175)
注:
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代码注解(https://github.com/hoohack/read-php-src/blob/master/Zend/zend_hash.c#L1033)。
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的性能提高了这么多,值得继续深究。
原创文章,文笔有限,才疏学浅,文中若有不正之处,万望告知。
如果本文对你有帮助,请点下推荐吧,谢谢^_^
参考文章:
- PHP数组的Hash冲突实例
- Understanding PHP’s internal array implementation (PHP’s Source Code for PHP Developers – Part 4)
- PHP’s new hashtable implementation