当前位置：首页 > PHP

php array底层实现

2026-02-15 16:48:12PHP

PHP 数组的底层实现

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

哈希表结构

PHP 数组的核心是哈希表（zend_array 或 HashTable），通过哈希函数将键（数字或字符串）映射到存储位置。哈希表解决冲突的方式是链地址法（每个桶用链表存储冲突的条目）。

哈希函数：将字符串键转换为哈希值，数字键直接使用。
桶（Bucket）：存储键值对，包含键、值、哈希值和指向链表中相邻元素的指针。

有序性实现

PHP 数组的遍历顺序与插入顺序一致，这是通过双向链表实现的。每个桶包含 pListNext 和 pListLast 指针，维护插入顺序的链表。

动态扩容

哈希表会根据元素数量动态调整容量（通常为 2 的幂次方），触发扩容时重新哈希所有元素。

内存优化

PHP 会对纯数字索引数组（如 [0 => 'a', 1 => 'b']）进行优化，直接使用连续内存存储（类似 C 数组），无需哈希表。

示例代码分析

$arr = [
    "foo" => "bar",
    42    => "answer",
];

字符串键 "foo" 通过哈希函数计算哈希值，存入哈希表。
数字键 42 直接作为索引处理。
双向链表维护 "foo" 和 42 的插入顺序。

性能特点

查找/插入/删除：平均时间复杂度 O(1)，最坏情况 O(n)（哈希冲突严重时）。
遍历：时间复杂度 O(n)，顺序与插入顺序一致。
内存占用：高于纯索引数组（如 C 数组），因需存储哈希表和链表结构。

内部结构（简化）

struct _zend_array {
    Bucket       *arData;       // 存储桶的数组
    uint32_t      nTableSize;   // 哈希表大小
    uint32_t      nNumUsed;     // 已用桶数
    uint32_t      nNumOfElements; // 有效元素数
    uint32_t      nTableMask;   // 哈希掩码（nTableSize - 1）
    uint32_t      nInternalPointer; // 遍历指针
    zend_long     nNextFreeElement; // 下一个数字键值
    Bucket       *pListHead;    // 链表头
    Bucket       *pListTail;    // 链表尾
};