php array 底层实现

PHP 数组的底层实现

PHP 数组是一种混合数据结构，既支持数字索引也支持字符串键（关联数组）。其底层实现基于哈希表（HashTable）和双向链表的结合体，称为有序哈希表（Ordered Hash Table）。

哈希表（HashTable）结构

PHP 数组的核心是哈希表，通过哈希函数将键（无论是数字还是字符串）映射到存储位置。哈希表解决了快速查找的问题，平均时间复杂度为 O(1)。

• Bucket（桶）：存储键值对的结构体，包含：
  • 键（数字或字符串的哈希值）
  • 值（zval，PHP 变量的通用结构）
  • 指向下一个桶的指针（解决哈希冲突）

双向链表维护顺序

PHP 数组的元素顺序是插入顺序，通过双向链表实现：

• 每个 Bucket 包含 pListNext 和 pListLast 指针，分别指向下一个和上一个元素。
• 哈希表头部的 pListHead 和 pListTail 分别指向链表的首尾。

动态扩容机制

哈希表会根据元素数量动态调整大小：

• 初始容量为 8（PHP 7+），当元素数量超过当前容量的阈值时（如负载因子 0.5），触发扩容。
• 扩容时容量翻倍，重新哈希所有元素到新桶中。

内存优化（PHP 7+）

PHP 7 对数组进行了显著优化：

• 打包数组（Packed Array）：当数组使用连续数字索引（0,1,2...）时，直接按顺序存储值，无需哈希表。
• 内存局部性：减少间接指针访问，提升缓存命中率。

示例代码分析

$arr = ['a' => 1, 2 => 'b'];

• 键 'a' 通过哈希函数计算位置，存储到 Bucket。
• 数字键 2 直接作为索引处理（若连续则可能用打包数组）。
• 双向链表记录插入顺序为 'a' → 2。

性能特点

• 查找：平均 O(1)，最坏 O(n)（哈希冲突时）。
• 插入/删除：平均 O(1)，需维护链表指针。
• 遍历：O(n)，按插入顺序通过链表遍历。

与其它语言对比

• 不同于 C 的纯连续内存数组或 Java 的 HashMap（无序）。
• 类似 Python 的 dict（但 Python 3.7+ 才保证顺序）。