4.3 雜湊表的應用實例#

概念說明#

雜湊表最常見的用法可以歸納成幾個模式：

集合判斷：「看過沒有？存在嗎？」——用 set/dict 做 O(1) 成員測試，取代巢狀迴圈。
計數統計：鍵是項目、值是次數，一次掃描完成統計。
索引對映：把資料的某個屬性（編號、名稱）映射到完整記錄，形成「目錄」。
快取 / 記憶化：把已算過的答案存起來，重複查詢直接命中。
分組：把資料依某鍵分類，值可以是串列。

以下用三個完整例子示範。

例一：兩數之和（經典面試題）#

在陣列中找兩個數使其和為 target。暴力法 O(n²)；用雜湊表「一邊掃、一邊查需要的另一半」可達 O(n)。

def two_sum(nums, target):
    seen = {}                       # 值 -> 索引
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:            # 之前看過的數裡有需要的嗎？
            return [seen[need], i]
        seen[x] = i
    return None

print(two_sum([2, 7, 11, 15], 9))    # [0, 1]
print(two_sum([3, 2, 4], 6))         # [1, 2]

例二：字詞頻率統計#

from collections import Counter, defaultdict

text = """資料結構是程式設計的基礎 學好資料結構 演算法自然水到渠成
資料結構與演算法相輔相成 程式設計需要資料結構"""

words = text.split()
counter = Counter(words)                    # 一行完成計數
print(counter.most_common(3))               # 出現最多的前三名

# 等價的手作版本（defaultdict：缺鍵自動建立預設值）
manual = defaultdict(int)
for w in words:
    manual[w] += 1
print(dict(manual) == dict(counter))        # True

# 依「字首」分組
groups = defaultdict(list)
for w in words:
    groups[w[0]].append(w)
print(dict(groups))

例三：記憶化——爬樓梯問題#

爬 n 階樓梯，每次走 1 或 2 階，共有幾種走法？遞迴是費氏數列，裸版是 O(2ⁿ)；用雜湊表快取子問題答案後變 O(n)。

from functools import lru_cache

def climb_plain(n):                     # O(2^n)，n=35 就明顯變慢
    if n <= 2:
        return n
    return climb_plain(n - 1) + climb_plain(n - 2)

memo = {}
def climb_memo(n):                      # O(n)
    if n <= 2:
        return n
    if n not in memo:
        memo[n] = climb_memo(n - 1) + climb_memo(n - 2)
    return memo[n]

@lru_cache(maxsize=None)                # 標準庫內建的自動記憶化
def climb_lru(n):
    if n <= 2:
        return n
    return climb_lru(n - 1) + climb_lru(n - 2)

import time
t = time.perf_counter(); climb_plain(30); t1 = time.perf_counter() - t
t = time.perf_counter(); climb_memo(30);  t2 = time.perf_counter() - t
print(f"裸遞迴 {t1:.4f} 秒 / 記憶化 {t2:.6f} 秒")

複雜度分析#

以上三例的核心操作都是「平均 O(1) 的鍵值查詢」，讓整體複雜度從 O(n²) 或 O(2ⁿ) 降到 O(n)。代價是額外 O(n) 空間與雜湊計算成本；最壞情況（碰撞嚴重）仍可能退化，因此關鍵的雜湊鍵要分布均勻。

練習#

修改 two_sum 回傳所有不重複的配對（如 [3, 3] 為 target 6 的合法解），維持 O(n)。
用 Counter 統計一篇文章的字母頻率，畫出長條圖（用字元 █ 重複列印即可）。
為 climb_memo 加上「一次可走 1、2、3 階」的規則，比較記憶化前後在 n=25 時的執行時間。