4.1 雜湊函數設計#

概念說明#

雜湊函數 h(key) 把鍵映射成陣列索引。好的雜湊函數要滿足三個條件：

確定性：同一個鍵永遠得到同一個索引。
均勻性：把鍵均勻撒到所有格子，減少碰撞。
快速計算：算雜湊值本身不能太慢，否則 O(1) 查詢的優勢被吃掉。

Python 中任何「可雜湊」物件都有 hash() 方法；整數的雜湊值通常是它自己（小整數），字串的雜湊值則經過複雜混合，且為了安全加入了隨機鹽（每次執行程式可能不同）。

常見設計策略#

除法取餘（division method）：h(k) = k % m。m 要選質數，避免鍵的分布與 m 有週期關係時碰撞暴增。例如 m=11 時，鍵 3、14、25 都映射到 3。
乘法混入高位（multiplicative method）：h(k) = floor(m * ((k * A) % 1))，A 取黃金比例相關常數，對任何 m 都大致均勻。
多項式滾動雜湊（polynomial rolling hash）：字串 "abc" 算成 c0*B^2 + c1*B + c2（B 取 31、131 等），讓位置不同的字元產生不同影響，避免 "ab"、"ba" 撞在一起。
折疊法：把長鍵切成幾段相加再取餘，適合身分證號、電話號碼等固定格式鍵。

Python 實作#

def hash_mod(k, m):                       # 除法取餘
    return k % m

def poly_hash(s, m, base=131):
    h = 0
    for ch in s:
        h = (h * base + ord(ch)) % m
    return h

def fold_hash(num_str, m, chunk=2):       # 折疊法
    parts = [int(num_str[i:i+chunk]) for i in range(0, len(num_str), chunk)]
    return sum(parts) % m

# 觀察均勻性：統計每個格子的碰撞數
from collections import Counter
import random

m = 97
keys = [random.randint(0, 10**6) for _ in range(10_000)]

c1 = Counter(hash_mod(k, m) for k in keys)
c2 = Counter(hash_mod(k, 100) for k in keys)   # m 不是質數
print(f"質數 m=97：最大格子 {max(c1.values())} 筆")
print(f"非質數 m=100：最大格子 {max(c2.values())} 筆")

names = ["alice", "bob", "charlie", "dave", "eve", "frank"]
for n in names:
    print(f"{n:8s} -> 格子 {poly_hash(n, 64)}")

鍵不是整數時，先用 hash() 取得整數再取餘：

def index_for(key, m):
    return hash(key) % m          # hash() 對 str/tuple 等都可用

壞雜湊的後果#

若所有鍵都撞到同一格，雜湊表退化成串列/陣列，查詢變 O(n)。經典案例：以「字串長度」當雜湊函數，所有等長字串全撞一格；以「百位數」當雜湊函數存電話號碼，尾數變化完全被忽略。設計時要問自己：我的鍵在哪些位元上會變化？雜湊函數有把這些變化都用上嗎？

複雜度分析#

雜湊計算本身：除法取餘 O(1)；多項式滾動雜湊為 O(字串長度)，對長字串這是必要成本（畢竟得讀完整個鍵才能區分它）。設計良好的情況下，n 筆資料撒進 m 格，每格平均 n/m 筆，這個比值叫負載因子 α，是下一節的主角。

練習#

用 poly_hash 統計 1 萬個隨機英文單字在 m=32、64、97 下的最大格子負載，解釋為何 m=97 表現最好。
設計一個存「西元生日（YYYYMMDD）」的雜湊函數，並說明為什麼 k % 10000（只取月日）可能比 k % m 更糟或更好。
為什麼 Python 的 list 不能當 dict 的鍵，tuple 卻可以？（提示：可變性與雜湊值穩定性）