太原PHP培训
达内太原php培训中心

0351-5608878

热门课程

PHP内核探索:PHP中的哈希表(二)

  • 时间:2016-07-07
  • 发布:太原PHP培训
  • 来源:伯乐在线

bucket结构体的定义

<a style='color:blue' href='http://ty.php.tedu.cn'>太原php培训</a>班

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的示例图如下所示:

太原达内php培训班

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的属性值,然后添加到哈希表中

如果哈希表空间满了,则重新调整哈希表的大小

函数执行流程图

太原达内php培训班

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培训班

上面这个demo是有多个hash冲突时和无冲突时的时间消耗比较。笔者在PHP5.4下运行这段代码,结果如下

插入 65536 个恶意的元素需要 43.72204709053 秒

插入 65536 个普通元素需要 0.009843111038208 秒

而在PHP7上运行的结果:

插入 65536 个恶意的元素需要 4.4028408527374 秒

插入 65536 个普通元素需要 0.0018510818481445 秒

可见不论在有冲突和无冲突的数组操作,PHP7的性能都提升了不少,当然,有冲突的性能提升更为明显。至于为什么PHP7的性能提高了这么多,值得继续深究。

原创文章,文笔有限,才疏学浅,文中若有不正之处,万望告知。

如果本文对你有帮助,请点下推荐吧,谢谢^_^

上一篇:PHP内核探索:PHP中的哈希表(一)
下一篇:为什么你应该学习编程

PHP autoload 机制详解

太原达内php培训班:10个值得深思的PHP面试问题

太原php培训班:10个值得深思的PHP面试问题(一)

选择城市和中心
贵州省

广西省

海南省