PHP 核心技術深度解析：Hash 表碰撞與鏈表法解決方案

PHP 底層 Hash 表碰撞原理與拉鏈法實作

PHP 陣列底層採用 Hash Table 實現。當不同鍵值經過雜湊函式計算出相同索引時，即發生「碰撞」。本文透過實際測試示範碰撞現象，並以「拉鏈法」完整實作解決方案。

碰撞現象演示

<?php
$ht = new HashTable();
$ht->insert('key1', 'value1');
$ht->insert('key12', 'value12'); // 與 key1 雜湊值相同（假設簡易演算法）

echo $ht->find('key1');  // 預期 value1，實際輸出 value12（被覆蓋）
echo $ht->find('key12'); // 輸出 value12
?>

原因：簡易雜湊函式將字串 ASCII 碼相加，key1 與 key12 皆得 8，導致同一索引位置被覆寫。

解決方案：拉鏈法

將相同雜湊值的節點串成鏈表，查找時遍歷鏈表比對原始鍵值。

1. 節點類別

<?php
class HashNode {
    public $key;
    public $value;
    public $nextNode;

    public function __construct($key, $value, $nextNode = null) {
        $this->key = $key;
        $this->value = $value;
        $this->nextNode = $nextNode;
    }
}
?>

2. 插入邏輯

public function insert($key, $value) {
    $index = $this->hashFunc($key);
    if (isset($this->buckets[$index])) {
        // 碰撞：新節點指向舊節點，成為新頭部
        $newNode = new HashNode($key, $value, $this->buckets[$index]);
    } else {
        $newNode = new HashNode($key, $value, null);
    }
    $this->buckets[$index] = $newNode;
}

3. 查找邏輯

public function find($key) {
    $index = $this->hashFunc($key);
    $current = $this->buckets[$index];
    while (isset($current)) {
        if ($current->key === $key) {
            return $current->value; // 找到
        }
        $current = $current->nextNode; // 遍歷下一節點
    }
    return null; // 未找到
}

演算法流程圖解

1. 插入：計算索引 → 檢查桶位 → 碰撞則新節點 nextNode 指向舊頭部 → 更新桶位指向新節點。
2. 查找：計算索引 → 遍歷鏈表 → 比對 key → 相等回傳 value → 遍歷結束回傳 null。

複雜度分析

良好的雜湊函式與負載因子控制（擴容）可維持平均 O(1)。

PHP 官方實現差異

• PHP 7+ 採用「開放定址法」結合「智慧型碰撞解決」，而非純拉鏈法。
• 使用 zend_ulong 整數雜湊，支援字串與整數鍵的混合儲存。
• 採用「遞增式擴容」，避免一次性重新雜湊大量資料造成延遲。

實戰建議

1. 鍵名盡量使用整數或定長字串，減少雜湊計算開銷。
2. 避免大量連續刪除導致「墓碑」堆積，必要時重建陣列。
3. 超大資料集考慮改用 Redis、Memcached 等外部儲存。