Learning Objectives
- 說明雜湊函式把鍵對應到桶號，寫出整數取餘數與字串多項式雜湊，並說明每一步取餘數的原因
- 說明什麼是碰撞，用鏈結法（每個桶一條串列）實作插入與查詢
- 計算負載因子，說明擴容時為什麼每個鍵都要重新雜湊
- 說明雜湊表平均 O(1)、最壞 O(n) 的原因
- 使用 Python 的 dict、C++ 的 unordered_map、Java 的 HashMap 解決兩數之和與字數統計，並知道走訪順序不固定
用鍵直接找到資料
系統裡有幾萬筆學生資料，輸入學號就要立刻顯示成績。依第 04 課的做法：
- 資料沒排序：線性搜尋，O(n)
- 資料排好序：二分搜尋，O(log n)
還能更快嗎？如果學號剛好是 0～999 的整數，可以開一個長度 1000 的陣列，學號直接當索引，score[學號] 一步就拿到，O(1)。
問題是真實的鍵通常很大（9 位數的學號）或根本不是整數（帳號、單字），不可能開那麼大的陣列。
雜湊表（hash table）的做法：準備 m 個格子（叫做桶，bucket），再用一個雜湊函式（hash function）把任何鍵換算成 0～m-1 之間的桶號：
鍵 "cat" ──雜湊函式──> 桶號 10 ──> 去第 10 個桶找
算桶號只要固定的幾步，所以查詢、插入、刪除平均都是 O(1)。Python 的 dict 和 set、C++ 的 unordered_map、Java 的 HashMap 都是雜湊表。
好的雜湊函式
雜湊函式要滿足三件事：
- 同一個鍵永遠算出同一個桶號，否則存進去就找不回來
- 計算很快
- 桶號分布平均，不要讓很多鍵擠在同一個桶
整數最常見的寫法是除以桶數取餘數：k % m。
字串要先把字元變成數字。最直覺的做法是把每個字元的編碼加起來再取餘數，但這樣 "cat"、"act"、"tac" 的加總都一樣，字母相同、順序不同的字一定撞在一起。
多項式雜湊讓每個位置的權重不同：
h = 0
for c in s:
h = (h * 31 + ord(c)) % m
展開來是 c₀ × 31² + c₁ × 31 + c₂（再取餘數），字元的順序會影響結果。Java 的 String.hashCode() 也是用 31 當乘數。
每一步都取餘數有兩個原因：最後的結果和「全部算完再取餘數」相同（餘數的加法、乘法性質），而且中間的數字永遠小於 m，
C++ 和 Java 的 int 不會溢位。如果不取餘數，長一點的字串很快就超過 int 的上限（約 21 億）；Python 的整數沒有上限，但數字越大算得越慢。
三種雜湊函式算出來的桶號
桶數 m = 11。整數 3、14、25 相差 11 的倍數，取餘數都是 3，撞在同一個桶。字串的部分看 h 怎麼一個字元一個字元累積：用加總時 cat 和 act 都是 4；用多項式雜湊時分別是 10 和 9。（C++、Java 的函式名稱是 hashInt、hashSum、hashPoly。）
碰撞與鏈結法
鍵的種類遠多於桶數，一定會有兩個不同的鍵算出同一個桶號，這叫碰撞（collision）。好的雜湊函式只能讓碰撞變少，不能完全避免。
處理碰撞最常見的兩種方法：
| 方法 | 做法 |
|---|---|
| 鏈結法（separate chaining） | 每個桶放一條串列，桶號相同的鍵依序接在後面 |
| 開放定址法（open addressing） | 每個桶只放一個鍵；桶被占了就依規則找下一個空桶，例如往後一格一格找（線性探測） |
下面的範例用鏈結法實作「學號 → 成績」的表：buckets 是「串列的串列」，每個桶是一條串列，裡面放 [鍵, 值]。
- 插入：算出桶號，在那一個桶裡找這個鍵；找到就更新值，找不到就接到後面
- 查詢：算出桶號，只在那一個桶裡一個一個比對鍵
桶裡可能有不同的鍵（碰撞），所以查詢時一定要比對鍵本身，不能只看桶號。
用串列的串列實作雜湊表
15、22、8 除以 7 的餘數都是 1，三個鍵依插入順序串在桶 1。再插入一次 22 時，桶 1 裡已經有 22，只更新它的值（65 改成 70）。查詢 29 時也算出桶 1，比對完三個鍵都不是，回傳 -1。（C++ 的每一對是 pair、Java 是長度 2 的 int[]；查詢函式在 C++、Java 叫 getValue。）
為什麼桶數常用質數
實驗室裡的第一、二個任務說明了一件事：鍵常常有規律（都是 10 的倍數、都是偶數、都以 000 結尾），
如果 m 和這個規律有公因數，例如 m = 10，k % m 只會落在少數幾個桶。m 是 5 也一樣，因為 10 是 5 的倍數，10 的倍數除以 5 全部餘 0。
把 m 取成質數（而且不是鍵的規律的因數），鍵的規律比較不容易和 m 對齊，分布會平均得多。這是經驗法則，不是保證；
也有實作固定用 2 的次方當桶數（例如 Java 的 HashMap），改由雜湊函式本身把位元打散。
想一想：雜湊函式與碰撞
下面的程式會印出什麼？
def hash_poly(s, m):
h = 0
for c in s:
h = (h * 31 + ord(c)) % m
return h
print(hash_poly("ab", 7))
（ord("a") 是 97，ord("b") 是 98）
桶數 m = 10，雜湊函式 k % m，依序插入 10、20、30、40、50、60、70、80。這時候查詢 90（不在表裡）要比較幾次鍵？
鏈結法的查詢已經算出了桶號，為什麼還要在桶裡逐一比對鍵？
負載因子與擴容
負載因子（load factor）＝ 鍵數 n ÷ 桶數 m，代表平均每個桶有幾個鍵。用鏈結法時，查詢平均要比對的次數大約和負載因子成正比：
- 負載因子 0.5：平均每條串列不到 1 個鍵，幾乎一步就找到
- 負載因子 5：平均每條串列 5 個鍵，查詢變慢
所以雜湊表會在負載因子超過某個門檻時擴容（resize）：開一個更大的桶陣列（例如桶數約變成兩倍），再把所有鍵搬過去。
搬家時每個鍵都要重新計算桶號（rehash），因為桶號是 k % m，m 變了，桶號也跟著變；不能把舊的桶原封不動複製過去。
擴容一次要搬 n 個鍵，是 O(n)，但桶數每次變成兩倍，擴容的次數很少。和第 03 課動態陣列的擴容一樣，平均分攤到每次插入，還是 O(1)（攤銷分析）。
各語言內建的門檻不同：Java 的 HashMap 預設是 0.75，C++ 的 unordered_map 預設的最大負載因子是 1.0。下面的範例用「超過 1 就擴容」。
負載因子超過 1 時擴容
先插入 5 個鍵到 5 個桶，負載因子 100%。插入第 6 個鍵 41 後變成 120%，超過 1，於是擴容成 11 個桶。看第二個面板：12 和 7 原本都在桶 2，重新計算後分到桶 1 和桶 7，碰撞變少了。（為了只看擴容，這個範例假設不會插入重複的鍵。）
平均 O(1)，最壞 O(n)
| 操作 | 平均 | 最壞 |
|---|---|---|
| 插入 | O(1) | O(n) |
| 查詢 | O(1) | O(n) |
| 刪除 | O(1) | O(n) |
平均 O(1) 的前提是雜湊函式把鍵分得夠平均，而且負載因子維持在固定的範圍內（靠擴容）。
最壞 O(n) 發生在所有鍵都擠進同一個桶：查詢要比對整條串列，等於線性搜尋。除了雜湊函式設計不好，也可能是有人故意送出大量會碰撞的鍵，讓伺服器變慢。
所以實際的實作會加上防護：Python 從 3.3 版起，字串的雜湊值預設加入每次執行都不同的隨機種子；Java 8 起，HashMap 的某個桶太長（8 個以上，而且桶數夠多）時，會把那條串列改成平衡樹，最壞情況變成 O(log n)。
雜湊表沒有順序：它不能快速找出最小的鍵，也不能依鍵的大小走訪。需要「有順序的 map」時，用 C++ 的 map、Java 的 TreeMap（第 14 課的二元搜尋樹），代價是操作變成 O(log n)。
各語言內建的雜湊表
| 操作 | Python dict |
C++ unordered_map |
Java HashMap |
|---|---|---|---|
| 建立 | d = {} |
unordered_map<string, int> d; |
HashMap<String, Integer> d = new HashMap<>(); |
| 設定 | d[k] = v |
d[k] = v; |
d.put(k, v); |
| 讀取 | d[k]（不存在會出錯）、d.get(k, 0) |
d[k]（不存在會自動建立，值是 0） |
d.get(k)（不存在回傳 null）、d.getOrDefault(k, 0) |
| 有沒有這個鍵 | k in d |
d.count(k) |
d.containsKey(k) |
| 刪除 | del d[k] |
d.erase(k); |
d.remove(k); |
只需要「有沒有」不需要值時，用集合：Python 的 set、C++ 的 unordered_set、Java 的 HashSet。
走訪順序：Python 的 dict 會依插入順序走訪，但 C++ 的 unordered_map 和 Java 的 HashMap 的順序取決於雜湊值與桶數，三種語言彼此不同，也可能在擴容後改變。
要印出整張表時，先把鍵排序再印，下面兩個範例都是這樣做。
兩數之和：邊走邊查
題目：陣列裡有沒有兩個數加起來等於 target？兩層迴圈要比較約 n² / 2 對；用雜湊表只要走一次：走到 a[i] 時，查表看「target - a[i]」有沒有出現過，每次查詢平均 O(1)，總共 O(n)。找 9 時，走到 7 發現 2 出現過，答案是索引 1 和 3。（C++、Java 的函式名稱是 twoSum；表格的順序依各語言的走訪順序，三種語言不一樣。）
字數統計：排序後再印
每看到一個單字，就把它的次數加 1。三種語言「鍵還不存在」的寫法不同：Python 用 get(w, 0)、Java 用 getOrDefault(w, 0)，C++ 的 counts[w] 遇到不存在的鍵會先建立一個值為 0 的項目。切換語言比較 counts 表格裡的順序：三種都不一樣，所以印之前先排序。
想一想：負載因子、複雜度與內建工具
一個用鏈結法的雜湊表有 8 個桶、存了 12 個鍵。負載因子是多少？如果「超過 1 就擴容成 2m 之後的第一個質數」，擴容後的負載因子大約是多少？
下面的程式會印出什麼？
counts = {}
for ch in "banana":
counts[ch] = counts.get(ch, 0) + 1
print(counts["a"], counts["n"], len(counts))
要依「學號由小到大」印出所有學生的成績，學生資料存在 C++ 的 unordered_map<int, int> 裡。下列哪個做法正確？
實作：第一個重複出現的值
從左到右掃描陣列，用集合（set）記住看過的值。請找出第一個「之前已經出現過」的值，並印出總共有幾種不同的值。C++ 用 unordered_set（count、insert），Java 用 HashSet（contains、add）。
重點整理
- 雜湊表用雜湊函式把鍵換算成桶號，查詢、插入、刪除平均 O(1)
- 整數鍵常用
k % m；字串用多項式雜湊h = (h * 31 + c) % m，字元順序會影響結果，每一步取餘數避免溢位 - 不同的鍵落在同一個桶叫碰撞；鏈結法讓每個桶掛一條串列，查詢時在那一個桶裡比對鍵
- 負載因子 = n / m；超過門檻就擴容，每個鍵都要依新的桶數重新雜湊，攤銷後插入仍是 O(1)
- 最壞情況所有鍵擠在同一個桶，退化成 O(n)；桶數常取質數，讓有規律的鍵分得比較平均
- 內建：Python
dict／set、C++unordered_map／unordered_set、JavaHashMap／HashSet；走訪順序不固定，要印就先排序
下一課：二元樹。雜湊表沒有順序，二元樹則能依大小組織資料；先從樹的術語與四種走訪方式開始。