哈希表：光速查找

演算法背後的故事：會瞬間移動的圖書館員

想像一個擁有 1000 萬本書的圖書館。在普通的圖書館（比如陣列或列表）中，妳必須走過每一個書架才能找到一本書。即使是在有序的圖書館（二分搜尋）中，妳仍需檢查 24 個書架。

1953 年，H.P. Luhn（同樣是哈希函數的鼻祖）提出了一種不同的圖書館方案。在這個圖書館裡，書名就是秘密地址。妳報出書名《了不起的蓋茨比》，套用一個魔術公式，它就會告訴妳：「在 429 號書架。」妳不需要走路，妳直接「瞬間移動」到了 429 號書架。

這就是 哈希表 (Hash Map)。它是現代軟體中最重要的基礎數據結構，因為它讓搜尋在實踐中變成了瞬時完成（$O(1)$ 時間）。

為什麼需要它？

如果妳用過 Python 的 dict、JavaScript 的 Object 或 Java 的 Map，妳就是在用哈希表。

• 資料庫索引： 資料庫如何在數十億記錄中找到妳？它使用哈希索引。
• 快取： 當妳想保存一個結果（如用戶資料）以便下次不用重新獲取時，妳會把它存入哈希表。
• 計數： 統計一本書中每個單詞出現的頻率。

演算法是如何「思考」的

這個演算法像是一個在鍵（Key）與記憶體之間牽線搭橋的媒人。

1. 公式 (哈希)： 它拿到妳的鍵（比如 “Luke”），透過哈希函數將其轉化為一個巨大的數字。
2. 地址 (壓縮)： 它將那個大數字縮小（通常使用取模 % 運算），以適配其內部儲存空間（陣列）的大小。
3. 儲存： 它將值（Value）放在那個特定的索引位置。
4. 化解衝突： 如果兩個不同的鍵（比如 “Luke” 和 “Sun”）算出了同一個索引怎麼辦？
   • 拉鏈法 (Chaining)： 在那個位置掛一個小列表，把兩人都放進去。
   • 開放尋址法： 在附近找下一個空位坐。

工程決策：負載因子

哈希表很快，但它是貪婪的記憶體消費者。

• 空間換時間： 為了保持高速，哈希表必須保持大部分空間是空的。如果表太滿（即「負載因子」過高），碰撞就會劇增，$O(1)$ 的速度會退化為 $O(N)$（也就是慢速列表的速度）。
• 擴容 (Resizing)： 當表裝到約 75% 時，它會觸發「擴容」——創建一個巨大的新倉庫，並重新計算每一個老住戶的地址。這是一個沈重的操作，所以如果我們預知數據規模，通常會提前分配足夠空間。

實作參考 (Python)

class SimpleHashMap:
    def __init__(self, size=100):
        self.size = size
        # 使用列表的列表來處理碰撞 (拉鏈法)
        self.table = [[] for _ in range(self.size)]

    def _hash(self, key):
        # Python 內建的 hash() 函數處理了底層的複雜工作
        return hash(key) % self.size

    def put(self, key, value):
        index = self._hash(key)
        # 如果鍵已存在，更新它；否則添加新項
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value))

    def get(self, key):
        index = self._hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        return None # 未找到

小結

哈希表教會我們：知識即位置。透過將問題的内容直接轉化為答案的地址，我們繞過了「搜尋」的必要。它提醒我們，在工程實踐中，有時候加速一個流程最簡單的方法就是多花一點錢在空間上。