萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 網路程式設計 >> PHP 程式設計

PHP 實現哈希表:從簡單數組到拉鏈法解決衝突的完整演進

哈希表基礎回顧

哈希表(Hash Table,又稱散列表)是實現 鍵值映射 的核心數據結構,通過哈希函數將任意 Key 映射到固定範圍的數組下標,實現平均 O(1) 的增刪改查。PHP 內部的陣列本質就是有序哈希表,但手寫實現有助於理解底層原理。

版本一:簡單數組 + 取模哈希(衝突直接覆蓋)

<?php
class SimpleHashTable {
    private $arr;
    private $size = 10;

    public function __construct() {
        // SplFixedArray 內存更緊湊、速度更快,類似 C 陣列
        $this->arr = new SplFixedArray($this->size);
    }

    private function simpleHash(string $key): int {
        $sum = 0;
        for ($i = 0, $len = strlen($key); $i < $len; $i++) {
            $sum += ord($key[$i]);
        }
        return $sum % $this->size;
    }

    public function set(string $key, mixed $value): bool {
        $this->arr[$this->simpleHash($key)] = $value;
        return true;
    }

    public function get(string $key): mixed {
        return $this->arr[$this->simpleHash($key)];
    }

    public function getList(): SplFixedArray {
        return $this->arr;
    }

    public function resize(int $size): void {
        $this->size = $size;
        $this->arr->setSize($size);
    }
}

測試與缺陷

$ht = new SimpleHashTable();
for ($i = 0; $i < 15; $i++) {
    $ht->set("key$i", "value$i");
}
print_r($ht->getList());
// 輸出:key3、key13 衝突導致 value3 被 value13 覆蓋

問題:不同 Key 經哈希後落入同一槽位(衝突),後寫入直接覆蓋前值,導致數據丟失。

版本二:拉鏈法解決衝突(鏈表存儲同桶元素)

1. 節點類

class HashNode {
    public string $key;
    public mixed $value;
    public ?HashNode $nextNode;

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

2. 改進後的哈希表

class ChainedHashTable {
    private SplFixedArray $buckets;
    private int $size = 10;

    public function __construct() {
        $this->buckets = new SplFixedArray($this->size);
    }

    private function hash(string $key): int {
        $sum = 0;
        for ($i = 0, $len = strlen($key); $i < $len; $i++) {
            $sum += ord($key[$i]);
        }
        return $sum % $this->size;
    }

    public function set(string $key, mixed $value): bool {
        $idx = $this->hash($key);
        // 頭插法:新節點指向原鏈表頭
        $this->buckets[$idx] = new HashNode($key, $value, $this->buckets[$idx]);
        return true;
    }

    public function get(string $key): mixed {
        $idx = $this->hash($key);
        $curr = $this->buckets[$idx];
        while ($curr !== null) {
            if ($curr->key === $key) {
                return $curr->value;
            }
            $curr = $curr->nextNode;
        }
        return null;
    }

    public function getList(): SplFixedArray {
        return $this->buckets;
    }
}

測試驗證

$ht = new ChainedHashTable();
for ($i = 0; $i < 30; $i++) {
    $ht->set("key$i", "value$i");
}

var_dump($ht->get('key3')); // 正確輸出 string(6) "value3"
print_r($ht->getList());    // 每個桶指向一個 HashNode 鏈表

輸出結構示意:

SplFixedArray Object
(
    [0] => HashNode Object ( [key]=>key23 [value]=>value23 [nextNode]=>HashNode Object ( [key]=>key14 ... ) )
    [1] => HashNode Object ( [key]=>key24 [value]=>value24 [nextNode]=>HashNode Object ( [key]=>key15 ... ) )
    ...
)

性能分析與優化方向

指標簡單數組版拉鏈法版
空間複雜度O(m) m=桶數O(n+m) n=元素數
查找最好O(1)O(1)
查找最壞O(1) 但數據丟失O(k) k=鏈表長度
適用場景教學演示實際可用

工程化優化建議

  1. 動態擴容:負載因子 n/m > 0.75 時自動擴容 2 倍並重新哈希。
  2. 優化哈希函數:採用 FNV-1a、MurmurHash 或 PHP 內建 hash('xxh32', $key)。
  3. 紅黑樹轉換:鏈表長度超過閾值(如 8)轉為紅黑樹,將最壞查找降為 O(log k)(Java 8 HashMap 策略)。
  4. 避免對象開銷:高性能場景可用兩個平行數組存儲 key/value,或使用 C 擴展(PHP 內建 array 已高度優化)。

總結

通過 SplFixedArray + 拉鏈法,我們在 PHP 用戶態代碼中實現了功能完整的哈希表。這不僅是數據結構教學的經典案例,更揭示了 PHP 內部陣列、Redis、Java HashMap 等高性能組件的共同設計哲學:以空間換時間,用鏈表/樹化解衝突。

copyright © 萬盛學電腦網 all rights reserved