您现在的位置：程式碼之家 >> 編程語言 > >> 網頁程式設計 >> PHP 程式設計 >> PHP 綜合知識

PHP 內核深度解析：HashTable 實現原理與 C 級代碼重構

編輯：PHP 綜合知識

為什麼要理解 HashTable？

PHP 中最核心的數據結構非陣列莫屬，而陣列的底層實現正是 HashTable（哈希表）。掌握其原理，能幫助你：

理解陣列操作的時間複雜度（O(1) 平均）
排查性能瓶頸（如哈希沖突導致退化）
編寫高性能擴展、優化內存佔用
深入理解 foreach、array_* 等函數行為

哈希表核心概念

術語	說明
Key（鍵）	數組索引，整數或字符串
Slot/Bucket（槽/桶）	存儲實際數據的容器單元
Hash Function（哈希函數）	將 Key 映射為槽索引的算法
Collision（沖突）	不同 Key 映射到同一索引
Load Factor（負載因子）	元素數/槽數，觸發擴容閾值

沖突解決：鏈地址法 vs 開放定址法

PHP 採用 鏈地址法：每個槽是一個鏈表頭，沖突元素掛在鏈表上。優點：實現簡單、支持動態擴容、刪除容易。缺點：極端情況退化為 O(n) 鏈表遍歷。

簡化版 HashTable C 實現（教學用）

數據結構定義

typedef struct _Bucket {
    char *key;           // 鍵（字符串）
    void *value;         // 值指針
    struct _Bucket *next; // 鏈表下一節點
} Bucket;

typedef struct _HashTable {
    int size;            // 槽數組大小
    int elem_num;        // 當前元素數
    Bucket **buckets;    // 槽數組（指針數組）
} HashTable;

哈希函數（簡化版）

static int hash_str(char *key) {
    int hash = 0;
    for (char *p = key; *p; p++) hash += *p; // 簡單累加
    return hash;
}
#define HASH_INDEX(ht, key) (hash_str(key) % (ht)->size)

生產級算法：PHP 實際使用 DJBX33A（Daniel J. Bernstein ×33 + Add），極快且分佈均勻：

static zend_ulong zend_inline_hash_func(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;
}

插入操作

int hash_insert(HashTable *ht, char *key, void *value) {
    // 1. 擴容檢查（負載因子 > 0.75 觸發 2x 擴容）
    if (ht->elem_num >= ht->size * 0.75) {
        resize_hash_table(ht);
    }
    
    int index = HASH_INDEX(ht, key);
    Bucket *head = ht->buckets[index];
    
    // 2. 檢查鍵是否已存在（更新值）
    for (Bucket *b = head; b; b = b->next) {
        if (strcmp(b->key, key) == 0) {
            b->value = value;
            return SUCCESS;
        }
    }
    
    // 3. 新建節點，頭插法
    Bucket *new = malloc(sizeof(Bucket));
    new->key = strdup(key);
    new->value = value;
    new->next = head;
    ht->buckets[index] = new;
    ht->elem_num++;
    return SUCCESS;
}

查找操作

int hash_lookup(HashTable *ht, char *key, void **result) {
    int index = HASH_INDEX(ht, key);
    for (Bucket *b = ht->buckets[index]; b; b = b->next) {
        if (strcmp(b->key, key) == 0) {
            *result = b->value;
            return SUCCESS;
        }
    }
    return FAILED; // 未找到
}

刪除操作

int hash_remove(HashTable *ht, char *key) {
    int index = HASH_INDEX(ht, key);
    Bucket **pp = &ht->buckets[index]; // 指向指針的指針
    while (*pp) {
        if (strcmp((*pp)->key, key) == 0) {
            Bucket *del = *pp;
            *pp = del->next; // 從鏈表移除
            free(del->key);
            free(del);
            ht->elem_num--;
            return SUCCESS;
        }
        pp = &(*pp)->next;
    }
    return FAILED;
}

PHP 內核實際結構：zend_array / HashTable

PHP 7+ 中，陣列即 zend_array，繼承自 HashTable，關鍵字段：

struct _zend_array {
    zend_refcounted_h gc;      // 引用計數、GC 信息
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar flags,     // 标志位：packed/有序/不可變等
                zend_uchar nApplyCount,
                zend_uchar nIteratorsCount,
                zend_uchar consistency
            )
        } v;
        uint32_t flags;
    } u;
    uint32_t nTableMask;       // 索引掩碼 = -(nTableSize) 用于位運算取模
    Bucket *arData;            // 連續內存數組（Bucket*），而非指針數組
    uint32_t nNumUsed;         // 已用槽數（含已刪除）
    uint32_t nNumOfElements;   // 實際元素數
    uint32_t nTableSize;       // 槽總數（2 的冪）
    uint32_t nInternalPointer; // 內部指針（foreach 用）
    zend_long nNextFreeElement; // 下一個整數鍵
    dtor_func_t pDestructor;   // 值析構函數
};

關鍵優化：Compact 數組

PHP 7 引入 Packed Array（緊湊陣列）：當鍵為連續整數 0..n-1 時，不使用哈希映射，直接按索引存取 arData[index]，極大提升性能與內存局部性。一旦出現字符串鍵或非連續整數，自動轉為哈希模式。

有序性維護：雙向鏈表

PHP 陣列保持插入順序，Bucket 額外包含：

typedef struct _Bucket {
    zval val;                // 值（直接內嵌，不再指針）
    zend_ulong h;            // 哈希值（整數鍵為鍵值，字符串鍵為哈希）
    zend_string *key;        // 字符串鍵指針（整數鍵為 NULL）
    // 以下維護順序：
    uint32_t nNext;          // 下一元素索引
    uint32_t nPrev;          // 上一元素索引
} Bucket;

arData 為連續內存，nNext/nPrev 形成雙向鏈表，實現 O(1) 順序遍歷。

擴容機制

初始大小 8（2³）
負載因子超過 0.75 觸發 2x 擴容（2 的冪）
重新計算所有元素哈希，重建 nTableMask、arData
擴容時保持順序鏈表不變，只重新映射槽位置

實際性能測試

<?php
$n = 100000;
// 緊湊陣列
$packed = range(1, $n);
$start = microtime(true);
foreach ($packed as $v) $sum += $v;
echo "Packed 遍歷: " . (microtime(true) - $start) . "s\n";

// 哈希陣列
$hash = [];
for ($i = 0; $i < $n; $i++) $hash["key$i"] = $i;
$start = microtime(true);
foreach ($hash as $v) $sum += $v;
echo "Hash 遍歷: " . (microtime(true) - $start) . "s\n";

// 輸出典型：
// Packed 遍歷: 0.004s
// Hash 遍歷: 0.006s
?>