PHP源码学习剖析PHP7数组的有序性

baiyan

案例

在 PHP7 中，我们往数组中插入元素的顺序，就决定了我们数组遍历元素的顺序。可以说，PHP7 中的数组是有序的。这个有序就是指 元素插入数组时的顺序 ，与 遍历时顺序 的一致性。为了直观地让大家了解到 PHP7 数组的有序性，请看下面一段 PHP 代码：

<?php
$a = [];
$a['insert1'] = 'baiyan1';
$a['insert2'] = 'baiyan2';
$a['insert3'] = 'baiyan3';
foreach ($a as $k => $v) {var_dump($k . ':' . $v);
}

我们按照 1、2、3 的顺序向数组中插入 key-value 对，然后在循环体中打印遍历的顺序，结果如下：

string(15) "insert1:baiyan1"
string(15) "insert2:baiyan2"
string(15) "insert3:baiyan3"

然后我们反转插入元素的顺序，以 3、2、1 的顺序插入，其余代码不变：

<?php
$a = [];
$a['insert3'] = 'baiyan3';
$a['insert2'] = 'baiyan2';
$a['insert1'] = 'baiyan1';
foreach ($a as $k => $v) {var_dump($k . ':' . $v);
}

同样的，打印结果如下：

string(15) "insert3:baiyan3"
string(15) "insert2:baiyan2"
string(15) "insert1:baiyan1"

观察以上两组输出结果，我们可以看到，往数组中插入元素的顺序决定了遍历的顺序，PHP 数组是有序的。

普通哈希表的问题：无序性

哈希表的无序性是指元素顺序与遍历顺序的不一致性。在 PHP7 中，为了达到查找某个 key 的复杂度为 O(1)，其内部是以 hashtable 的结构来实现的。先抛开 PHP 的实现不说，首先我们举一个一般的例子。通常情况下，一个 hashtable 长这样，每个存储单元被称为一个 bucket（桶）：

这个哈希表很普通，它的大小为 8，目前还没有任何元素插入，接下来我们插入上面的三条数据，假设对其 key 进行哈希运算的结果分别为 4、2、6，插入之后的情形如下（key 和 value 本来应该绑定在一起的，为了简化 故省略 value 的书写 ）：

我们想一下，这样存储的问题都有哪些：

• 元素之间的分布很零散，在扩容或缩容的时候不好处理
• 插入与遍历的无序性

第一条不是我们此篇文章的重点。我们在遍历这个数组的时候，单看这张图，我们是不知道插入的顺序是什么样的，只能通过 insert2、insert1、insert3 的顺序遍历。所以，遍历的顺序与插入的 insert1、insert2、insert3 的顺序并不吻合，并不能达到我们在 PHP7 中数组的预期。

PHP7 数组：解决普通哈希表的无序性问题

为了实现插入与遍历的顺序一致性，在 PHP7 中，增加了一个中间映射层，它的大小与哈希表相同，存储了元素在 bucket 中最终存储的位置。这样说可能大家还不太明白，让我们用图解一步一步来复现上一个案例的插入过程。我们先忽略哈希冲突的问题。首先我们插入 insert1 这个 key-value 对：

首先，假设对 key insert1 的哈希运算结果为 4，由于现在哈希表中的所有 bucket 均为空，所以我们可以利用第一个 bucket 空间来存储这个 insert1。为了让后续的查找等操作能够顺利找到 insert1，我们在映射表中下标为 4 的地方记录下 insert1 存储的位置，即 bucket 的下标 0。这样，在查找的时候，根据这个 hash 值 4，通过映射表就能够顺利找到 insert1 在 bucket 中存储的位置 0。
然后我们继续插入 insert2 这对 key-value 对，同理，我们直接往后找可用的 bucket，下标为 1 的 bucket 就是可用的，那么我们准备把 insert2 存入这里，同时利用映射表记下存储的 bucket 下标 1：

假设对 key insert2 的哈希运算结果为 2，由于下一个可用的 bucket 下标为 1，我们需要记录下这个 1，而它的哈希运算结果为 2，我们就在映射表下标为 2 的位置记录下 insert2 的存储 bucket 位置 1。
到这里，我们可以发现，我们插入新元素的时候，会直接往后寻找可用的 bucket 位置，而这个位置是和之前插入的元素紧紧相邻的。这样，我们在 foreach 循环的时候，直接对这个 bucket 进行遍历，其遍历结果就是有序的。
如果你还没有明白，我们继续往中插入 insert3 这对 key-value 对：

假设对 key insert3 的哈希运算结果为 6，我们直接往后寻找可用的 bucket，下标为 2。我们需要记录下这个 2，于是在映射表下标为哈希值运算结果 6 的位置，存储下这个下标 2 即可。
这样一来，我们直接去遍历这个 hashtable，从 bucket 下标为 0 开始直接遍历到末尾，就能够得到与插入时候一摸一样的顺序，即 insert1、insert2、insert3 了，且元素之间没有碎片，提高了 hashtable 的空间利用率，方便扩容与缩容。
到这里，我们应该清楚了这个 映射表的作用 ： 实现 PHP7 数组的插入与遍历顺序一致性 。
在 PHP7 中，为了方便映射表的访问，没有将映射表的空间额外单独去分配，而是直接分配在与 hashtable 中前一块相邻的内存空间中，这样通过一个指针，就可以同时访问 映射表 和每一个 bucket啦：

在 PHP7 中，由于映射表的下标为负值，为了实现相同的功能，不能用我们之前直接使用哈希值做下标来存储 bucket 的位置，而是需要经过一步计算：

nIndex = h | nTableMask

由此，我们最后来看一下 PHP 中 hashtable 的结构，最重要的就是这个 arData 指针。通过它，我们可以同时访问映射表和哈希表中的 bucket：

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    nApplyCount,
                zend_uchar    nIteratorsCount,
                zend_uchar    consistency)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask;
    Bucket           *arData;  // 映射表以及哈希表的指针，利用 arData[-x]访问映射表，利用 arData[+x]访问哈希表中的 bucket
    uint32_t          nNumUsed;
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

typedef struct _zend_array HashTable;

由于我们这篇文章没有提到哈希冲突的问题，我们这里讲到的是最简单的插入情况。至于在 PHP 中如何解决插入时产生的哈希冲突问题，实际上是使用了数组模拟链表的思想，这里不再展开，以后我会再开一篇专题来进行讲解。