专栏首页大眼瞪小眼PHP HashTable总结

PHP HashTable总结

本篇文章主要是对 PHP HashTable 总结,下面的参考链接是很好的学习资料。学习“散列”这个数据结构—推荐《数据结构与算法分析 C语言描述》

总结

HashTable 又叫做散列表,是一种用于以常数平均时间执行插入、删除和查找的技术。不能有效的支持元素之间的排序。——《数据结构与算法分析 C语言描述》

HashTable 是 PHP 的灵魂,因为在 Zend 引擎中大量的使用了 HashTable,如变量表,常量表,函数表等,这些都是使用 HashTable 保存的,另外,PHP 的数组也是通过使用 HashTble 实现的。

接下来看下面这一句话:

Hashtable是非常常见的数据结构,它被设计出来解决计算机只能直接表示以连续的整数作为索引的数组的问题。使用Hashtable,程序员才能使用字符串或者其他的复合类型作为数组的键。

Hashtable 的概念:字符串的键先会被传递给一个 hash 函数(hashing function,中文也翻译为散列函数),然后这个函数会返回一个整数,而这个整数就是“通常”的数组的索引,通过这个数字索引可以访问到 字符串的键对应的数据。

关于 HashTable 的几个概念

  • 键(key):用于操作数据的标示,例如PHP数组中的索引,或者字符串键等等。
  • 槽(slot/bucket):哈希表中用于保存数据的一个单元,也就是数据真正存放的容器。
  • 哈希函数(hash function):将key映射(map)到数据应该存放的slot所在位置的函数。
  • 哈希冲突(hash collision):哈希函数将两个不同的key映射到同一个索引的情况。

对比 PHP 的数组和 C 语言的数组,发现 PHP 的数组确实支持更多的写法,下标不仅可以是数字也可以是字母等。另一方面 HashTable 是无序的,那 PHP 数组的顺序结构是怎么实现的呢?可以带着这些疑问阅读 PHP 源码。 

源码版本: php-7.1.19-src

解决哈希冲突一般有两种方式,PHP 使用的是分离链接法,既当产生冲突时,数据形成一个链表。

Hashtable 的数据结构

 1 typedef struct _Bucket {
 2     zval              val;                /* 存储的具体数据 */
 3     zend_ulong        h;                /* 一个 hash 值 */
 4     zend_string *key;                    /* 一个字符串键 */
 5 } Bucket;
 6 
 7 typedef struct _zend_array HashTable;
 8 
 9 struct _zend_array {
10     zend_refcounted_h gc;
11     union {
12         struct {
13             ZEND_ENDIAN_LOHI_4(
14                 zend_uchar    flags,
15                 zend_uchar    nApplyCount,
16                 zend_uchar    nIteratorsCount,
17                 zend_uchar    consistency)
18         } v;
19         uint32_t flags;
20     } u;
21     uint32_t          nTableMask;         /* 掩码,用于根据hash值计算存储位置,永远等于nTableSize-1 */
22     Bucket           *arData;             /* 存放实际数据 */
23     uint32_t          nNumUsed;         /* arData数组已经使用的数量 */
24     uint32_t          nNumOfElements;      /* hash表中元素个数 */
25     uint32_t          nTableSize;        /* hash表的大小 */
26     uint32_t          nInternalPointer;    /* 用于HashTable遍历 */
27     zend_long         nNextFreeElement; /* 下一个空闲可用位置的数字索引 */
28     dtor_func_t       pDestructor;         /* 析构函数 */
29 };

结构体 _Bucket 代表的是 PHP 里数组的元素, _zend_array 为 PHP 具体功能添加了一些必要的数据。

例如当将一个元素从哈希表删除时并不会将对应的Bucket移除,而是将Bucket存储的zval标示为IS_UNDEF,所以使用 nNumOfElements 保存 Hash 的元素个数,使用 nNumUsed 表示数组真实的使用数量。

nTableSize 表示分配的内存大小,最小为8。

HashTable中另外一个非常重要的值 arData ,这个值指向存储元素数组的第一个Bucket,插入元素时按顺序依次插入数组,比如第一个元素在arData[0]、第二个在arData[1]...arData[nNumUsed]。PHP数组的有序性正是通过arData保证的。

哈希表实现的关键是有一个数组存储哈希值与 Bucket 的映射,但是HashTable中并没有这样一个索引数组。实际上这个索引数组包含在arData中,在内存中一块存在。具体的位置如下图。

所以,整体来看 HashTable 主要依赖 arData 实现元素的存储、索引。插入一个元素时先将元素插入Bucket数组,位置是 index,再根据key的哈希值与nTableMask计算出索引数组的位置,将 index 存入这个位置;查找时先根据 key 的哈希值与 nTableMask 计算出索引数组的位置,获得元素在 Bucket 数组的位置 index,再从 Bucket 数组中取出元素。

哈希表的大小为2^n,插入时如果容量不够则首先检查已删除元素所占比例,如果达到阈值(ht->nNumUsed - ht->nNumOfElements > (ht->nNumOfElements >> 5),则将已删除元素移除,重建索引,如果未到阈值则进行扩容操作,扩大为当前大小的2倍,将当前Bucket数组复制到新的空间,然后重建索引。

参考

PHP 7中新的Hashtable实现和性能改进

PHP internals Book

PHP 哈希表(数组)的内核实现

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《算法之美》例题

    【3.4 拓展问题】编写一个函数,给定一个链表的头指针,要求只遍历一次,将单链表中的元素顺序反转过来。

    大眼瞪小眼
  • 程序的机器级表示

    预处理阶段:预处理器cpp根据编译文件以“#”开头的命令,读取系统头文件stdio.h(.h结尾的表示头文件,.c表示可执行文件)的内容,并把它插入到程序文本中...

    大眼瞪小眼
  • HTML定位简介

    定位一直是WEB标准应用中的难点,如果理不清楚定位那么可能应实现的效果实现不了,实现了的效果可能会走样。如果理清了定位的原理,那定位会让网页实现的更加完美。

    大眼瞪小眼
  • 前端测试题: 数组的扩展中,不属于用于数组遍历的函数的是?

    方法会返回一个由一个给定对象的自身可枚举属性组成的数组,数组中属性名的排列顺序和使用 for...in 循环遍历该对象时返回的顺序一致 。如果对象的键-值都不可...

    舒克
  • Javascript数组操作

    使用JS也算有段时日,然对于数组的使用,总局限于很初级水平,且每每使用总要查下API,或者写个小Demo测试下才算放心,一来二去,浪费不少时间;思虑下,堪能如此...

    晚晴幽草轩轩主
  • [随缘一题]合并排序数组ii

    呼延十
  • Python数据处理(2)-NumPy的ndarray

    NumPy是Python中众多科学软件包的基础。它提供了一个特殊的数据类型ndarray,其在向量计算上做了优化。这个对象是科学数值计算中大多数算法的核心。下面...

    企鹅号小编
  • data_structure_and_algorithm -- 哈希算法(上):如何防止数据库中的用户被脱库?

    还记得 2011 年 CSDN 的“脱库”事件吗?当时,CSDN 网站被黑客攻击,超过 600 万用户的注册邮箱和密码明文被泄露,很多网友对 CSDN 明文保存...

    MachineLP
  • Python 中那些令人拍案叫绝的功能!

    链接:www.oschina.net/translate/python-functions

    Rocky0429
  • 弱水三千,只取你标!AL(主动学习)结合GAN如何?

    众所周知,深度学习的崛起和广泛应用是依靠着大量的标注数据的,但在很多场合下,大规模数据的标注成本太高,同时也可能导致训练时间过长。主动学习可挑出所谓高信息的数据...

    公众号机器学习与生成对抗网络

扫码关注云+社区

领取腾讯云代金券