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 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

15:Challenge 11(主席树裸题)

总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

34913
来自专栏大闲人柴毛毛

三分钟理解“模板方法模式”——设计模式轻松掌握

模板方法模式的官方定义: 在模板方法模式中,只定义一个算法的骨架,而将一些步骤延迟到子类中。模板方法使得子类可以不改变一个算法的结构即可重新定义该算法的某些特定...

36810
来自专栏C语言及其他语言

[蓝桥杯]Hello, world!

题目描述 This is the first problem for test. Since all we know the ASCII code, your ...

3488
来自专栏数据结构与算法

08:Challenge 1

总时间限制: 10000ms单个测试点时间限制: 1000ms内存限制: 262144kB描述 给一个长为N的数列,有M次操作,每次操作是以下两种之一: (1)...

30912
来自专栏云霄雨霁

Java虚拟机--Class文件结构

1725
来自专栏郑科的专栏

PHP7 新特性简介(一)

PHP7是PHP编程语言全新的一个版本,在性能方面获得了极大的提升。官方的文档显示,PHP7可以达到PHP5.x版本两倍的性能。同时还提供了很多其他语言流行的语...

6360
来自专栏zhangdd.com

nginx location匹配规则

~      #波浪线表示执行一个正则匹配,区分大小写 ~*    #表示执行一个正则匹配,不区分大小写 ^~    #^~表示普通字符匹配,如果该选项匹配...

1064
来自专栏Linyb极客之路

并发编程之Synchronized关键字

一、Synchronized的基本使用 Synchronized是Java中解决并发问题的一种最常用的方法,也是最简单的一种方法。Synchronized的作...

2936
来自专栏liukaili_666888999

swift基础1

872
来自专栏WebDeveloper

跟我学习php字符串常用函数-下篇

1> mixed parse_url ( string $url [, int $component = -1 ] )

952

扫码关注云+社区

领取腾讯云代金券