PHP 內核中陣列的 HashTable 實現原理

核心結構

PHP 陣列在 Zend Engine 中以 HashTable 實現，結合雙向鏈表維持插入順序，支援 O(1) 存取、遍歷、插入、刪除。

關鍵資料結構 (簡化)

typedef struct _zval_struct {
    zvalue_value value;  // 聯合體：long, double, str, ht, obj, res, ref
    zend_uint refcount__gc;
    zend_uchar type;     // IS_ARRAY, IS_STRING, IS_LONG...
    zend_uchar is_ref__gc;
} zval;

typedef struct bucket {
    ulong h;             // 數字鍵雜湊值 或 字串鍵雜湊
    uint nKeyLength;     // 0=數字鍵, >0=字串鍵長度(+1 含結尾\0)
    void *pData;         // 指向 zval*
    void *pDataPtr;      // 直接指向資料 (優化)
    struct bucket *pListNext, *pListLast;  // 全域插入順序鏈表
    struct bucket *pNext, *pLast;          // 同雜湊桶鏈表
    char arKey[1];       // 字串鍵名 (柔性陣列)
} Bucket;

typedef struct _hashtable {
    uint nTableSize;     // 雜湊桶數量 (2 的冪)
    uint nTableMask;     // nTableSize - 1
    uint nNumOfElements; // 元素數量
    ulong nNextFreeElement; // 下一個自動數字索引
    Bucket *pInternalPointer; // 遍歷指標
    Bucket *pListHead, *pListTail; // 插入順序鏈表頭尾
    Bucket **arBuckets;  // 雜湊桶陣列
    dtor_func_t pDestructor; // 元素銷毀回呼
    zend_bool persistent; // 是否持久化
    unsigned char nApplyCount; // 遞迴保護
    zend_bool bApplyProtection;
} HashTable;

陣列建立與操作巨集 (Zend API)

// 建立空陣列
zval *arr;
ALLOC_INIT_ZVAL(arr);
array_init(arr); // 等同於 Z_TYPE_P(arr)=IS_ARRAY; zend_hash_init(...)

// 關聯陣列新增
add_assoc_long(arr, "key", 123);
add_assoc_string(arr, "name", "value", 1); // 1=複製字串

// 數字索引新增
add_index_long(arr, 0, 456);

// 追加 (自動索引)
add_next_index_string(arr, "auto", 1);

// 子陣列
zval *sub; ALLOC_INIT_ZVAL(sub); array_init(sub);
add_next_index_string(sub, "child", 1);
add_assoc_zval(arr, "sub", sub);

PHP 代碼對應內核操作對照表

效能特性

• 查找/插入/刪除：平均 O(1)，最壞 O(n) (雜湊衝突極多)
• 記憶體：每個元素 ~48-72 bytes (64 位系統)，含 Bucket、zval、字串鍵
• 擴容：負載因子超過閾值 → 重新雜湊 (rehash)，桶數量翻倍
• 有序性：嚴格保持插入順序 (雙向鏈表)
• Copy-on-Write：參考計數機制，寫入時才複製

PHP 7/8 優化 (zend_array)

• 陣列結構從 HashTable 獨立為 zend_array，內嵌 HashTable 欄位
• 壓縮指標 (32 位偏移量替代 64 位指標) 節省記憶體 ~50%
• 整數鍵專用儲存，避免字串鍵分配
• Immortal arrays (靜態陣列) 無參考計數開銷
• Preloading / OpCache 共享陣列跨請求

除錯技巧

// gdb 中檢查陣列
print *arr
print *(HashTable*)arr->value.ht
// 遍歷桶
set $bucket = ((HashTable*)arr->value.ht)->pListHead
while ($bucket) {
    print $bucket->arKey
    print *(zval*)$bucket->pData
    set $bucket = $bucket->pListNext
}