資料結構 · 雜湊表 # 雜湊表：算出櫃號，直接去拿（C# Dictionary 與 Go map） Chance Lu 在一堆資料裡找東西，最笨的方法是從頭一個一個比。**雜湊表**（hash table）換個做法：**用 key 算出位置，直接走過去拿**。C# 的 `Dictionary`、Go 的 `map` 都是它。 這篇接在[上一篇〈動態陣列〉](https://docs.smartech.tw/n/dynamic-array-list-slice)後面，擴容那段會用到它的「翻倍」。 > 一句話：雜湊表像一間**包裹店**。用收件人名字算出**櫃號**，櫃台那張紙條寫著包裹在倉庫哪一格，直接去拿。 沒有雜湊表：從頭一個一個比示意（數字是假設的）小明小華阿強美玲志豪淑芬建宏雅婷找「雅婷」比了 8 次；n 筆資料最多要比 n 次雜湊表：先用名字算出號碼，直接走過去「雅婷」固定公式算出 5 號01234雅婷567直接到 5 號：算 1 次、看 1 格 示意：沒有雜湊表要一路比過去；有雜湊表就先算出號碼、直接過去（細節下面一步步拆，點圖可放大） ## 七個名詞就夠 | 名詞 | 白話 | | --- | --- | | **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 倍。 | ## 第一步：用 key 算出櫃號 整篇用同一組例子：**3 個櫃號**（0、1、2），放 3 個 key：A、B、C。假設它們的 hash code 是 **10、7、5**。 同一個 key 每次都算出一樣的數字 → 每次都到同一個櫃號 keyA 雜湊函式C#：GetHashCode() hash code＝ 10 10 % 3 ＝ 1除以櫃號總數，取餘數 三個 key 各算一次（hash code 是假設的） A：10 % 3 ＝ 1 → 櫃號 1 B：　7 % 3 ＝ 1 → 櫃號 1　← 跟 A 同號，碰撞了 C：　5 % 3 ＝ 2 → 櫃號 2 圖 A：key 經過固定公式變成數字，取餘數得到櫃號（點圖可放大） 好的雜湊函式要做到兩件事： - **同一個 key，算出來永遠一樣**：不然放進去的東西就找不回來了。 - **不同的 key 盡量分散**：分得越平均，每個櫃號的東西越少，找得越快。 > 這段在講：包裹店先用名字算出櫃號，就知道去哪找，不用從頭翻。A、B 撞在同一個櫃號是正常的，下一步看它們怎麼放。 ## 第二步：東西怎麼存：櫃台紙條＋倉庫 先想一個問題：**櫃子很小，一格只夾得下一張紙條**，放不下包裹。可是 A 和 B 偏偏都分到 1 號櫃，兩件要擺哪？ 包裹店的做法：**包裹全部放到後面的倉庫**，照到貨順序排（第 0 格、第 1 格…）。櫃台上每個櫃號只夾一張紙條，寫「去倉庫第幾格找」。 照順序放 A、B、C，看紙條和倉庫怎麼變： ① 放 A（櫃號 1） 櫃台紙條 倉庫 櫃 0 — 櫃 1 第 0 格 櫃 2 — [0]A下一件：沒有 （空） （空） A 放第 0 格。 1 號紙條寫「去第 0 格」。 ② 放 B（也是櫃號 1） 櫃台紙條 倉庫 櫃 0 — 櫃 1 第 1 格 櫃 2 — [0]A下一件：沒有 [1]B下一件：第 0 格 （空） B 放第 1 格，貼紙指回 A。 1 號紙條改成「去第 1 格」。 ③ 放 C（櫃號 2） 櫃台紙條 倉庫 櫃 0 — 櫃 1 第 1 格 櫃 2 第 2 格 [0]A下一件：沒有 [1]B下一件：第 0 格 [2]C下一件：沒有 C 放第 2 格。 2 號紙條寫「去第 2 格」。 圖 B0：照順序放 A、B、C，每一步只改橘色那一格（點圖可放大） 1. **放 A**（1 號櫃）：A 放進倉庫第 0 格，1 號紙條寫「去第 0 格」。 2. **放 B**（也是 1 號櫃）：紙條只寫得下一個格號，那 A 怎麼辦？做法是在 B 身上貼一張**貼紙**：「我後面還有一件，在第 0 格」。B 放進第 1 格，再把 1 號紙條改成「去第 1 格」。 3. **放 C**（2 號櫃）：C 放進第 2 格，2 號紙條寫「去第 2 格」。C 後面沒東西，貼紙寫「沒有」。 現在要找 1 號櫃的東西，路線是：紙條說第 1 格 → 拿到 B → B 的貼紙說下一件在第 0 格 → 拿到 A → A 的貼紙寫「沒有」，結束。 這種「一件指到下一件」的排法，就叫一**串**（英文 chaining）；貼紙上的「下一件在哪」叫 **next**，「沒有」在程式裡寫成 −1。B 比 A 晚到卻排在前面，是因為新來的直接插最前面最省事：改一張紙條、寫一張貼紙就好。 三件都放好的樣子就是下面這張表。貼紙上另外還抄了每件的 hash code，下一步查的時候會用到。 櫃台紙條只寫「第一件在倉庫第幾格」 倉庫照到貨順序放；hash code 和 next 寫在貼紙上 櫃號 0 — 櫃號 1 第 1 格 櫃號 2 第 2 格 格 hash code key next [0] 10 A −1 [1] 7 B 0 [2] 5 C −1 next＝0→ 第 0 格 查櫃號 1：紙條寫「第 1 格」→ B → B 的 next＝0 → 第 0 格的 A → A 的 next＝−1，到底。 B 比 A 晚到，卻排在串的最前面。櫃號 0 沒有東西，紙條是空的。 圖 C：放好之後的完整樣子。紙條指到 B，B 的貼紙再指到 A（點圖可放大） 註：在 .NET 原始碼裡，櫃台紙條是一個陣列叫 `_buckets`，倉庫是另一個陣列叫 `_entries`。紙條實際存「格號＋1」好讓 0 代表空的，觀念一樣。 > 這段在講：櫃子太小放不下包裹，所以包裹全放倉庫、櫃台只夾一張「去第幾格」的紙條；同一個櫃號的包裹，靠貼紙上的「下一件在哪」一件接一件。 ## 第三步：查一次：先比貼紙上的數字，一樣才問 Equals 查 `dict[A]` 時，先算出櫃號、看紙條，再沿著串一件件看。每看一件分兩關： 1. **先比貼紙上的 hash code**：兩個整數比一下，很便宜。不一樣就一定不是，直接看下一件。 2. **數字一樣，才呼叫 Equals**：真的核對 key。這可能比較貴，例如要比一長串字。 要查的 key 10 % 3 ＝ 1→ 看櫃號 1 的紙條 櫃台紙條 櫃號 0 — 櫃號 1 第 1 格 櫃號 2 第 2 格 格 hash code key next [0] 10 A −1 [1] 7 B 0 [2] 5 C −1 A（hash code 10） D（hash code 剛好也是 10） ① 查 A：hash code 10，10 % 3 ＝ 1 → 看櫃號 1 的紙條 ② 紙條寫「第 1 格」→ 倉庫第 1 格是 B ③ 先比貼紙：7 ≠ 10，一定不是，不用問 Equals → 照 next＝0 往下 7 ≠ 10，跳過 10＝10，Equals ✓④ 第 0 格是 A：10 ＝ 10，再問 Equals ✓ → 找到 A 10＝10，Equals ✕⑤ 換查 D：跳過 B；到 A 時 10 ＝ 10 但 Equals ✕ → next＝−1，查無 D 圖 B：同一份資料，先查 A、再查 D（動畫會循環，點圖可放大） 注意第 ⑤ 步：**D 和 A 的 hash code 剛好一樣，但不是同一個 key**。數字一樣只代表「可能是」，最後一定要靠 Equals 確認。 > 這段在講：店員找包裹，先看貼紙上的數字，數字對了才核對收件人。hash 負責「快速縮小範圍」，Equals 負責「確定是同一個」，兩個缺一不可。 ## 用自己寫的型別當 key：要告訴 C#「怎樣算一樣」 **背景。**前面的 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 寫得再對，也沒機會上場，所以明明放進去了，卻查不到。 只覆寫 EqualsEquals 和 GetHashCode 都覆寫 兩個 new 出來的 Point(1,2)一個放進去、一個拿來查 兩個 new 出來的 Point(1,2)一個放進去、一個拿來查 GetHashCode 用預設的每個物件自己的號碼 → 兩個數字不同 GetHashCode 用 X、Y 算HashCode.Combine(X, Y) → 兩個數字一樣 比貼紙：數字不同 → 跳過Equals 一次都沒被呼叫 比貼紙：數字一樣 → 呼叫 EqualsX、Y 都相等 ✓ ContainsKey → False（找不到） ContainsKey → True（找到） 圖 F：差別只在 GetHashCode。數字對不上，Equals 根本輪不到（點圖可放大） ### 實驗 1：只覆寫 Equals，Dictionary 找得到嗎？ 準備開一個新資料夾：`mkdir lab-cs && cd lab-cs && dotnet new console`，把 `Program.cs` 整個換成： ``` var d = new Dictionary(); 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 件），就像[上一篇](https://docs.smartech.tw/n/dynamic-array-list-slice)的動態陣列一樣**翻倍**：櫃號變成約 2 倍（.NET 會挑質數，3 → 7）。 每件包裹用貼紙上抄好的 hash code **重新取餘數**，換到新櫃號。偶爾搬一次很貴，平均下來 Add 還是 O(1)，道理跟上一篇一樣。 擴容前：3 個櫃號，倉庫 3 格也滿了櫃號 0櫃號 1櫃號 2BAC2 × 3 ＝ 6挑質數 → 7擴容後：7 個櫃號，重新分櫃號 0B7 % 7 ＝ 0櫃號 1櫃號 2櫃號 3A10 % 7 ＝ 3櫃號 4櫃號 5C5 % 7 ＝ 5櫃號 6用貼紙上抄好的 hash code 重新取餘數，不用再呼叫 GetHashCode。原本擠在櫃號 1 的 A、B 分開了 圖 D：3 個櫃號 → 7 個。同一個 hash code 除以新的櫃號數，原本擠在一起的 A、B 分開了（點圖可放大） > 這段在講：包裹多到倉庫放滿，就換一間兩倍大的店，照貼紙上的數字重新分櫃號，擠在一起的會散開。 ## 什麼時候會變慢：全擠在同一個櫃號 O(1) 有前提：**key 要平均分散**。微軟文件也說查找「接近 O(1)」，快慢取決於雜湊函式的品質。 如果所有 key 都算到同一個櫃號，那一串就有 n 件，每次查都從頭比到尾，變成 **O(n)**。擴容也救不了：hash code 全一樣，櫃號再多也是同一號。 好的 hash：每個櫃號 0～2 件櫃號 0櫃號 1櫃號 2櫃號 3櫃號 4櫃號 5查一次：算櫃號＋比 1～2 件 → O(1)爛的 hash（永遠 return 1）：全擠在櫃號 1櫃號 0櫃號 1櫃號 2櫃號 3櫃號 4櫃號 5…查一次：沿著整串比過去 → O(n) 圖 E：左邊分得平均，查一次只比 1～2 件；右邊全擠一個櫃號，查一次要比整串（點圖可放大） GetHashCode 寫成永遠 `return 1` **是合法的**：相等的 key 數字一樣，這條仍成立。只是全部擠進同一個櫃號。慢多少？自己量。 ### 實驗 2：同樣 20000 個 key，好的 hash vs 爛的 hash 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 = 20000lockers := make([][]int, n) // n 個櫃號，每號一條串longest := 0for 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 次，就換一條壞人猜不到的公式，整張表重排。 > 這段在講：包裹全塞進同一個櫃號，店員就得一件件翻，雜湊表退回「從頭比」。 ### Go map 對照與常見的坑 - **查不到時**：C# `dict[k]` 丟 `KeyNotFoundException`；Go `m[k]` 回傳**零值**（該型別的空白值，int 就是 0），不會出錯。 - **分辨「沒有」和「值剛好是 0」**：Go 寫 `v, ok := m[k]`（這叫 comma-ok，`ok` 就是「有沒有」）；C# 用 `TryGetValue`。 - **Go 的 key 要能用 `==` 比**：slice、map、func 都不能當 key。Go 也不讓你自己寫雜湊函式。 - **別依賴走訪順序**：Go 故意每次打亂；C# 文件說順序沒有保證。 - **key 放進去後別改它**：改了算 hash 的欄位，包裹還在舊櫃號，你卻被帶去新櫃號，找不到。 Go 1.24 起 map 底層改用 [Swiss Tables](https://go.dev/blog/swisstable)，碰撞時不串成一串，但「算位置、直接拿」的想法一樣。 ## ✔ 過關標準 能不看筆記回答下面 5 題，這篇就過了。 1. 櫃台紙條和倉庫各存什麼？A、B 同一個櫃號時怎麼串起來？ **紙條只寫「第一件在倉庫第幾格」，倉庫照到貨順序放包裹。** - 每件包裹的貼紙上有 **hash code** 和 **next**。 - B 晚到排最前：紙條 → B，B 的 next＝0 → A，A 的 next＝−1，到底。 2. 沿著串比對時，為什麼先比 hash code，數字一樣才呼叫 Equals？ **比整數很便宜，不同就一定不是；一樣卻不一定是同一個。** - 數字不同：直接跳過，省下 Equals。 - 數字一樣：可能是碰撞（像 D 和 A），要 Equals 確認。hash 縮小範圍，Equals 確定是同一個。 3. 只覆寫 Equals 會怎樣？為什麼？ **放得進去，卻查不到。** - 預設的 GetHashCode 看「是不是同一個物件」，兩個 `Point(1,2)` 的數字不同。 - Dictionary 先比 hash code，數字不同就跳過，**Equals 根本沒被呼叫**。 - 編譯器會警告 CS0659。修法：`HashCode.Combine`，或直接用 `record`。 4. 擴容後，原本都在櫃號 1 的 A、B 為什麼分開了？ **櫃號總數變了，同一個 hash code 取餘數的結果就變了。** - 10 % 3 和 7 % 3 都是 1；換成 7 個櫃號，10 % 7 ＝ 3、7 % 7 ＝ 0。 5. 什麼情況會從 O(1) 變成 O(n)？擴容救得了嗎？ **大量 key 擠在同一個櫃號時；擴容救不了。** - 原因：GetHashCode 寫爛（例如永遠 return 1），或有人故意灌會碰撞的 key。 - hash code 全一樣，櫃號再多也是同一號，每次查都要比過整串。 ## 參考來源 - [dotnet/runtime — Dictionary.cs](https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Collections/Generic/Dictionary.cs)（\_buckets／\_entries 一樣大、Entry 存 hashCode 與 next、先比 hashCode 再 Equals、新的插在串頭、倉庫滿才擴容、碰撞門檻） - [dotnet/runtime — HashHelpers.cs](https://github.com/dotnet/runtime/blob/main/src/libraries/Common/src/System/Collections/HashHelpers.cs)（ExpandPrime 取 2 倍再找質數、HashCollisionThreshold＝100） - [Microsoft Learn — Dictionary<TKey,TValue>](https://learn.microsoft.com/en-us/dotnet/api/system.collections.generic.dictionary-2)（接近 O(1)、取決於雜湊品質、key 不可變、列舉順序未定義） - [Microsoft Learn — Object.GetHashCode](https://learn.microsoft.com/en-us/dotnet/api/system.object.gethashcode)（相等 ⇒ hash 相同、預設照物件參照、HashCode.Combine、可變物件、惡意碰撞） - [Microsoft Learn — Compiler Warning CS0659](https://learn.microsoft.com/en-us/dotnet/csharp/misc/cs0659)（覆寫 Equals 卻沒覆寫 GetHashCode） - [Microsoft Learn — Records](https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/builtin-types/record)（編譯器自動產生 Equals／GetHashCode） - [The Go Programming Language Specification](https://go.dev/ref/spec)（查不到回傳零值、comma-ok、key 要能用 == 比、走訪順序未指定） - [Go 1 Release Notes](https://go.dev/doc/go1)（故意讓 map 走訪順序不可預測）、[Go blog — Swiss Tables](https://go.dev/blog/swisstable)