Learning Objectives
- 自己寫整數與字串的雜湊函數，說明為什麼不直接用語言內建的 hash()／hashCode()
- 用節點與指標實作鏈結法：插入放在桶的最前面，刪除時用 prev 指標跳過節點
- 實作開放定址的線性探測，並說明主要叢集為什麼會讓探測次數變多
- 比較線性探測、平方探測、雙重雜湊三種探測順序，算出每一次要試的位置
- 說明開放定址刪除時為什麼要留下墓碑，以及插入時怎麼重複使用墓碑
- 說明負載因子對兩種做法的影響，實作重新雜湊（擴容並清掉墓碑）
把雜湊表拆開來看
演算法軌第 12 課用過雜湊表：Python 的 dict、C++ 的 unordered_map、Java 的 HashMap，查詢、插入、刪除平均都是 O(1)。
這一課自己把它做出來，回答三個實作上的問題：
- 雜湊函數怎麼寫：鍵怎麼換成 0～m-1 的位置
- 碰撞了放哪裡：兩種做法 - 鏈結法（separate chaining）：每個位置掛一條鏈結串列，碰撞的鍵都串在同一條上 - 開放定址（open addressing）：所有鍵都放在陣列本身，位置被占了就依規則去試別的位置
- 刪除與擴容：刪掉一個鍵之後，其他鍵還找得到嗎？表滿了怎麼辦？
| 語言內建 | 用哪一種做法 |
|---|---|
Java HashMap |
鏈結法（某個桶太長時改成平衡樹） |
C++ unordered_map |
標準規定了「桶」的操作介面，常見的實作都是鏈結法 |
Python dict |
開放定址（探測順序用雜湊值的高位元打散，不是單純的線性探測） |
自己寫雜湊函數
整數：最常用除法，h(k) = k % m。m 選質數，鍵有規律時（例如都是 10 的倍數）比較不會擠在少數幾個位置。
教科書還會介紹其他做法，概念如下：
| 方法 | 做法 |
|---|---|
| 除法 | k % m |
| 平方取中 | 把 k 平方，取中間幾位數 |
| 折疊 | 把很長的鍵（例如身分證號）切成幾段相加，再取餘數 |
字串：把每個字元的編碼加權後加起來，再取餘數。用霍納法（Horner）一邊乘一邊加：
v = 0
for ch in s:
v = (v * 31 + ord(ch)) % m # 前面的字元乘過比較多次 31
只把字元碼直接相加的話，"cat"、"act" 的和相同，一定碰撞；加權之後字元的位置也會影響結果。每一步都取餘數，數字永遠小於 m，C++、Java 的 int 不會溢位。
為什麼不用內建的 hash()／hashCode()？ 這一課要看的是雜湊表本身，結果要能在三種語言重現：
- Python 的字串
hash()每次執行程式都不同（預設加了隨機種子，防止有人故意送出大量會碰撞的鍵） - Java 的
String.hashCode()固定，C++ 的std::hash由各家實作決定 - 三種語言對同一個字串算出來的值彼此不同
所以本課的範例全部用自己寫的雜湊函數。
鏈結法：每個桶是一條鏈結串列
表是長度 7 的陣列，每一格存一個指標，指向那一條串列的第一個節點（空的桶是 null）。cat、ant、yak 算出來都是桶 3：新節點一律插在最前面，所以桶 3 的順序是 yak → ant → cat。刪除 ant 時，prev 停在 yak、p 停在 ant，讓 yak 直接指向 cat；刪除 dog 時它是桶裡第一個節點，改的是 table[6] 本身。C++ 版刪除後要 delete p，最後再把所有節點釋放。
鏈結法的記憶體與操作
鏈結法的記憶體分成兩部分：
table（m 個指標） 節點（每個鍵一個，散在堆積區）
[0] null
[1] ──→ [owl | •]──→ null
[3] ──→ [yak | •]──→ [cat | •]──→ null
[6] null
| 操作 | 做法 | 時間 |
|---|---|---|
| 插入 | 先在這一桶找有沒有重複，沒有就插在最前面 | 和這一桶的長度成正比 |
| 搜尋 | 只走這一桶 | 和這一桶的長度成正比 |
| 刪除 | 走的時候用 prev 記住前一個節點，找到後讓 prev.next 跳過它；刪第一個節點時改的是 table[b] |
和這一桶的長度成正比 |
每一桶的平均長度就是負載因子 α = n / m。鏈結法的 α 可以超過 1（範例裡 8 個鍵放在 7 個桶），只是串列變長、變慢，所以實際的實作在 α 超過某個門檻時擴容（演算法軌第 12 課）。
插在最前面而不是最後面，是因為串列只有 head：插在最後面得先走到尾巴。不過範例在插入前仍然走了一遍整條串列，那是為了檢查鍵是否已經存在；如果確定不會有重複的鍵，插入就是真正的 O(1)。
開放定址：所有鍵都放在陣列裡
開放定址不用串列，每個位置只放一個鍵。位置被占了，就依固定的規則算出下一個要試的位置，這一串位置叫探測序列（probe sequence）。 第 i 次（i 從 0 開始）要試的位置：
| 方法 | 第 i 次試的位置 | 從原位往後的距離 |
|---|---|---|
| 線性探測（linear probing） | (h(k) + i) % m |
0、1、2、3… |
| 平方探測（quadratic probing） | (h(k) + i²) % m |
0、1、4、9… |
| 雙重雜湊（double hashing） | (h(k) + i × h2(k)) % m |
0、s、2s、3s…，s = h2(k) 每個鍵不同 |
搜尋照同一個探測序列走：遇到要找的鍵就找到了；遇到空格才能確定不在表裡，因為插入時如果它在，會放在這個空格之前。
線性探測最簡單，但被占用的格子會連成一長串，叫做叢集（clustering）。原位落在叢集裡任何一格的鍵，都要走到叢集尾端才找得到空格，而且放進去之後叢集又更長了。 下面的範例 8 個鍵裡有 3 個原位是 0、2 個原位是 2，位置 0～5 很快連成一串。
線性探測與叢集
表的大小 m = 11。22、11、33 的原位都是 0，13、24 的原位是 2，它們互相擠壓，位置 0～5 連成 6 格的叢集。插入 33 時要看 6 格。最後搜尋不在表裡的 44（原位 0），要從 0 一路走到 6 才遇到空格，看了 7 格。
平方探測與雙重雜湊
線性探測的問題叫主要叢集（primary clustering）：不同原位的鍵也會被同一個叢集拖累。兩種改進：
平方探測跳的距離越來越大（1、4、9…），離開原位附近比較快，不容易連成一長串。 但原位相同的兩個鍵，探測序列還是完全一樣，這叫次要叢集（secondary clustering）。 另一個限制：平方探測不保證試遍每一格。m 是質數而且表不到一半滿時，一定找得到空格；超過一半就可能繞不到空格。
雙重雜湊用第二個雜湊函數決定步長，原位相同的鍵，步長通常不同，探測序列就分開了。步長要注意兩件事：
- 不能是 0，否則永遠停在原位。常見寫法
h2(k) = R - k % R（R 是比 m 小的質數），結果在 1～R 之間 - 要和 m 互質，才會試遍每一格。m 取質數時，1～m-1 的步長都和 m 互質
下面的範例把同一組鍵（22、33、44 的原位都是 0，1、12 的原位都是 1）用三種方法各插一次，比較總共看了幾格。
三種探測方法比一比
同樣 5 個鍵、同樣 m = 11。看 44 這個鍵：線性探測依序試 0、1、2；平方探測試 0、1、4；雙重雜湊的步長是 7 - 44 % 7 = 5，試 0、5。總探測次數：線性 13、平方 11、雙重雜湊 8。（雙重雜湊每個鍵都要多算一次步長；資料量大時，少看幾格通常比較划算。）
想一想：雜湊函數、鏈結法與探測
鏈結法、新節點插在桶的最前面。cat、ant、yak 三個鍵依序插入，都落在桶 3。桶 3 的串列從頭到尾是什麼順序？
下面的程式用線性探測，會印出什麼？
m = 7
slots = [-1] * m
for k in [10, 17, 3]:
i = k % m
while slots[i] != -1:
i = (i + 1) % m
slots[i] = k
i, probes = 24 % m, 1
while slots[i] != -1 and slots[i] != 24:
i = (i + 1) % m
probes += 1
print(slots, probes)
為什麼本課的雜湊表不直接用 Python 的 hash() 或 Java 的 hashCode()？
刪除：留下墓碑
鏈結法刪除很直接：把節點從串列拿掉。開放定址就麻煩了。假設 3、14、25 都餘 3，依序放在位置 3、4、5：
位置 3 4 5 6
[3] [14] [25] [空]
如果刪除 14 時把位置 4 清成空格，之後搜尋 25：從 3 開始，看到位置 4 是空格就停下，以為 25 不在表裡，其實它在位置 5。 空格的意思是「從來沒有東西放過這裡」，搜尋靠它判斷可以停了；刪除不能製造假的空格。
做法是放一個墓碑（tombstone，也叫 lazy deletion）：
| 格子的狀態 | 搜尋遇到時 | 插入遇到時 |
|---|---|---|
| 空格 | 停：鍵不在表裡 | 可以放（如果路上沒有墓碑） |
| 墓碑 | 繼續往後找 | 記下第一個墓碑，最後放在那裡（重複使用） |
| 有鍵 | 是要找的就找到了，否則繼續 | 是同一個鍵就不重複放，否則繼續 |
插入時不能一看到墓碑就放下去：鍵可能在後面已經存在，要一路找到空格、確定沒有重複，才回頭放進第一個墓碑。
墓碑：刪除後還找得到，位置還能再用
3、14、25、36 都餘 3，放在位置 3～6。刪除 14 後，位置 4 變成 -2（墓碑）。搜尋 25 經過墓碑時繼續往後，在位置 5 找到；搜尋 14 一路走到位置 7 的空格才停。最後插入 47（也餘 3）：路上記下位置 4 的墓碑，走到空格確定 47 不在表裡之後，放進位置 4。
負載因子與重新雜湊
負載因子 α = n / m 對兩種做法的意義不同：
| 鏈結法 | 開放定址 | |
|---|---|---|
| α 的範圍 | 可以超過 1（每一桶平均 α 個節點） | 一定小於 1（每格只放一個鍵） |
| α 變大時 | 串列變長，搜尋時間大約和 α 成正比 | 叢集變長，α 接近 1 時探測次數急遽增加 |
| 常見的擴容門檻 | 0.75～1（Java HashMap 預設 0.75） |
0.5 左右（平方探測要保證找得到空格，一定要不到一半滿） |
在實驗室裡把「分散的鍵」插進 m = 7 的表，再插幾個鍵，觀察平均探測次數怎麼隨著負載因子上升。
開放定址還要把墓碑算進去：墓碑雖然沒有鍵，搜尋時還是要走過它。一直插入又刪除，表裡可能幾乎沒有鍵、卻滿是墓碑，搜尋失敗時要走很久。
重新雜湊（rehash）同時解決兩件事：
- 開一個更大的陣列（例如約兩倍，最好是質數）
- 把舊表裡真正的鍵一個一個重新插入：m 變了，每個鍵的位置都要重新計算；空格和墓碑都不搬
搬一次是 O(n)，但大小每次約變成兩倍，攤銷到每次插入仍是 O(1)，道理和第 03 課的動態陣列相同。
開放定址的重新雜湊
規則：放進下一個鍵之後，如果負載因子會超過 1/2，就先擴容。表一開始只有 5 格；插入第 3 個鍵前（3/5 超過 1/2）擴容成 11 格，12 和 7 重新算位置（12 % 11 = 1、7 % 11 = 7），原本擠在一起的鍵分開了。插入第 6 個鍵 41 前（6/11 超過 1/2），再擴容成 23 格。
想一想：探測順序、墓碑與負載因子
平方探測，m = 11，鍵 k 的原位是 3，而且前幾個位置都被占了。前 4 次試的位置依序是？
開放定址刪除一個鍵時，如果直接把那一格改回空格，會發生什麼事？
雙重雜湊用 h2(k) = 7 - k % 7，而不是直接用 k % 7 當步長。主要原因是什麼？
一張開放定址的表（m = 11）經過多次插入與刪除，現在只剩 2 個鍵，但有 7 個墓碑。下列哪個說法正確？
實作：會跳過墓碑的搜尋
請完成 find(slots, key)：用線性探測找 key，找到就回傳位置，找不到回傳 -1。insert 與 remove 已經寫好，remove 會留下墓碑 DELETED。注意：遇到墓碑不能停，只有遇到空格 EMPTY 才能確定不在表裡。可以切換成你熟悉的語言。
重點整理
- 雜湊函數：整數用
k % m（m 取質數）；字串用字元碼加權（v = (v * 31 + 字元) % m），每一步取餘數避免溢位；本課不用內建hash()，結果才固定、三種語言相同 - 鏈結法：m 個指標加上散在堆積區的節點；新節點插在桶的最前面；刪除要記
prev，刪第一個節點時改的是table[b]；C++ 要delete - 開放定址：所有鍵放在陣列裡，依探測序列找位置；遇到空格才能確定不在表裡
- 線性探測
h + i：簡單，但有主要叢集 - 平方探測
h + i²：減少主要叢集，仍有次要叢集；表要不到一半滿才保證找得到空格 - 雙重雜湊
h + i × h2：步長因鍵而異；h2 不能是 0，要和 m 互質 - 開放定址刪除要留墓碑：搜尋遇到墓碑繼續找，插入可以重複使用第一個墓碑
- 負載因子：鏈結法可以超過 1；開放定址一定小於 1，通常 0.5 左右就擴容。重新雜湊只搬真正的鍵，墓碑一起清掉
下一課：樹與二元樹的走訪。從線性的結構進到有分支的結構。