PHP 的数组（array）是这门语言中使用频率最高的数据结构，它同时支持整数索引和字符串键，兼具列表、字典、集合的能力。这种灵活性背后，依赖的是 PHP 内核中一个精心设计的 HashTable 实现。本文将深入 Zend 引擎源码层面，剖析 PHP 数组从哈希计算、冲突处理到有序遍历的完整设计。
HashTable 的整体结构
PHP 的数组在底层对应 zend_array（即 HashTable），其核心结构可以简化为以下几个部分：
- Bucket 数组：存储实际元素的连续内存区域，每个 Bucket 包含
key、val（zval）以及h（哈希值）和next指针。 - 哈希索引表：一个指针数组，用于快速定位 Bucket，解决冲突。
- 全局链表指针：
head、tail以及每个 Bucket 中的next/prev，维护元素的插入顺序。
这种设计的关键在于：哈希索引表负责快速查找，而双向链表负责维护顺序，两者通过同一个 Bucket 结构耦合在一起。
哈希函数与冲突处理
PHP 对整数键直接使用其值作为哈希（经过简单混合），对字符串键则使用 DJBX33A 哈希算法。该算法计算速度快，分布较为均匀，适合短字符串为主的 Web 场景。
当两个不同的键计算出相同的哈希值时，就发生了哈希冲突。PHP 采用链地址法（Separate Chaining）解决冲突：哈希索引表的每个槽位存储一个指向 Bucket 的指针，冲突的元素通过 Bucket 中的 next 指针形成单向链表。
// 简化示意
typedef struct _Bucket {
zval val;
zend_ulong h; // 哈希值
zend_string *key; // 字符串键（整数键为 NULL）
struct _Bucket *next; // 冲突链指针
} Bucket;
查找时，先通过 h & nTableMask 定位到哈希槽，然后遍历该槽上的冲突链，逐一比较哈希值和键。由于 PHP 的哈希表在扩容时会保持负载因子在合理范围，冲突链通常很短，查找效率接近 O(1)。
扩容与 rehash 策略
当哈希表中的元素数量超过一定阈值时，PHP 会触发扩容（rehash）。Zend 引擎采用2 的幂次作为哈希表大小，这样可以用位运算 h & (size - 1) 代替取模运算，提升性能。
扩容时，引擎会分配一个更大的 Bucket 数组和哈希索引表，然后遍历所有元素，重新计算它们在哈希索引表中的位置。值得注意的是，PHP 的 rehash 不会打乱元素的插入顺序，因为顺序由独立的双向链表维护，rehash 只影响哈希索引表。
有序遍历的实现
这是 PHP 数组最精妙的设计之一。每个 Bucket 除了用于冲突链的 next 指针外，还有 prev 和 next 用于维护一个全局双向链表。HashTable 结构中的 head 和 tail 分别指向链表的首尾。
当插入新元素时，它被追加到链表尾部；当删除元素时，它从链表中摘除。这样，无论哈希索引表如何变化，元素的插入顺序始终被保留。
PHP 的 foreach 遍历正是沿着这条双向链表进行的，因此遍历顺序就是元素的插入顺序。这也解释了为什么 PHP 数组被称为“有序哈希表”——它既有哈希表的快速查找，又有链表的顺序保证。
// 遍历示意
for (bucket = ht->head; bucket; bucket = bucket->next) {
// 按插入顺序访问每个元素
}
紧凑数组优化：packed array
在 PHP 7 之前，即使是一个纯整数索引的列表，也会使用完整的哈希表结构，造成内存浪费。PHP 7 引入了 packed array 优化：当数组的键是连续的整数（从 0 开始递增）时，HashTable 会切换为 packed 模式。
在 packed 模式下，不再需要哈希索引表和冲突链，元素直接按索引存储在 Bucket 数组中，查找退化为简单的数组下标访问。这大幅减少了内存占用并提升了缓存友好性。当插入非连续整数键或字符串键时，数组会自动转换为传统的 hash 模式。
写时复制与引用计数
PHP 数组赋值默认是写时复制（Copy-On-Write）。当 $a = $b 时，两个变量共享同一个 HashTable，只是引用计数加一。只有当其中一个变量发生修改时，才会真正复制一份新的 HashTable。
这一机制依赖于 zval 中的引用计数和 ZEND_ARRAY_ELEMENT 的分离标志。在遍历过程中，如果数组被修改，PHP 会通过 zend_hash_protect 等机制确保遍历的安全性，避免迭代器失效。
总结
PHP 内核的 HashTable 是一个兼顾性能与语义的经典设计。它通过链地址法处理冲突，通过 2 的幂次扩容和位运算优化查找，通过独立双向链表保证插入顺序，通过 packed array 优化纯列表场景，再配合写时复制降低内存开销。理解这套机制，不仅能帮助开发者写出更高效的 PHP 代码，也为阅读 Zend 引擎源码、理解 PHP 性能特性打下了坚实基础。
未经允许不得转载：任鹏个人博客 » PHP 内核数组 HashTable 实现原理：从哈希冲突到有序遍历的完整设计
