php的数组实现

PHP 数组的实现原理

PHP 的数组是一种混合数据结构，结合了哈希表（Hash Table）和有序链表（Ordered List）的特性。底层使用哈希表存储元素，同时通过链表维护插入顺序。

哈希表结构

PHP 数组的核心是 zend_array（或称 HashTable），其关键组成部分包括：

• 桶（Bucket）数组：存储实际数据的连续内存空间，每个桶包含键、值和哈希值。
• 哈希函数：将键转换为哈希值，用于确定桶的位置。
• 冲突解决：采用链地址法（拉链法），哈希冲突时通过链表连接。

有序性维护

PHP 数组通过双向链表维护元素插入顺序：

• 每个桶包含 pListNext 和 pListLast 指针，指向链表中相邻元素。
• 新元素插入时追加到链表尾部，保证 foreach 遍历顺序与插入顺序一致。

动态扩容机制

当数组容量不足时，PHP 会自动扩容：

1. 计算新容量（通常为当前容量的 2 倍）。
2. 分配新的桶数组，并重新哈希所有元素。
3. 迁移数据到新桶数组，保持原有顺序。

内存优化

PHP 8 引入了 packed array 优化：

• 当数组使用连续数字键（如 [0 => 'a', 1 => 'b']）时，直接使用紧凑的 C 数组存储，跳过哈希表开销。
• 一旦插入非数字键或非连续键，自动转换为普通哈希表。

示例代码分析

$array = [
    'foo' => 'bar',
    42    => 'answer',
    'nested' => ['a', 'b']
];

1. 哈希表会为 'foo' 和 42 分配不同桶。
2. 链表按 'foo' → 42 → 'nested' 顺序连接。
3. 'nested' 的值是另一个独立数组结构。

性能特征

• 插入/删除：平均 O(1) 时间复杂度，最坏情况 O(n)（哈希冲突或扩容时）。
• 遍历：O(n) 时间复杂度，按插入顺序进行。
• 查找：平均 O(1)，依赖哈希函数效率。