PHP 5数组的实现

对于 PHP 5 的数组实现，本文以 PHP-5.6.31 为例进行研究。因为 PHP 7 相较 PHP 5 在数组方面的设计改动非常大，通过对比学习，我们可以更加理解 PHP 7 版本带来的革命性提升。限于篇幅，本章只是简单介绍，不做过多展开。

PHP 5的bucket与HashTable结构

首先看下 PHP5 的 bucket 以及 HashTable 结构定义：

typedef struct bucket {
    ulong h; /* 用于数值索引的哈希值。对于整数索引，h 存储的是整数值本身 */
    uint nKeyLength;  /* 用于字符串索引的键长度。包括终止符的长度 */
    void *pData; /* 指向存储数据的指针 */
    void *pDataPtr; /* 指向 zval 的指针，zval 是 PHP 中用于表示变量的结构 */
    struct bucket *pListNext; /* 用于维护哈希表中元素的双向链表结构，保持元素的插入顺序 */
    struct bucket *pListLast;
    struct bucket *pNext; /* 用于处理哈希冲突的链表结构 */
    struct bucket *pLast;
    const char *arKey; /* 用于字符串索引的键 */
} Bucket;

typedef struct _HashTable {
    uint nTableSize; /* 哈希表大小 */
    uint nTableMask; /* 哈希掩码 */
    uint nNumOfElements; /* 元素数量 */
    ulong nNextFreeElement; /* 下一个空闲元素 */
    Bucket *pInternalPointer;
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets; /* 指向桶（Bucket）数组的指针 */
    dtor_func_t pDestructor; /* 析构函数 */
    zend_bool persistent; /* 持久化标志 */
    unsigned char nApplyCount; /* 应用计数 */
    zend_bool bApplyProtection; /* 保护标志 */
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

（1）bucket 中新增的三个元素

先分析一下 bucket，这里除了 HashTable 设计中必要的三个元素外，还增加了一些字段，如图 5-3 所示。

image 2024 06 08 12 16 50 935
Figure 1. 图5-3 PHP 5的bucket结构示意图

  1. arKey：对应 HashTable 设计中的 key，表示字符串 key。

  2. h：对应 HashTable 设计中的 h，表示数字 key 或者字符串 key 的 h 值。

  3. pData 和 pDataPtr：对应 HashTable 设计中的 value。

    这里的 pData 和 pDataPtr 都是指针。一般地，value 都存储在 pData 所指向的内存空间，pDataPtr 是 NULL，即空指针。但有一种情况例外，如果 value 的大小等于一个指针的大小（大部分情况是指针），那么将不会额外申请内存空间存储这个指针，而是直接存储在 pDataPtr 上，再让 pData 指向 pDataPtr，这样可以减少内存碎片。

  4. nKeyLength:arKey 的长度。当 nKeyLength 等于 0 时，表示数字 key。之前有提到，比较字符串 key 是否相等时，会先比较 h 值，如果 h 值相等，则不会直接比较字符串的内容，而是先比较字符串的长度是否相等。这样可以提高比较的速度。

  5. pListLast、pListNext、pLast、pNext:4 个指向 bucket 的指针。

    为什么会有 4 个指针呢？原来，为了实现数组的两个语义，PHP 5 维护了两种双向链表。一种是全局链表，按插入顺序将所有的 bucket 全部串联起来，整个 HashTable 只有一个全局链表。另一种是局部链表，为了解决哈希冲突，每个 slot 维护着一个链表，将所有哈希冲突的 bucket 串联起来。也就是，每一个 bucket 都处在两个双向链表上。所以这 4 个指针的作用就很明显了：pLast 和 pNext 分别指向局部链表的前一个和后一个 bucket; pListLast 和 pListNext 则指向全局链表的前一个和后一个 bucket。

（2）HashTable 的成员变量

再让我们看一下 HashTable 的成员变量。

  1. arBuckets：是一个指针，指向一段连续的数组内存，这段数组内存并没有存储 bucket，而是存储着指向 bucket 的指针。每一个指针代表着一个 slot，并且指向 slot 局部链表的首元素。通过这个指针，可以遍历这个 slot 下的所有的 bucket。

  2. nTableSize:arBuckets 指向的连续内存中指针的个数，即表示 slot 的数量。该字段取值始终是 2 的 n 次方，最小值是 8，最大值为 0x80000000（2 的 31 次方）。当 bucket 数量大于 slot 数量时，肯定会存在某一个 slot 至少有两个 bucket，随着 slot 下 bucket 数量的增多，HashTable 逐渐退化成链表，性能会有严重下降。这时 PHP 5 会进行扩容，将 slot 数量加倍，然后进行 rehash，让 bucket 均匀分布在 slot 中。

  3. nTableMask：掩码。总是等于 nTableSize-1，即 2n-1，因此，nTableMask 的每一位都是 1。上文提到的哈希过程中，key 经过 hash1 函数，转为 h 值，h 值通过 hash2 函数转为 slot 值。这里的 hash2 函数就是 slot = h & nTableMask，进而通过 arBuckets[slot] 取得当前 slot 链表的头指针。

  4. nNumOfElements:bucket 元素的个数。在 PHP 5 中，删除某一个元素会将 bucket 从全局链表和局部链表中真正删除掉，并释放 bucket 本身以及 value 占用的内存。

  5. pListHead 和 pListTail：为了保证数组的第二个语义（有序），HashTable 维护了一个全局链表，这两个指针分别指向这个全局链表的头和尾。所以在 PHP 5 中的遍历实现，其实是遍历了这个双向链表。

其他字段限于篇幅不一一介绍。

PHP 5数组实现示例

下面举个例子：将 4 个 key-value 对插入数组中，按插入顺序，key 分别是："a"、"b"、"c"、"d"，并且假设 "a" 被映射到了 slot1，而 "b"、"c"、"d" 被映射到了 slot0 中（这里的 slot 映射只是为了举例说明哈希冲突问题），那么最终这个数组应该有 4 个元素，它在内存中的分布如图5-4所示（虚线表示全局链表，实线表示局部链表）。

image 2024 06 08 12 26 28 214
Figure 2. 图5-4 元素插入数组示例

可以看到 pListHead 和 pListTail 作为全局链表的表头和表尾，分别指向了 key 为 "a" 和 key 为 "d" 的 bucket。通过 pListHead 遍历全局链表，就可以按插入顺序 "a", "b", "c", "d" 遍历完整个 HashTable。同理，通过 pListTail 可以按插入顺序的逆序 "d", "c", "b", "a" 遍历完整个 HashTable，实现了语义二，即 HashTable 是有序的。

arBuckets 指向的指针数组内存中，slot0 和 slot1 这两个指针分别指向了各自局部链表的第一个 bucket:key 为 "a" 和 key 为 "d" 的 bucket。读者可能奇怪为什么 slot0 指向的 bucket 是 "d" 而不是 "b"。原来在哈希冲突发生的时候，会采用头插法将新加入的 bucket 插入到 slot 局部链表的头部。由于 "b" 最先插入，"c" 紧随其后，这时会将 "c" 插入到 slot0 这个链表中第 1 个 bucket 的位置，"b" 就变成了第 2 个 bucket。因此当 "d" 最后插入时，反而在最前面。

到这里，有没有想过 PHP 5 的数组设计在时间效率和空间效率上存在哪些问题呢？这里笔者觉得有以下问题。

  1. 每一个 bucket 都需要一次内存分配。尽管由于内存池的存在，不需要通过 malloc 函数直接申请系统内存，避免了系统调用在用户态和内核态之间的切换以及 malloc 函数额外开销所造成的空间浪费，但是内存申请的耗时还是存在并且不可忽略。

  2. 对于大部分场景，key-value 中的 value 都是 zval。这种情况下，每个 bucket 需要维护指向 zval 的指针 pDataPtr 以及指向 pDataPtr 的 pData 指针。空间效率不是很高。

  3. 为了保证数组的两个语义，每一个 bucket 需要维护 4 个指向 bucket 的指针。在 32位/64位 系统，每个 bucket 将为这 4 个指针付出 16字节/32字节。想象一下，对于拥有 1024 个 bucket 的 HashTable，为了实现数组的两个语义，需要额外 16KB/32KB 的内存。而且由于 bucket 内存分配是随机的，导致了 CPU 的 cache 命中率并不高，这样在遍历 HashTable 的时候并没有很高的性能。

PHP 7 的数组，对 HashTable 进行了全新的设计，在性能上和节约内存方面都有了很大的提升。具体是如何设计的呢？读者这里可以先自行思考如何实现更高时间效率和空间效率的数组，然后再进入后续章节，相信会更加有收获。