解析PHP8底层内核源码-数组（三）

上文已经全文剖析了PHP中数组的基本结构实现和 索引的组成原理

依赖于 _Bucket 和 _zend_array 两个结构体

通过散列函数实现o(1）的复杂度

可是bucket之前还有一个 索引数组 我当时在理解这个索引数组的时候走了不少坑

下图为 $c =array('x'=>1,'y'=>2,'z'=>3,'a'=>0); 中数组c的bucket结构

/2021/06/9b9a0213.jpg" data-caption="" data-size="normal" data-rawwidth="1440" data-rawheight="397" class="origin_image zh-lightbox-thumb" width="1440" data-original="https://pic3.zhimg.com/v2-82de82d13a44a18e25e31b9da41c1bda_r.jpg /2021/06/bc35a986.png" /2021/06/bc35a986.png" alt="4a167edc4a1a3e15753be51c8808d70.png

上文已经说了 如果是packed_array的时候 索引数组一直是2 也不会发挥作用

因为如果是packed key直接是null 也不需要去计算hash值 这个索引数组只是用于快速定位h值所用

/2021/06/8f5b159e.jpg" data-size="normal" data-rawwidth="1600" data-rawheight="600" class="origin_image zh-lightbox-thumb" width="1600" data-original="https://pic1.zhimg.com/v2-1abc881428724203c7c6e915eef49d1c_r.jpg /2021/06/e18975b4.png" /2021/06/e18975b4.png" alt="224e6328afdb6438b0ae2aa8d7726be.png

typedef struct _Bucket {
zval              val;   //数组的值 ( 复习下 zval只有16个字节)
zend_ulong         h;     // key的 h  值
zend_string      *key;      //当数组为 hash_array时候 会用到 也就是 key的值  
} Bucket;

当为packedarray的时候 也不要被val影响了你的学习思路 h值就等于 数组的位置的下标(数组都是从0开始 ，所以下标也从0开始)。比如上文提到的
$b =array(1=>'a',3=>'b',5=>'c'); 其中数组b 一样也是packed_array 结构如下

/2021/06/820d7374.jpg" data-caption="" data-size="normal" data-rawwidth="1532" data-rawheight="358" class="origin_image zh-lightbox-thumb" width="1532" data-original="https://pic3.zhimg.com/v2-f8b2c3df23f5591df1a345c8d99043c6_r.jpg /2021/06/870243f1.png" /2021/06/870243f1.png" alt="3cd34252d7729f5f230e5a3a5027106.png

因为数组b没有定义第0个数组的值 所以 是无效的 其中$b[1]内容是‘a’ 这里我图上是直接标出了val=a(zval) 其实 是16字节的zval中 类型为 string的 zend_string 这里面又套了之前学到的gc 等 所有PHP内核源码里存在很多无限套娃 方便你温故知新。

返回来再说 $c =array('x'=>1,'y'=>2,'z'=>3,'a'=>0);

结构如下

/2021/06/9b9a0213.jpg" data-caption="" data-size="normal" data-rawwidth="1440" data-rawheight="397" class="origin_image zh-lightbox-thumb" width="1440" data-original="https://pic3.zhimg.com/v2-82de82d13a44a18e25e31b9da41c1bda_r.jpg /2021/06/bc35a986-1.png" /2021/06/bc35a986-1.png" alt="021be407f0bf388d14f1fb765a32d92.png

这个h值很大 是用key 通过time33计算得来的哈希值 我也不知道为什么叫哈希值 我觉得就是通过time33计算得来的h值 然后形成散列表

/2021/06/4bf363e1.jpg" data-caption="" data-size="normal" data-rawwidth="1692" data-rawheight="950" class="origin_image zh-lightbox-thumb" width="1692" data-original="https://pic3.zhimg.com/v2-35a05a4c47707af38cbbc48bfaa85312_r.jpg /2021/06/4d404266.png" /2021/06/4d404266.png" alt="0ef5476843285bb71393ffaf965d777.png

散列表主要由两部分组成:存储元素数组、散列函数。一个简单的散列函数可以采用取余数的方式，比如 散列表大小为8 那么在散列表初始化数组的时候就分配8个元素大小的空间，跟进key的hash code 除以8 得到的值就是该元素在数组中的下标。这样就可以通过key映射到存储数组中的具体位置

/2021/06/c5b77505.jpg" data-caption="" data-size="normal" data-rawwidth="1564" data-rawheight="1354" class="origin_image zh-lightbox-thumb" width="1564" data-original="https://pic3.zhimg.com/v2-5a28c0c6ce9d1dc99b4901e4d1123a32_r.jpg /2021/06/973c1bb6.png" /2021/06/973c1bb6.png" alt="499a6c30bd075efe1b957822d32e96a.png

但是直接用上面的方式实现数组 会有一个问题 :元素在数组中位置是随机的 它是无序的

PHP中的数组是有序的 所以它在散列函数与元素数组之间加了一层索引表 这个索引表也是一个数组。大小与存储元素的数组相同。但是它存储的元素类型永远都是整型，用于保存元素数组在实际存储的数组中的下标：元素按照先后顺序依次插入实际存储数组中 ，然后将其数组下标按照散列函数计算出的位置存储在新加的索引标中。

/2021/06/10b35d09.jpg" data-caption="" data-size="normal" data-rawwidth="1588" data-rawheight="1448" class="origin_image zh-lightbox-thumb" width="1588" data-original="https://pic3.zhimg.com/v2-71e0e536a3e0de5e993f3213d15a6142_r.jpg /2021/06/870243f1-1.png" /2021/06/870243f1-1.png" alt="5c9f67f91d7a5d3eccb667e16842d7a.png

第一步计算出来 4 然后 取索引表中 找到-4 因为这是第0个数组所以把索引表中第-4个数组里面的值设置为0 然后把真正的数组表中第0个元素设置为真正赋值的zval

散列表中不同元素的key 可能最后计算得到的哈希值 是一样的 也就是指向同一个索引表中的下标 这个时候就会发生hash冲突 。因为索引表只能存一个元素 PHP为了实现hash冲突 采用了拉链法 就是把值用链表拉起来 。可以参考下图 《PHP7 内核剖析-秦朋》

/2021/06/ce9d42c0.jpg" data-caption="" data-size="normal" data-rawwidth="1720" data-rawheight="1052" class="origin_image zh-lightbox-thumb" width="1720" data-original="https://pic3.zhimg.com/v2-9b1c299f1bcaf12b56df7b95d2827732_r.jpg /2021/06/acb2ac7f.png" /2021/06/acb2ac7f.png" alt="0d97a77d9d7bce4216fca1176b53034.png

正常情况 val.u2.next 的值为-1 也就是初始值 一旦出现hash冲突 那么这里的值就会指向 冲突之前的数组的真实位置 。

▏本文经原作者PHP崔雪峰同意，发布在北冥有鱼，原文地址：https://zhuanlan.zhihu.com/p/360952022