基本概念

在开始了解 PHP 数组实现细节之前，我们有必要知道，PHP 数组的设计目标以及相关基本概念。本节将对 PHP 数组的语义以及基本概念进行说明。

数组的语义

无论是 PHP 5 还是 PHP 7，在实现 PHP 数组的时候，首先需要明确 PHP 数组的设计目标，即 PHP 数组具有哪些语义。那么什么是 PHP 数组？它可以为 PHP 开发者提供哪些能力呢？本质上，PHP 数组是一个有序的字典。它必须同时满足如下两个语义。

  • 语义一：PHP 数组是一个字典，存储着键-值（key-value）对。通过键可以快速地找到对应的值，键可以是整型，也可以是字符串。

  • 语义二：PHP 数组是有序的。这个有序指的是插入顺序，即遍历数组的时候，遍历元素的顺序应该和插入顺序一致，而不像普通字典一样是随机的。

为了实现语义一，PHP 使用 HashTable 来存储键-值对。但是 HashTable 本身并不能保证语义二，为了实现语义二，PHP 不同版本中都对 HashTable 进行了一些额外设计来保证有序，而其中尤以 PHP 7 的设计最为巧妙。5.3 节会详细展开阐述 PHP 7 数组的实现，在此之前，先讨论一下数组的概念。

数组的概念

PHP 的数组 zend_array 对应的是 HashTable。HashTable 是哈希表（也叫散列表），也是一种通过某种哈希函数将特定的键映射到特定值的一种数据结构，它维护着键和值的一一对应关系，并且可以快速地根据键检索到值，查找效率为 \$O(1)\$。HashTable 的示意如图5-1所示。

image 2024 06 08 12 07 30 415
Figure 1. 图5-1 HashTable示意

  1. key：键，通过它可以快速检索到对应的 value。一般是数字或字符串。

  2. value：值，目标数据。可以是复杂的数据结构。

  3. bucket：桶，HashTable 中存储数据的单元。用来存储 key 和 value 以及辅助信息的容器。

  4. slot：槽，HashTable 有多个槽，一个 bucket 必须从属于具体的某一个 slot，一个 slot 下可以有多个 bucket。

  5. 哈希函数：需要自己实现，在存储的时候，会对 key 应用哈希函数确定所在的 slot。

  6. 哈希冲突：当多个 key 经过哈希计算后，得出的 slot 的位置是同一个，那么就叫作哈希冲突。这时，一般有两种方法解决冲突——链地址法 和 开放地址法。PHP 中采用的是链地址法，即将同一个 slot 中的 bucket 通过链表连接起来。

在具体实现过程中，PHP 基于上述基本概念，对 bucket 以及哈希函数进行了一些补充，增加了 hash1 函数以生成 h 值，然后通过 hash2 函数散列到不同的 slot，如图5-2所示。

image 2024 06 08 12 10 26 264
Figure 2. 图5-2 带有h值的HashTable示意图

  1. bucket 里面增加 h 字段。

  2. 哈希函数拆分成了 hash1 和 hash2 函数。hash1 将 key 映射为 h 值，hash2 将 h 值映射为 slot 的索引值。

  3. bucket 里面的 key 字段作为字符串 key，不再表示数字 key。

这个 h 值的作用是什么呢？笔者认为是出于两方面的考虑。

一方面由于 HashTable 中 key 可能是数字，也有可能是字符串，所以 bucket 在设计 key 的时候，需要做拆分，拆分成数字 key 和字符串 key，在上图的 bucket 中，“h” 代表数字 key，“key” 代表字符串 key。实际上，对于数字 key, hash1 函数没有做任何事情，h 值就是数字 key。

另一方面，每一个字符串 key，经过 hash1 函数都会计算出一个 h 值。这个 h 值可以加快字符串 key 之间的比较速度。如果要比较两个字符串 key1 和 key2 是否相等，会首先比较 key1 和 key2 的 h 值是否相等，如果相等，再去比较字符串的长度以及内容。否则，可直接判定 key1 和 key2 不相等。在大部分场景，不同字符串的 h 值都不会发生碰撞，这大大提高了 HashTable 插入、查找的速度。

讨论完数组的语义和数组的概念后，为了更好地理解 PHP 7 数组实现的精妙之处，我们首先来讨论一下 PHP 5 数组的实现。