PHP7数组底层实现示例

时间：2021-08-20 来源：互联网编辑：宝哥软件园浏览：次

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 ']；回声电流($ arr)；数组的长度是可变的

$arr=[1，2，3]；$ arr[]=4；array_push($arr，5)；基于这些特性，我们可以在PHP中使用数组轻松实现集合、栈、列表、字典等各种数据结构。那么这些特性是如何在底层实现的呢？这从数据结构开始。

数据结构

PHP中的数组实际上是一个有序映射。映射是一种将值与键相关联的类型。

PHP数组的底层实现是hashTable。哈希表是一种根据键直接访问内存存储位置的数据结构。它的键值之间有一个映射函数，可以直接将映射函数得到的哈希值按照键索引到对应的值，不需要关键字比较。理想情况下，不考虑哈希冲突，哈希表的搜索效率很高，时间复杂度为O(1)。

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

typedef struct _ Zend _ array Zend _ array；typedef struct _ Zend _ array hashTable；struct _ Zend _ array { Zend _ ref count _ h GC；union { struct { ZEND _ ENDIAN _ LOHI _ 4(ZEND _ uchar flags，zend_uchar nApplyCount，zend_uchar nIteratorsCount，ZEND _ uchar reserve)} v；uint32_t标志；} u；uint32 _ t问题询问；//哈希值计算掩码，等于nTableSize(ntablemask=-nTableSize)bucket * ardata的负值；//存储元素数组，指向第一个Bucket uint32 _ t nNumUsed//已用桶(包括无效桶)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指向数组的起始位置，用映射函数映射键值可以得到偏移量，通过内存起始位置的偏移量可以在哈希表中进行寻址操作。

Bucket的数据结构如下：

typedef struct _ Bucket { zval val//具体的存储值，这里是一个zval，不是指针Zend _ ulong h；//数字键或字符串键的哈希值。用于查找密钥的Comparison zend _ string *密钥；//当键值为字符串时，指向该字符串对应的zend_string(使用数值索引时值为NULL)，用于搜索时比较关键字} Bucket这里有一个问题：哈希表中存储的元素顺序不对，PHP数组怎么能按顺序读取？

答案是中间映射表。为了实现哈希表的排序，PHP增加了一个中间映射表，它是一个与Bucket大小相同的数组。该数组存储整形数据，用于保存实际存储在Bucekt元素中的值的下标。Bucekt中的数据是有序的，而中间映射表中的数据是无序的。

映射函数映射的哈希值应该在中间映射表的区间内，这需要映射函数。

映射函数

PHP7数组采用的映射方法：

nIndex=h | ht-n问题询问；映射表的下标可以通过time33算法生成的哈希值H与n个问题的OR运算得到，其中n个问题的值为n个问题的负数。而且因为nTableSize的值是2的幂，所以nTableMask的右位都是0，保证了h | ht-nTableMask的取值范围会在[-nTableSize，-1]之间，正好在映射表的下标范围内。另外，与取余数等其他方法相比，按位OR的运算速度更高，所以这个映射函数可以说设计得非常巧妙。

哈希冲突

映射函数为不同的键名计算的哈希值可能是相同的，然后会发生哈希冲突。

有四种常见的哈希冲突方法：

1.将哈希值放在相邻的最近地址中

2.使用不同的哈希函数重新计算哈希值

3.将冲突的哈希值放在另一个地方

4.在冲突位置构造一个单向链表，将哈希值相同的元素放入同一槽对应的链表中。这种方法被称为链地址法，由PHP数组用来解决哈希冲突的问题。

具体实现是将冲突的Bucket串成链表，这样中间映射表就不会映射某个元素，而是一个Bucket链表。通过hash函数定位对应的桶链表时，需要遍历链表，逐个比较Key值，然后找到目标元素。每个Bucket之间的链接是将原始值的下标保存到新值的zval.u2.next中，并将新值放在当前位置，从而形成单向链表。

例如：

当我们访问$arr['key']时，通过哈希运算假设映射表索引为-2，然后我们访问映射表，发现其内容指向arData数组的元素索引1。这时候我们把这个元素的键和要访问的键名进行比较，发现它们并不相等，所以这个元素并不是我们想要访问的，元素的zval.u2.next保存的值是另一个哈希值相同的元素对应的arData数组的下标，所以我们可以不断遍历zval.u2.next的值，直到找到相同键名的元素。

膨胀

PHP的数组在底层实现了自动扩展机制。当插入一个元素，没有自由空间时，会触发自动展开机制，展开后再进行插入。

扩展过程如下：

如果删除元素的比例达到阈值，则逻辑上已删除的存储桶将被删除，然后后续存储桶将被空存储桶填充。因为Bucket的下标发生了变化，所以需要为每个元素改变存储在中间映射表中的实际下标值。

如果没有达到阈值，PHP会申请一个大小是原数组两倍的新数组，并将旧数组中的数据复制到新数组中。由于数组的长度发生了变化，需要重新计算键值的映射关系。这一步是重建索引。

重建哈希表

删除数组元素时，会先用标志位对元素进行逻辑删除，也就是在删除值时，值的类型只会设置为IS _ UNDEF，元素所在的Bucket不会被立即删除，因为如果每次删除元素都会立即删除Bucket，那么每次都需要进行排列，会造成不必要的性能开销。

因此，当删除的元素数量达到一定数量或扩展后，需要重新构建哈希表，即删除标记为已删除的值。重建过程是遍历Bucket数组中的值，然后重新计算映射值并将其更新到哈希表中，因为键和值之间的映射关系会因为值在Bucket位置移动或哈希数组的nTableSize更改而更改。

这就是PHP7数组底层实现的全部内容，因为层次有限，无法详细研究。如果你有任何问题或缺点，请提问~ ~

参考材料

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

php7-内部