PHP 核心 HashTable 實現原理深度解析

HashTable 是 PHP 內核的「心臟」——陣列、變量符號表、類屬性、函數表、常量表、資源列表……無一不建立在 HashTable 之上。理解其結構與 API，是進階 PHP 開發者、擴展作者、性能調優者的必修課。本文從數據結構、核心 API、衝突解決、遍歷機制四個維度系統梳理。

一、數據結構全景

1. 四大核心組件

• 哈希函數：PHP 使用 DJBX33A (times33) 演算法，將字串 Key 映射為整數：hash = hash * 33 + char，速度極快、分佈均勻。
• Bucket 桶：存儲實際數據的結構體，包含 key、h (預計算哈希值)、val (指向 zval)、next/prev (同桶鏈表指針)。
• 雙向鏈表（桶內）：解決哈希衝突，同一索引下的多個 Bucket 組成鏈表（分離鏈接法）。
• 雙向鏈表（全局）：將所有 Bucket 按插入順序串聯，支援 foreach、reset/next/prev/end 等順序遍歷，也是「陣列有序」的根本原因。

2. 關鍵結構體（簡化版）

typedef struct _Bucket {
    ulong        h;            // 數字鍵或字串鍵哈希值
    uint         nKeyLength;   // 鍵長度，0 表示數字鍵
    void        *pData;        // 指向值 (zval*)
    void        *pDataPtr;     // 指針值 (IS_PTR)
    struct _Bucket *pListNext; // 全局鏈表 next
    struct _Bucket *pListLast; // 全局鏈表 prev
    struct _Bucket *pNext;     // 衝突鏈表 next
    struct _Bucket *pLast;     // 衝突鏈表 prev
    char         arKey[1];     // 柔性數組存鍵名
} Bucket;

typedef struct _hashtable {
    uint         nTableSize;   // 桶數組大小 (2 的冪)
    uint         nTableMask;   // nTableSize - 1，用於索引計算
    uint         nNumOfElements; // 當前元素數
    ulong        nNextFreeElement; // 下一個可用數字索引
    Bucket      *pInternalPointer; // 內部指針 (foreach 用)
    Bucket      *pListHead;    // 全局鏈表頭
    Bucket      *pListTail;    // 全局鏈表尾
    Bucket     **arBuckets;    // 桶指針數組 (Bucket**)
    dtor_func_t  pDestructor;  // 元素銷毀回調
    zend_bool    persistent;   // 是否持久化 (共享內存)
    unsigned char nApplyCount; // 遞歸保護計數
    zend_bool    bApplyProtection;
} HashTable;

二、核心 API 分類速查 (zend_hash.h)

三、關鍵機制深度剖析

1. 索引計算與擴容

// 索引 = h & nTableMask  (等價 h % nTableSize，但位運算更快)
index = p->h & ht->nTableMask;

• 初始大小默認 8，負載因子超過閾值（通常 1.0）觸發 zend_hash_do_resize 擴容（2倍）。
• 擴容需重新計算所有 Bucket 索引（Rehash），O(n) 操作，頻繁插入大量數據時建議預先 zend_hash_init(ht, estimated_size, ...)。

2. 衝突解決：分離鏈接 + 全局有序鏈表

雙鏈表設計 同時滿足：

1. O(1) 平均查找/插入/刪除（桶內鏈表）
2. O(1) 維護插入順序遍歷（全局鏈表）

這就是為什麼 PHP 陣列「既是哈希表又是有序列表」的根本原因。

3. 數字鍵自動重建索引

• 插入數字鍵時，若 key >= nNextFreeElement，自動更新 nNextFreeElement = key + 1。
• zend_hash_next_free_element() 返回下一個可用數字索引，支援 $arr[] = value 語法。

4. 遞歸保護

nApplyCount 防止 zend_hash_apply 回調中修改同一 HashTable 導致無限遞歸，超過限制直接報錯。

四、從 C 到 PHP 的映射關係

五、實戰啟示

1. 大陣列預分配：$arr = []; for($i=0;$i<100000;$i++) $arr[$i]=$i; 會觸發多次 Rehash，改用 $arr = array_fill(0, 100000, null); 或 SplFixedArray 可顯著提速。
2. foreach 引用陷阱：foreach($arr as &$v) 會將內部指針鎖定，循環結束後 $v 仍指向最後元素，後續操作易出 Bug，習慣 unset($v)。
3. 陣列合併性能：+ 運算符保留鍵不覆蓋，array_merge 重建數字鍵，大數據量選擇正確 API 關鍵。
4. 擴展開發：自定義資料結構直接操作 HashTable*，需嚴格遵循持久化標誌、銷毀回調、遞歸保護規範。

推薦閱讀

• PHP 源碼：Zend/zend_hash.c、Zend/zend_hash.h
• 鳥哥博客：《深入理解 PHP 之陣列 (遍歷順序)》、《PHP 內核探索：HashTable》
• 《PHP 7 內核剖析》第 3 章：HashTable 重構 (Packed Array、Immutable Array)

1. 上一篇文章： PHP 實現 ZIP 文件在線解壓功能
2. 下一篇文章： PHP 根據日期計算星座函數（精準邊界處理）

PHP 相關知識

PHPExcel 導出 Excel 完整教程：從建立工作表、填充資料到瀏覽器下載

前言 PHPExcel（現已併入 PhpSpreadshee

PHPExcel 多工作表上傳與下載完整實作

PHPExcel 多工作表上傳與下載完整實作 資料庫三張表：

《增加反向鏈接的 101 個方法》中文版 PDF 下載 —— 經典 SEO 鏈接誘餌案例

SEO 領域的經典之作《增加反向鏈接的 101 個方法》（1

PHP 5 物件導向圖形庫建構：從基本繪圖到可擴展渲染引擎

設計目標：超越過程式繪圖 API PHP 內建 GD 函數（