课程咨询 :13623629309

太原PHP培训 > 达内新闻 > PHP内核探索:PHP中的哈希表(二)
  • PHP内核探索:PHP中的哈希表(二)

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

  • bucket结构体的定义

    太原php培训班

    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高级开发名企定制班(剩2个名额)

php高级开发名企定制班(剩2个名额)

开班日期:12-30

php高级开发周末班(剩5个名额)

php高级开发周末班(剩5个名额)

开班日期:12-30

php高级开发免费试听(剩5个名额)

php高级开发免费试听(剩5个名额)

开班日期:12-30

更多高级开发工程师精品班

更多高级开发工程师精品班

开班日期:12-30

  • 地址:山西省太原市小店区学府街长治路高新国际A座24层
  • 课程培训电话:13623629309     全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56

    在线客服系统