PHP 的数组（Array）是日常开发中最常用的数据结构，它既可以作为列表（List）使用，也可以作为字典（Map）使用。很多人只知道“PHP 数组很强大”，但当面试官问“PHP 数组底层是怎么实现的？扩容机制是怎样的？”时，往往答不上来。本文从底层结构出发，讲清楚 PHP 数组的哈希表实现与扩容机制。
一、PHP 数组的本质：有序哈希表
PHP 数组底层并不是简单的“连续内存 + 链表”，而是一个 HashTable（哈希表），并且它同时维护了元素的插入顺序，因此被称为 有序哈希表。
在 PHP 7 之后，HashTable 的结构做了较大优化，核心结构大致如下（以 PHP 7/8 为例）：
typedef struct _Bucket {
zval val; // 存储的值
zend_ulong h; // 哈希值
zend_string *key; // 字符串键，数字键为 NULL
} Bucket;
typedef struct _HashTable {
uint32_t nTableSize; // 哈希表容量，始终为 2 的幂
uint32_t nTableMask; // 掩码，等于 nTableSize - 1
uint32_t nNumUsed; // 已使用的 Bucket 数量
uint32_t nNumOfElements; // 有效元素个数
zend_long nNextFreeElement; // 下一个自增数字键
Bucket *arData; // Bucket 数组
uint32_t *arHash; // 哈希索引表
} HashTable;
关键点：
arData是一个连续的Bucket数组，元素按插入顺序依次存放。arHash是一个索引表，保存的是arData的下标，用于通过哈希值快速定位元素。nTableSize永远是 2 的幂，nTableMask = nTableSize - 1，这样可以用位运算代替取模，提高效率。
二、哈希冲突如何解决
PHP 数组使用 链地址法（拉链法） 解决哈希冲突，但与常见的链表实现不同，PHP 7 之后不再使用显式链表指针，而是通过 arHash 中的“链表”来串联冲突元素。
查找过程大致如下：
- 对 key 计算哈希值
h。 - 用
h & nTableMask得到哈希槽位置idx。 - 从
arHash[idx]取出arData的下标。 - 比较 key 是否相等，若相等则命中。
- 若冲突，则沿着
arHash中保存的“下一个下标”继续查找。
这种设计让 Bucket 结构更紧凑，减少了内存占用，也提升了 CPU 缓存命中率。
三、插入与更新流程
以插入一个元素为例：
- 计算 key 的哈希值。
- 在
arData的nNumUsed位置写入新的Bucket。 - 将新 Bucket 的下标插入到
arHash对应槽的链表中。 nNumUsed++，nNumOfElements++。
如果 key 已存在，则直接更新对应 Bucket 的 val，不会新增元素。
需要注意的是，删除元素时 PHP 并不会立即移动 arData，而是把该 Bucket 的 val 标记为 IS_UNDEF。这样做的目的是保持插入顺序和索引稳定，避免大量数据搬移。但这也意味着 nNumUsed 可能大于 nNumOfElements，当“空洞”过多时，会触发 rehash（重建哈希表）。
四、扩容机制：什么时候扩容
PHP 数组的扩容发生在插入新元素时。判断条件大致是：
- 当
nNumUsed >= nTableSize时，说明arData已经写满，需要扩容。 - 扩容时，新容量为原容量的 2 倍，即
nTableSize = nTableSize * 2。 - 同时重新计算
nTableMask，并重建arHash索引表。
扩容不是简单的“翻倍 + 复制”，而是一个 rehash 过程：
- 申请新的、更大的
arData和arHash。 - 遍历旧的
arData，跳过已删除的IS_UNDEF元素。 - 将有效元素重新计算哈希槽，插入新的
arHash。 - 释放旧内存。
因此，扩容的代价是 O(n)，但它不是每次插入都发生，而是按 2 的幂次增长，均摊到每次插入的复杂度仍然是 O(1)。
五、为什么容量必须是 2 的幂
这是 PHP 数组设计中的一个关键优化：
- 当
nTableSize是 2 的幂时，nTableMask = nTableSize - 1的低位全是 1。 - 此时
h & nTableMask等价于h % nTableSize，但位运算比取模快得多。 - 同时，哈希值分布更均匀，减少冲突概率。
这也是为什么 PHP 数组的容量总是 8、16、32、64…… 这样的 2 的幂。
六、packed array 与 hash array
PHP 7 之后，数组内部还区分两种形态：
- packed array（紧凑数组）：键是连续递增的整数（0、1、2……），此时
arHash可以不使用，查找和遍历更快，内存更省。 - hash array（哈希数组）：键是字符串或不连续的整数，需要完整的
arHash索引。
当 packed array 中插入一个非连续整数键或字符串键时，会转换为 hash array。这也是为什么“尽量使用连续整数键”能提升性能的原因。
七、面试答题要点总结
如果面试中被问到这个问题，可以按以下逻辑回答：
- PHP 数组底层是 有序哈希表，同时支持列表和字典。
- 核心结构包括
arData（Bucket 数组）和arHash（哈希索引表）。 - 使用 链地址法 解决哈希冲突，但用索引表模拟链表。
- 容量始终为 2 的幂，用位运算代替取模。
- 插入时若
nNumUsed >= nTableSize，则 翻倍扩容并 rehash。 - 删除元素只标记
IS_UNDEF，不立即搬移，空洞过多时触发 rehash。 - PHP 7 后区分 packed array 和 hash array，连续整数键性能更优。
理解这些底层机制，不仅能帮助你在面试中脱颖而出，也能在实际开发中写出更高效的 PHP 代码。
未经允许不得转载：任鹏个人博客 » PHP 面试题：说说 PHP 数组底层哈希表实现与扩容机制
