雜湊表：用櫃號快速找書
圖書館用「書名 → 櫃號」快速找書，雜湊表是電腦版。平均 O(1) 找東西，超快。
想像你在管理一座圖書館
讀者來借書，怎麼快速找到書？三種策略：
- 一排一排找 → O(n) 線性搜尋，書多就慘。
- 按書名排序，二分搜尋 → O(log n)，加書時要重排。
- 建一張「書名 → 櫃號」對照表 → O(1) 一秒找到。
第三種就是雜湊表 (Hash Table)。
核心想法
用一個雜湊函數 (Hash Function) 把 key 變成「陣列的 index」。
key: "蘋果"
hash("蘋果") = 7
A[7] = "蘋果", value要找 “蘋果” 時，再算一次 hash，直接跳到 A[7]——不用一格一格找。
衝突：兩本書要放同一格
問題來了——hash(“蘋果”) 和 hash(“香蕉”) 可能算出同一個 index！ 這叫衝突 (Collision)。
解法 1：Chaining（鏈結法）
每一格存一個 list，衝突的都串起來：
A[7] → ["蘋果"-1] → ["香蕉"-2] → null
A[3] → ["橘子"-3] → null找 “蘋果”：先算 hash → 7 → 走 list 找到 “蘋果”。
解法 2：Open Addressing（開放定址）
衝突了就找下一格空的塞進去：
A[7] = "蘋果"
hash("香蕉") = 7，但 A[7] 滿了 → 試 A[8]
A[8] = "香蕉"找 “香蕉”：先算 hash → 7 → 不是 → 看 8 → 是！
複雜度
| 操作 | 平均 | 最壞 |
|---|---|---|
| 插入 | O(1) | O(n) |
| 查詢 | O(1) | O(n) |
| 刪除 | O(1) | O(n) |
最壞 O(n) 何時發生？當大量衝突堆在同一格時——基本上 hash 函數選太爛。 好的 hash 函數會讓衝突很少，所以平均 O(1) 是實際表現。
- 需要快速查詢「這個 key 有沒有出現過」→ 用 Set
- 需要快速查表「這個 key 對應的 value 是什麼」→ 用 Dict / Map
- 不需要排序、不在乎順序
Python dict、JavaScript Object、Java HashMap 背後都是雜湊表。
一個好的 Hash Function 要做到
- 均勻分布：不同的 key 算出來的 index 要散得均勻，少衝突。
- 快：算 hash 本身不能慢，不然就失去意義了。
- 同 key 同 hash：相同輸入永遠得到相同輸出。
實務上字串雜湊常用多項式雜湊：
但你不用記公式，知道**「用某種混合方式把 key 變成數字」**就好。
題型一：給 hash function 和一串 key，畫出 hash table。
例：表大小 10，hash(k) = k mod 10。插入 21, 4, 15, 32, 11，用 chaining：
- 21 → 1
- 4 → 4
- 15 → 5
- 32 → 2
- 11 → 1（衝突，串在 21 後）
A[1] → 21 → 11
A[2] → 32
A[4] → 4
A[5] → 15題型二：講 chaining vs open addressing 優缺點。
| Chaining | Open Addressing | |
|---|---|---|
| 空間 | 表 + 鏈結串列 | 只有表本身 |
| 刪除 | 容易 | 麻煩（要標記） |
| 滿了 | 不會「滿」 | 可能滿，要 resize |
| cache | 跳指標較慢 | 較 cache-friendly |
題型三：為什麼平均 O(1) 但最壞 O(n)？ 答：好 hash 函數讓衝突少 → 大多數操作 O(1)。 但極端情況（hash 全衝突 / 惡意輸入），所有 key 擠同一格 → 變成走完整個 list → O(n)。
這章記住
- 雜湊表 = key → hash → index，平均 O(1) 查詢。
- 衝突解法：Chaining（串起來）或 Open Addressing（找下一格）。
- 最壞 O(n)，但實務上接近 O(1)。
- Python
dict、JavaHashMap都是這玩意。
學習進度只存在你的瀏覽器，不會上傳。