PHP 內核探秘：數組底層哈希表實現原理深度解析

編輯：關於C語言

核心觀點：一切皆哈希表

PHP 內部大量使用哈希表：數組、對象屬性、函數表、符號表、變量作用域等均基於同一套 HashTable 實現。理解其結構是掌握 PHP 內核的關鍵。

哈希表基礎

C 語言原生數組僅支持整數下標。哈希表通過哈希函數將任意字符串鍵映射為整數桶索引，解決關聯數組需求。衝突通過**鏈地址法**處理：每個桶指向 Bucket 鏈表。

核心結構體

HashTable

typedef struct _hashtable {
    uint nTableSize;        // 桶數組大小（2的冪）
    uint nTableMask;        // nTableSize - 1，用於哈希值取模
    uint nNumOfElements;    // 當前元素數量，count() 直接返回
    ulong nNextFreeElement; // 下一個可用數字索引
    Bucket *pInternalPointer; // 內部指針，支撐 current/next/prev 等
    Bucket *pListHead;      // 雙向鏈表頭，維護插入順序
    Bucket *pListTail;      // 雙向鏈表尾
    Bucket **arBuckets;     // 桶數組（指針數組）
    dtor_func_t pDestructor; // 值析構函數（如 zval_ptr_dtor）
    zend_bool persistent;   // 是否跨請求持久化
    // ... 調試/保護字段
} HashTable;

Bucket

typedef struct bucket {
    ulong h;                // 原始哈希值（未掩碼）
    uint nKeyLength;        // 字符串鍵長度
    void *pData;            // 值指針（通常指向 zval）
    void *pDataPtr;         // 直接嵌入值（優化小數據）
    struct bucket *pListNext; // 全局雙向鏈表 next
    struct bucket *pListLast; // 全局雙向鏈表 prev
    struct bucket *pNext;   // 同桶衝突鏈表 next
    struct bucket *pLast;   // 同桶衝突鏈表 prev
    const char *arKey;      // 字符串鍵（數字鍵時為 NULL）
} Bucket;

關鍵機制

1. 擴容策略

nTableSize 總是 2 的冪，且 ≥ nNumOfElements。插入導致負載因子超標時，擴容為 2 倍，重新計算所有鍵的桶索引（h & nTableMask）。

2. 數字鍵與字符串鍵統一

數字鍵直接存儲在 h，arKey=NULL、nKeyLength=0。字符串鍵存儲在 arKey，h 為其哈希值。

3. 符號表特殊語義

zend_symtable_update 將數字字符串鍵（如 "123"）自動轉為數字鍵 123，實現 $arr["123"] 與 $arr[123] 互通。對象屬性轉數組時若屬性名為數字字符串，會產生「隱藏元素」（無法用數字/字符串下標訪問）。

4. 遍歷順序

PHP 數組是**有序映射**：pListHead/pListTail 維護插入順序雙向鏈表，foreach、reset/next/prev/end 均基於此鏈表，而非桶數組順序。

實例：`array_fill_keys` 實現剖析

// 1. 解析參數：keys 數組、val 值
// 2. 初始化返回數組，預分配大小 = zend_hash_num_elements(keys)
// 3. 遍歷 keys：
//    zend_hash_internal_pointer_reset_ex(keys, &pos);
//    while (zend_hash_get_current_data_ex(keys, &entry, &pos) == SUCCESS) {
//        if (Z_TYPE_PP(entry) == IS_LONG) { // 數字鍵
//            zval_add_ref(&val);
//            zend_hash_index_update(return_value, Z_LVAL_PP(entry), &val, ...);
//        } else { // 字符串鍵
//            zval key = **entry; zval_copy_ctor(&key);
//            convert_to_string(&key); // 強制轉字符串
//            zval_add_ref(&val);
//            zend_symtable_update(return_value, Z_STRVAL_P(key), Z_STRLEN_P(key)+1, &val, ...);
//            if (key != *entry) zval_dtor(&key); // 銷毀臨時副本
//        }
//        zend_hash_move_forward_ex(keys, &pos);
//    }

關鍵點：預分配優化、數字/字符串鍵分支、符號表語義、引用計數管理（zval_add_ref/zval_dtor vs zval_ptr_dtor）。