PHP 內核深度探秘（二）：哈希表 實現原理與遍歷優化

PHP 數組的靈魂是 有序哈希表。它既支持整數/字符串鍵混合、保持插入順序，又提供 O(1) 平均查找/插入/刪除。本文基於 PHP 7/8 源碼，解析 zend_array、Bucket、哈希函數 (DJBX33A)、沖突解決 (開放寻址法)、擴容縮容、遍歷機制、內存佈局優化。

核心數據結構

// Bucket: 哈希表節點
struct _Bucket {
    zval              val;        // 值 (內嵌 zval，PHP 7 優化)
    zend_ulong        h;          // 哈希值 (整數鍵直接用值，字符串鍵預計算)
    zend_string      *key;        // 字符串鍵指針 (整數鍵為 null)
};

// zend_array: 哈希表容器
struct _zend_array {
    zend_refcounted_h gc;
    uint32_t          nTableMask;  // = ~(nTableSize - 1)，用於索引計算: idx = h & nTableMask
    Bucket           *arData;      // 連續內存數組，存儲所有 Bucket
    uint32_t          nNumUsed;    // 已用 Bucket 數 (含已刪除標記)
    uint32_t          nNumOfElements; // 實際有效元素數
    uint32_t          nTableSize;  // arData 分配大小 (2 的冪次)
    uint32_t          nInternalPointer; // 內部指針 (current/next/prev)
    zend_long         nNextFreeElement; // 下一個可用整數鍵
    dtor_func_t       pDestructor; // 元素析構函數
};

關鍵設計亮點

1. 連續內存 Bucket 數組： arData 為連續分配的 Bucket 數組，非鏈表。CPU 緩存友好，遍歷極快 (線性掃描)。
2. 開放寻址法解決沖突： 索引 idx = h & nTableMask。沖突時線性探測 idx = (idx + 1) & nTableMask 直到空槽。無鏈表指針開銷，查找路徑短。
3. 有序性維護： arData 按插入順序排列。nInternalPointer 指向當前遍歷位置。foreach 直接線性掃描 arData，跳過 IS_UNDEF (已刪除標記)。
4. 整數鍵優化： 整數鍵直接作為哈希值 h，key = null，節省 zend_string 分配。
5. 擴容策略： 裝載因子 > 0.75 觸發 2 倍擴容。重新計算所有元素索引並搬移 (rehash)。nTableMask 同步更新。
6. 縮容策略： 刪除後 nNumOfElements < nTableSize / 4 觸發 1/2 縮容 (避免頻繁擴縮容滯後)。
7. 打包優化： 純整數鍵、連續、從 0 開始的數組標記 IS_ARRAY_PACKED，迭代直接按索引訪問 arData[i]，無需哈希計算。

哈希函數：DJBX33A

// 源碼: Zend/zend_string.h
static zend_always_inline zend_ulong zend_string_hash_val(const char *str, size_t len) {
    zend_ulong hash = 5381;
    for (size_t i = 0; i < len; i++) {
        hash = ((hash << 5) + hash) + (zend_ulong)str[i]; // hash * 33 + c
    }
    return hash;
}

經典字符串哈希，分佈均勻、計算極快。PHP 7 在 zend_string 創建時預計算並緩存 h，避免重複計算。

插入/查找/刪除流程

插入 zend_hash_add/zend_hash_update

1. 檢查是否需擴容 (nNumUsed >= nTableSize * 0.75)。
2. 計算索引 idx = h & nTableMask。
3. 線性探測找空槽 (Z_TYPE(arData[idx].val) == IS_UNDEF)。
4. 寫入 Bucket: val (zval)、h、key (字符串鍵需 zend_string_copy 增引用計數)。
5. nNumUsed++, nNumOfElements++。
6. 若整數鍵且 key == null 且 h >= nNextFreeElement，更新 nNextFreeElement = h + 1。

查找 zend_hash_find

1. 計算索引 idx = h & nTableMask。
2. 線性探測：比較 h 相等且 key 相等 (字符串鍵用 zend_string_equals)。
3. 找到返回 &arData[idx].val，否則返回 null。

刪除 zend_hash_del

1. 查找到目標 Bucket。
2. 調用析構函數釋放 val (zval_ptr_dtor) 和 key (zend_string_release)。
3. 標記 Z_TYPE(val) = IS_UNDEF (墓碑標記，不實際移動後續元素，保持探測鏈完整)。
4. nNumOfElements--。檢查縮容條件。

遍歷機制：foreach 內核實現

// 內部指針遍歷
ZEND_HASH_FOREACH_VAL(ht, val) {
    // val 為 zval*
} ZEND_HASH_FOREACH_END();

// 或帶鍵
ZEND_HASH_FOREACH_KEY_VAL(ht, h, key, val) {
    // h: 整數鍵, key: zend_string*, val: zval*
} ZEND_HASH_FOREACH_END();

實質是線性掃描 arData[0] ... arData[nNumUsed-1]，跳過 IS_UNDEF。修改數組長度 (增刪) 會導致重置內部指針，foreach 行為未定義 —— 這就是為什麼不能在 foreach 中增刪當前數組。

性能啟示與最佳實踐

總結

PHP 哈希表 = 連續 Bucket 數組 + 開放寻址法 + 插入順序維護 + 打包優化。這種設計在「動態鍵值存儲」與「有序遍歷」雙重需求下取得了極佳平衡，是 PHP 數組性能強悍的根本原因。理解其內核機制，能指導你寫出更高效的數組操作代碼。