侯体宗的博客
  • 首页
  • Hyperf版
  • beego仿版
  • 人生(杂谈)
  • 技术
  • 关于我
  • 更多分类
    • 文件下载
    • 文字修仙
    • 中国象棋ai
    • 群聊
    • 九宫格抽奖
    • 拼图
    • 消消乐
    • 相册

PHP7数组的底层实现示例

php  /  管理员 发布于 7年前   190

PHP 数组具有的特性

PHP 的数组是一种非常强大灵活的数据类型,在讲它的底层实现之前,先看一下 PHP 的数组都具有哪些特性。

可以使用数字或字符串作为数组健值

$arr = [1 => 'ok', 'one' => 'hello'];

可按顺序读取数组

foreach($arr as $key => $value){ echo $arr[$key];}

可随机读取数组中的元素

$arr = [1 => 'ok', 'one' => 'hello', 'a' => 'world'];echo $arr['one'];echo current($arr);

数组的长度是可变的

$arr = [1, 2, 3];$arr[] = 4;array_push($arr, 5);

正是基于这些特性,我们可以使用 PHP 中的数组轻易的实现集合、栈、列表、字典等多种数据结构。那么这些特性在底层是如何实现的呢? 这就得从数据结构说起了。

数据结构

PHP 中的数组实际上是一个有序映射。映射是一种把 values 关联到 keys 的类型。

PHP 数组的底层实现是散列表(也叫 hashTable ),散列表是根据键(Key)直接访问内存存储位置的数据结构,它的key - value 之间存在一个映射函数,可以根据 key 通过映射函数得到的散列值直接索引到对应的 value 值,无需通过关键字比较,在理想情况下,不考虑散列冲突,散列表的查找效率是非常高的,时间复杂度是 O(1)。

从源码中我们可以看到 zend_array 的结构如下:

typedef struct _zend_array zend_array;typedef struct _zend_array hashTable;struct _zend_array {  zend_refcounted_h gc;  union {    struct {      ZEND_ENDIAN_LOHI_4(          zend_uchar  flags,          zend_uchar  nApplyCount,          zend_uchar  nIteratorsCount,          zend_uchar  reserve)    } v;    uint32_t flags;  } u;  uint32_t     nTableMask; // 哈希值计算掩码,等于nTableSize的负值(nTableMask = -nTableSize)  Bucket      *arData;   // 存储元素数组,指向第一个Bucket  uint32_t     nNumUsed;  // 已用Bucket数(含失效的 Bucket)  uint32_t     nNumOfElements; // 哈希表有效元素数  uint32_t     nTableSize;   // 哈希表总大小,为2的n次方(包括无效的元素)  uint32_t     nInternalPointer; // 内部指针,用于遍历  zend_long     nNextFreeElement; // 下一个可用的数值索引,如:arr[] = 1;arr["a"] = 2;arr[] = 3; 则nNextFreeElement = 2;  dtor_func_t    pDestructor;};

该结构中的 Bucket 即储存元素的数组,arData 指向数组的起始位置,使用映射函数对 key 值进行映射后可以得到偏移值,通过内存起始位置 + 偏移值即可在散列表中进行寻址操作。

Bucket 的数据结构如下:

typedef struct _Bucket {  zval       val; // 存储的具体 value,这里是一个 zval,而不是一个指针  zend_ulong    h;  // 数字 key 或字符串 key 的哈希值。用于查找时 key 的比较    zend_string   *key; // 当 key 值为字符串时,指向该字符串对应的 zend_string(使用数字索引时该值为 NULL),用于查找时 key 的比较} Bucket;

到这里有个问题出现了:存储在散列表里的元素是无序的,PHP 数组如何做到按顺序读取的呢?

答案是中间映射表,为了实现散列表的有序性,PHP 为其增加了一张中间映射表,该表是一个大小与 Bucket 相同的数组,数组中储存整形数据,用于保存元素实际储存的 Value 在 Bucekt 中的下标。Bucekt 中的数据是有序的,而中间映射表中的数据是无序的。

而通过映射函数映射后的散列值要在中间映射表的区间内,这就对映射函数提出了要求。

映射函数

PHP7 数组采用的映射方式:

nIndex = h | ht->nTableMask;

将 key 经过 time33 算法生成的哈希值 h 和 nTableMask 进行或运算即可得出映射表的下标,其中 nTableMask 数值为 nTableSize 的负数。并且由于 nTableSize 的值为 2 的幂次方,所以 nTableMask 二进制位右侧全部为 0,保证了 h | ht->nTableMask 的取值范围会在 [-nTableSize, -1] 之间,正好在映射表的下标范围内。另外,用按位或运算的方法和其他方法如取余的方法相比运算速度较高,这个映射函数可以说设计的非常巧妙了。

散列(哈希)冲突

不同键名的通过映射函数计算得到的散列值有可能相同,此时便发生了散列冲突。

对于散列冲突有以下 4 种常用方法:

1.将散列值放到相邻的最近地址里

2.换个散列函数重新计算散列值

3.将冲突的散列值统一放到另一个地方

4.在冲突位置构造一个单向链表,将散列值相同的元素放到相同槽位对应的链表中。这个方法叫链地址法,PHP 数组就是采用这个方法解决散列冲突的问题。

其具体实现是:将冲突的 Bucket 串成链表,这样中间映射表映射出的就不是某一个元素,而是一个 Bucket 链表,通过散列函数定位到对应的 Bucket 链表时,需要遍历链表,逐个对比 Key 值,继而找到目标元素。而每个 Bucket 之间的链接则是将原 value 的下标保存到新 value 的 zval.u2.next 里,新 value 放在当前位置上,从而形成一个单向链表。

举个例子:

当我们访问 $arr['key'] 的过程中,假设首先通过散列运算得出映射表下标为 -2 ,然后访问映射表发现其内容指向 arData 数组下标为 1 的元素。此时我们将该元素的 key 和要访问的键名相比较,发现两者并不相等,则该元素并非我们所想访问的元素,而元素的 zval.u2.next 保存的值正是另一个具有相同散列值的元素对应 arData 数组的下标,所以我们可以不断通过 zval.u2.next 的值遍历直到找到键名相同的元素。

扩容

PHP 的数组在底层实现了自动扩容机制,当插入一个元素且没有空闲空间时,就会触发自动扩容机制,扩容后再执行插入。

扩容的过程为:

如果已删除元素所占比例达到阈值,则会移除已被逻辑删除的 Bucket,然后将后面的 Bucket 向前补上空缺的 Bucket,因为 Bucket 的下标发生了变动,所以还需要更改每个元素在中间映射表中储存的实际下标值。

如果未达到阈值,PHP 则会申请一个大小是原数组两倍的新数组,并将旧数组中的数据复制到新数组中,因为数组长度发生了改变,所以 key-value 的映射关系需要重新计算,这个步骤为重建索引。

重建散列表

在删除某一个数组元素时,会先使用标志位对该元素进行逻辑删除,即在删除 value 时只是将 value 的 type 设置为 IS_UNDEF,而不会立即删除该元素所在的 Bucket,因为如果每次删除元素立刻删除 Bucket 的话,每次都需要进行排列操作,会造成不必要的性能开销。

所以,当删除元素达到一定数量或扩容后都需要重建散列表,即移除被标记为删除的 value。因为 value 在 Bucket 位置移动了或哈希数组 nTableSize 变化了导致 key 与 value 的映射关系改变,重建过程就是遍历 Bucket 数组中的 value,然后重新计算映射值更新到散列表。

关于 PHP7 的数组底层实现就总结这么些了,因为水平有限也无法研究的十分详尽清楚,如果有疑问或者不足之处欢迎提出~~

参考资料

《PHP7 的底层设计与源码实现》

php7-internal

总结

以上就是这篇文章的全部内容了,希望本文的内容对大家的学习或者工作具有一定的参考学习价值,谢谢大家对AIDI的支持。


  • 上一条:
    php的命名空间与自动加载实现方法
    下一条:
    PHP实现cookie跨域session共享的方法分析
  • 昵称:

    邮箱:

    0条评论 (评论内容有缓存机制,请悉知!)
    最新最热
    • 分类目录
    • 人生(杂谈)
    • 技术
    • linux
    • Java
    • php
    • 框架(架构)
    • 前端
    • ThinkPHP
    • 数据库
    • 微信(小程序)
    • Laravel
    • Redis
    • Docker
    • Go
    • swoole
    • Windows
    • Python
    • 苹果(mac/ios)
    • 相关文章
    • Laravel从Accel获得5700万美元A轮融资(0个评论)
    • PHP 8.4 Alpha 1现已发布!(0个评论)
    • 用Time Warden监控PHP中的代码处理时间(0个评论)
    • 在PHP中使用array_pop + yield实现读取超大型目录功能示例(0个评论)
    • Property Hooks RFC在PHP 8.4中越来越接近现实(0个评论)
    • 近期文章
    • 智能合约Solidity学习CryptoZombie第三课:组建僵尸军队(高级Solidity理论)(0个评论)
    • 智能合约Solidity学习CryptoZombie第二课:让你的僵尸猎食(0个评论)
    • 智能合约Solidity学习CryptoZombie第一课:生成一只你的僵尸(0个评论)
    • 在go中实现一个常用的先进先出的缓存淘汰算法示例代码(0个评论)
    • 在go+gin中使用"github.com/skip2/go-qrcode"实现url转二维码功能(0个评论)
    • 在go语言中使用api.geonames.org接口实现根据国际邮政编码获取地址信息功能(1个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf分页文件功能(0个评论)
    • gmail发邮件报错:534 5.7.9 Application-specific password required...解决方案(0个评论)
    • 欧盟关于强迫劳动的规定的官方举报渠道及官方举报网站(0个评论)
    • 在go语言中使用github.com/signintech/gopdf实现生成pdf文件功能(0个评论)
    • 近期评论
    • 122 在

      学历:一种延缓就业设计,生活需求下的权衡之选中评论 工作几年后,报名考研了,到现在还没认真学习备考,迷茫中。作为一名北漂互联网打工人..
    • 123 在

      Clash for Windows作者删库跑路了,github已404中评论 按理说只要你在国内,所有的流量进出都在监控范围内,不管你怎么隐藏也没用,想搞你分..
    • 原梓番博客 在

      在Laravel框架中使用模型Model分表最简单的方法中评论 好久好久都没看友情链接申请了,今天刚看,已经添加。..
    • 博主 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 @1111老铁这个不行了,可以看看近期评论的其他文章..
    • 1111 在

      佛跳墙vpn软件不会用?上不了网?佛跳墙vpn常见问题以及解决办法中评论 网站不能打开,博主百忙中能否发个APP下载链接,佛跳墙或极光..
    • 2016-10
    • 2016-11
    • 2017-06
    • 2017-07
    • 2017-08
    • 2017-09
    • 2017-11
    • 2017-12
    • 2018-01
    • 2018-02
    • 2018-03
    • 2020-03
    • 2020-04
    • 2020-05
    • 2020-06
    • 2020-07
    • 2020-09
    • 2021-02
    • 2021-03
    • 2021-04
    • 2021-05
    • 2021-06
    • 2021-07
    • 2021-08
    • 2021-09
    • 2021-10
    • 2021-11
    • 2021-12
    • 2022-01
    • 2022-02
    • 2022-05
    • 2022-06
    • 2022-07
    • 2022-08
    • 2022-09
    • 2022-10
    • 2022-11
    • 2022-12
    • 2023-01
    • 2023-02
    • 2023-03
    • 2023-04
    • 2023-05
    • 2023-06
    • 2023-07
    • 2023-08
    • 2023-09
    • 2023-10
    • 2023-11
    • 2023-12
    • 2024-01
    • 2024-02
    • 2024-03
    • 2024-04
    • 2024-05
    • 2024-06
    • 2024-07
    • 2024-09
    Top

    Copyright·© 2019 侯体宗版权所有· 粤ICP备20027696号 PHP交流群

    侯体宗的博客