php数组的内部实现
PHP 数组的内部实现
PHP 的数组实际上是一个有序的哈希表（HashTable），它结合了链表和哈希表的特性，既能通过数字索引快速访问，也能通过字符串键名高效查找。
哈希表结构
PHP 数组的核心是 zend_array（也称为 HashTable）结构，包含以下关键部分：
- 桶（Buckets）：存储实际的键值对，每个桶包含键、值和哈希值。
- 哈希函数：将键名转换为哈希值，用于快速定位桶。
- 冲突解决：使用链表解决哈希冲突，即多个键名映射到同一哈希值的情况。
有序性实现
PHP 数组通过双向链表维护元素的插入顺序：
- 每个桶包含
pListNext和pListLast指针，指向链表中相邻的元素。 - 遍历数组时，按照链表顺序访问，而非哈希表的物理存储顺序。
内存优化
PHP 7 对数组进行了显著优化：
- 使用连续内存块存储整数索引的数组，类似 C 语言的普通数组。
- 对于混合类型键名的数组，仍使用哈希表实现。
- 减少了内存占用和 CPU 缓存未命中情况。
动态扩容
当数组元素数量超过当前容量时，PHP 会自动扩容：
- 容量通常按 2 的幂次增长（如 8, 16, 32）。
- 扩容时会重新哈希所有元素，并调整链表指针。
示例代码分析
以下代码展示了数组的内部行为：
$array = [];
$array['a'] = 1; // 哈希表插入
$array[0] = 2; // 可能使用连续内存存储
$array[] = 3; // 自动选择下一个整数索引性能特点
- 插入/删除：平均 O(1) 时间复杂度，最坏情况 O(n)（需遍历链表）。
- 查找：平均 O(1)，取决于哈希冲突程度。
- 迭代：O(n)，按插入顺序遍历所有元素。
与其它语言对比
- 不同于 Java 的
HashMap（无序），PHP 数组始终保持插入顺序。 - 不同于 JavaScript 的稀疏数组，PHP 会实际分配所有整数键的内存。
