在一堆資料裡找東西，最笨的方法是從頭一個一個比。雜湊表（hash table）換個做法：用 key 算出位置，直接走過去拿。C# 的 Dictionary、Go 的 map 都是它。
這篇接在上一篇〈動態陣列〉後面，擴容那段會用到它的「翻倍」。
一句話：雜湊表像一間包裹店。用收件人名字算出櫃號，櫃台那張紙條寫著包裹在倉庫哪一格，直接去拿。
示意：沒有雜湊表要一路比過去；有雜湊表就先算出號碼、直接過去（細節下面一步步拆，點圖可放大）
| 名詞 | 白話 |
|---|---|
| key ／ value | 拿來找的「名字」／找到後拿到的「東西」。dict[key] = value。 |
| 雜湊函式（hash function） | 一條固定公式，把 key 變成一個整數。同一個 key 每次算都一樣。C# 裡就是 key 的 GetHashCode()。 |
| hash code | 公式算出來的那個整數。 |
| bucket（櫃號） | hash code 除以櫃號總數取餘數，就是第幾號。 |
| 碰撞（collision） | 兩個不同的 key 算到同一個櫃號。很正常，一定會發生。 |
| Equals | 核對「這件真的是我要的 key 嗎」。hash code 一樣，不代表是同一個 key。 |
| O(1) ／ O(n) | 花的時間「跟資料量無關」／「跟資料量成正比」。資料多 10 倍，O(n) 的事就慢約 10 倍。 |
整篇用同一組例子：3 個櫃號（0、1、2），放 3 個 key：A、B、C。假設它們的 hash code 是 10、7、5。
圖 A：key 經過固定公式變成數字，取餘數得到櫃號（點圖可放大）
好的雜湊函式要做到兩件事：
這段在講：包裹店先用名字算出櫃號，就知道去哪找，不用從頭翻。A、B 撞在同一個櫃號是正常的，下一步看它們怎麼放。
先想一個問題：櫃子很小，一格只夾得下一張紙條，放不下包裹。可是 A 和 B 偏偏都分到 1 號櫃，兩件要擺哪？
包裹店的做法：包裹全部放到後面的倉庫，照到貨順序排（第 0 格、第 1 格…）。櫃台上每個櫃號只夾一張紙條，寫「去倉庫第幾格找」。
照順序放 A、B、C，看紙條和倉庫怎麼變：
圖 B0：照順序放 A、B、C，每一步只改橘色那一格（點圖可放大）
現在要找 1 號櫃的東西，路線是：紙條說第 1 格 → 拿到 B → B 的貼紙說下一件在第 0 格 → 拿到 A → A 的貼紙寫「沒有」，結束。
這種「一件指到下一件」的排法，就叫一串（英文 chaining）；貼紙上的「下一件在哪」叫 next，「沒有」在程式裡寫成 −1。B 比 A 晚到卻排在前面，是因為新來的直接插最前面最省事：改一張紙條、寫一張貼紙就好。
三件都放好的樣子就是下面這張表。貼紙上另外還抄了每件的 hash code，下一步查的時候會用到。
圖 C：放好之後的完整樣子。紙條指到 B，B 的貼紙再指到 A（點圖可放大）
註：在 .NET 原始碼裡，櫃台紙條是一個陣列叫 _buckets，倉庫是另一個陣列叫 _entries。紙條實際存「格號＋1」好讓 0 代表空的，觀念一樣。
這段在講：櫃子太小放不下包裹，所以包裹全放倉庫、櫃台只夾一張「去第幾格」的紙條；同一個櫃號的包裹，靠貼紙上的「下一件在哪」一件接一件。
查 dict[A] 時，先算出櫃號、看紙條，再沿著串一件件看。每看一件分兩關：
圖 B：同一份資料，先查 A、再查 D（動畫會循環，點圖可放大）
注意第 ⑤ 步：D 和 A 的 hash code 剛好一樣，但不是同一個 key。數字一樣只代表「可能是」，最後一定要靠 Equals 確認。
這段在講：店員找包裹，先看貼紙上的數字，數字對了才核對收件人。hash 負責「快速縮小範圍」，Equals 負責「確定是同一個」，兩個缺一不可。
背景。前面的 key 都是字串或數字，這些是 C# 內建的型別，它本來就知道兩個 "apple" 是一樣的。但有時 key 不只是一個值。例如做一張地圖，想記「(1, 2) 這格是家、(3, 5) 這格是商店」，key 就是一個座標，你得自己寫一個 Point 型別來裝 X 和 Y。
問題。C# 不知道你的 Point 怎樣算「一樣」。它預設只認「同一個物件」：就像兩張內容一模一樣的名片，C# 只認你當初放進去的那一張；你拿另一張一樣的來問，它說不認識。
這段要學的。怎麼告訴 C#「X、Y 一樣就算同一個」，以及只說一半會發生什麼事：放進去了，卻查不到。
要說的有兩件事，剛好對應第三步查詢時的兩關：
| 查詢的關卡 | 靠哪個方法 | 你要教它什麼 |
|---|---|---|
| 第 1 關：比貼紙上的數字 | GetHashCode | 數字要照 X、Y 算，X、Y 一樣就算出一樣的數字 |
| 第 2 關：數字一樣，才核對是不是同一個 | Equals | X、Y 都一樣，就算同一個 |
兩件都沒教的話，C# 用預設的做法：每個物件一出生就領一個自己的號碼，跟裡面裝什麼無關。所以你放進去的 (1, 2) 和後來拿來查的 (1, 2)，號碼幾乎一定不一樣。
常見的錯，是只教了第 2 關、忘了第 1 關（程式裡叫「只覆寫 Equals」，覆寫＝把 C# 預設的做法換成你自己的）。結果查的時候，第 1 關一比，號碼不一樣，Dictionary 直接判定「不是這件」，第 2 關根本輪不到。你的 Equals 寫得再對，也沒機會上場，所以明明放進去了，卻查不到。
圖 F：差別只在 GetHashCode。數字對不上，Equals 根本輪不到（點圖可放大）
準備開一個新資料夾：mkdir lab-cs && cd lab-cs && dotnet new console，把 Program.cs 整個換成：
var d = new Dictionary<Point, string>();
d[new Point { X = 1, Y = 2 }] = "家";
Console.WriteLine(d.ContainsKey(new Point { X = 1, Y = 2 }));
class Point
{
public int X, Y;
public override bool Equals(object? o)
{ Console.WriteLine("呼叫了 Equals"); return o is Point p && p.X == X && p.Y == Y; }
// public override int GetHashCode() => HashCode.Combine(X, Y);
}先猜Equals 寫對了，會印 True 嗎？「呼叫了 Equals」會出現嗎？
執行在 lab-cs 裡 dotnet run：
…warning CS0659: 'Point' overrides Object.Equals(object o) but does not override Object.GetHashCode()
False再把最後一行 GetHashCode 前面的 // 拿掉，重跑：
呼叫了 Equals
True你會看到第一次只有 False，「呼叫了 Equals」一次都沒出現，編譯器還先警告了 CS0659。補上 GetHashCode 後，Equals 被呼叫一次，印 True。
這證明hash code 對不上，Dictionary 在「比數字」那關就跳過了，Equals 根本沒被呼叫。
所以規則只有一條：Equals 說相等的兩個 key，GetHashCode 一定要算出同一個數。反過來不用：數字一樣不一定相等，那就是碰撞。
HashCode.Combine(X, Y) 組起來。record Point(int X, int Y);，編譯器會自動產生成對的 Equals 和 GetHashCode。這段在講：查詢要過兩關，第 1 關比數字（GetHashCode）、第 2 關才核對（Equals）。只教第 2 關的話，第 1 關就被擋下來，永遠查不到。編譯器的 CS0659 警告就是在提醒你：Equals 改了，GetHashCode 也要跟著改。
.NET 的倉庫格數和櫃號數一樣多。倉庫一滿（平均每個櫃號 1 件），就像上一篇的動態陣列一樣翻倍：櫃號變成約 2 倍（.NET 會挑質數，3 → 7）。
每件包裹用貼紙上抄好的 hash code 重新取餘數，換到新櫃號。偶爾搬一次很貴，平均下來 Add 還是 O(1)，道理跟上一篇一樣。
圖 D：3 個櫃號 → 7 個。同一個 hash code 除以新的櫃號數，原本擠在一起的 A、B 分開了（點圖可放大）
這段在講：包裹多到倉庫放滿，就換一間兩倍大的店，照貼紙上的數字重新分櫃號，擠在一起的會散開。
O(1) 有前提：key 要平均分散。微軟文件也說查找「接近 O(1)」，快慢取決於雜湊函式的品質。
如果所有 key 都算到同一個櫃號，那一串就有 n 件，每次查都從頭比到尾，變成 O(n)。擴容也救不了：hash code 全一樣，櫃號再多也是同一號。
圖 E：左邊分得平均，查一次只比 1～2 件；右邊全擠一個櫃號，查一次要比整串（點圖可放大）
GetHashCode 寫成永遠 return 1 是合法的：相等的 key 數字一樣，這條仍成立。只是全部擠進同一個櫃號。慢多少？自己量。
Go 不讓你換 map 的雜湊函式，所以自己做一個迷你雜湊表：每個櫃號一條串（用 slice），只放 key。兩次執行只差在雜湊函式。
準備開一個新資料夾：mkdir lab-go && cd lab-go && go mod init lab-go，建一個 main.go：
package main
import (
"fmt"
"time"
)
func run(name string, hash func(int) int) {
const n = 20000
lockers := make([][]int, n) // n 個櫃號，每號一條串
longest := 0
for k := 0; k < n; k++ { // 放進去：算櫃號，接到那一號的串上
i := hash(k) % n
lockers[i] = append(lockers[i], k)
longest = max(longest, len(lockers[i]))
}
start := time.Now()
for k := 0; k < n; k++ { // 每個 key 查一次：到它的櫃號，沿串一個個比
for _, x := range lockers[hash(k)%n] {
if x == k {
break
}
}
}
fmt.Printf("%s：最長的串 %5d 個，查 %d 次花 %v\n", name, longest, n, time.Since(start))
}
func main() {
run("好的 hash", func(k int) int { return k }) // key 是 0～19999，剛好各佔一號
run("爛的 hash", func(k int) int { return 1 }) // 不管什麼 key 都去 1 號
}先猜爛的 hash 會慢幾倍？10 倍？100 倍？
執行在 lab-go 裡 go run .：
好的 hash：最長的串 1 個，查 20000 次花 101.542µs
爛的 hash：最長的串 20000 個，查 20000 次花 74.011292ms你會看到最長的串從 1 變成 20000，時間慢了好幾百倍（連跑三次約 700～2000 倍，看電腦而定）。
這證明圖 E：O(1) 靠的是「分得開」；全擠一個櫃號，每次查都要比過整串。
故意灌碰撞（hash flooding）：key 來自使用者輸入時，壞人可以專挑會撞在一起的 key 塞進來，把伺服器拖慢。.NET 對 string key 有防線：一條串碰撞超過 100 次，就換一條壞人猜不到的公式，整張表重排。
這段在講：包裹全塞進同一個櫃號，店員就得一件件翻，雜湊表退回「從頭比」。
dict[k] 丟 KeyNotFoundException；Go m[k] 回傳零值（該型別的空白值，int 就是 0），不會出錯。v, ok := m[k]（這叫 comma-ok，ok 就是「有沒有」）；C# 用 TryGetValue。== 比：slice、map、func 都不能當 key。Go 也不讓你自己寫雜湊函式。Go 1.24 起 map 底層改用 Swiss Tables，碰撞時不串成一串，但「算位置、直接拿」的想法一樣。
能不看筆記回答下面 5 題，這篇就過了。
Point(1,2) 的數字不同。HashCode.Combine，或直接用 record。