哈希表(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 經哈希後落入同一槽位(衝突),後寫入直接覆蓋前值,導致數據丟失。
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;
}
}
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=鏈表長度 |
| 適用場景 | 教學演示 | 實際可用 |
n/m > 0.75 時自動擴容 2 倍並重新哈希。hash('xxh32', $key)。通過 SplFixedArray + 拉鏈法,我們在 PHP 用戶態代碼中實現了功能完整的哈希表。這不僅是數據結構教學的經典案例,更揭示了 PHP 內部陣列、Redis、Java HashMap 等高性能組件的共同設計哲學:以空間換時間,用鏈表/樹化解衝突。