雜湊表

🎯 什麼情境該想到我

當你「要用鍵找值，而且不在乎順序」的時候——去重、計數、快取、索引、集合運算。
★ 它是使用頻率最高的資料結構，也因此它的失效模式最值得記住。

⚙️ 怎麼用（機制與 Go 的實際情況）

核心想法

用雜湊函式把「任意鍵」映射成「陣列索引」，於是查找變成一次陣列存取。

key "kais" ──hash──▶ 0x9f3a1c...  ──取模──▶ bucket 7
                                              ↓
                                     buckets[7] = {"kais": 42}

平均 $O(1)$ 的代價是：失去順序，而且最差是 $O(n)$。

兩種碰撞處理

	鏈結法（chaining）	開放定址（open addressing）
做法	同一個 bucket 掛一串	撞到就往後找下一個空位（線性探測／二次探測／雙重雜湊）
負載因子 $\alpha$	可以 > 1	必須 < 1，且超過 ~0.7 就明顯劣化
快取	較差（要跳指標）	較好（連續掃描）
刪除	直接移除	麻煩——要用墓碑標記，否則探測鏈會斷
用者	Java HashMap、早期 Go map	Python dict、Rust HashMap、Go 1.24+ map

★ 負載因子與 rehash

$\alpha =\frac{\text{元素數}}{\text{bucket 數}}$

$\alpha$ 太大 → 碰撞多 → 退化。超過門檻就擴容 + 重新雜湊所有元素（rehash）。

單次 rehash 是 $O(n)$，但因為是倍增，攤還後仍是 $O(1)$——
推導與 堆疊與佇列 的 append 完全相同（等比級數 $1+2+4+\cdots +n<2n$）。

⚠️ 但「攤還 $O(1)$」不代表「延遲穩定」。
某一次插入會觸發整表重建，造成延遲尖峰。對即時系統這是真實問題——
解法是預先 make(map[K]V, n) 指定容量，避免執行期反覆擴容。

★ Go 的 map（2026-09-20 查證官方文件）

版本	實作
Go 1.23 以前	bucket 陣列，每個 bucket 存 8 組 key/value，溢位時鏈接 overflow bucket
Go 1.24 起	改用 Swiss Tables（開放定址家族）。官方回報： “a new builtin map implementation based on Swiss Tables”， 連同其他改動使基準測試 CPU 開銷平均降低 2–3%。 可用 GOEXPERIMENT=noswissmap 退回舊實作

Go map 的四個必知行為：

1. ★ range 的順序是隨機的，而且是刻意的
   Go 故意在每次 range 時隨機化起點，就是為了讓你不能依賴順序。

   // ❌ 不可依賴
   for k, v := range m { ... }
   // ✅ 要固定順序就自己排
   keys := slices.Sorted(maps.Keys(m))   // Go 1.23+

   ★ 很多人是在「本機跑對、CI 跑錯」時才發現這件事。

2. ★ 不是並行安全的
   並行讀寫會直接 panic: concurrent map writes（runtime 主動偵測）。
   要並行用 sync.Map（讀多寫少）或自己加 sync.RWMutex。

   sync.Map 不是萬用替代品——它只在「讀遠多於寫」或「不同 goroutine 操作不相交的鍵」時較快，其他情況比 mutex + map 慢。

3. 不能取元素的位址：&m[k] 編譯錯誤（因為 rehash 會搬動元素）。
   要改結構體欄位得整個取出、改完再放回，或存指標 map[K]*V。

4. 刪除不會縮小 map。大量刪除後記憶體不會還給系統——要釋放就重建一個新 map。

★ 雜湊碰撞攻擊（HashDoS）

如果雜湊函式可預測，攻擊者可以構造大量雜湊值相同的鍵，
讓所有元素擠進同一個 bucket → 查找退化成 $O(n)$ → CPU 100%。

這是真實發生過的攻擊（2011 年多個語言的 Web 框架同時中招，攻擊面是 HTTP 參數解析）。

Go 的防禦：map 的雜湊種子在程式啟動時隨機化，攻擊者無法離線算出碰撞鍵。
→ 也因此 Go map 的迭代順序與雜湊值在不同執行之間都不一樣。

複雜度

操作	平均	最差
查找／插入／刪除	$O(1)$	$O(n)$（全部碰撞）
空間	$O(n)$	—

🧪 我實際套用的紀錄

• （待填）

⚠️ 注意 / 什麼時候不適用

• ★ 不保證順序。需要有序就用 紅黑樹／B 樹（Go 標準庫沒有，用排序過的 slice + 二分搜尋，或第三方 B-tree）。
• ★ 不支援範圍查詢（「所有 key 在 [a,b] 之間的」）——這是雜湊表的結構性限制，有序結構才做得到。
• Go map 並行寫會 panic，不是靜默錯誤。這算是好事（早期發現），但要知道。
• 鍵必須可比較。Go 裡 slice、map、function 不能當 key；struct 若含這些欄位也不行。
• ★ 浮點數當 key 很危險：NaN != NaN，存進去就再也取不出來。
• 自訂雜湊要小心分布。分布不均會讓 $O(1)$ 名存實亡。
• 記憶體開銷比陣列大（bucket 有空位、有 metadata）。$n$ 很小時（< 8 個）線性掃描一個 slice 通常更快也更省。
• 迭代中刪除：Go 允許在 range 中 delete，但新增的元素是否被走訪是未定義的。

🔗 相關工具

• 鏈結串列 —— 碰撞鏈；以及 LRU 快取的另一半
• 堆疊與佇列 —— rehash 攤還分析與 append 完全同源
• 二元搜尋樹、紅黑樹 —— 需要順序或範圍查詢時的替代品
• 計數排序 —— 同樣是「把鍵直接當索引」的思路
• 工具-資料結構的選擇 —— 決策層
• 工具-用trigram索引加速模糊查詢 —— 資料庫端的另一種索引取捨
• 演算法導論