乐趣区

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 中如何解决插入时产生的哈希冲突问题,实际上是使用了数组模拟链表的思想,这里不再展开,以后我会再开一篇专题来进行讲解。

退出移动版