PHP7 数组的底层实现

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

You can not connect the dots looking forward, you can only connect them looking backwards.

《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L03 构架 API 服务器》
你将学到如 RESTFul 设计风格、PostMan 的使用、OAuth 流程,JWT 概念及使用 和 API 开发相关的进阶知识。
讨论数量: 1

有兴趣一起看swoole源码吗

3周前 评论
JeffreyC (楼主) 3周前

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!