🎯 什麼情境該想到我
分工：這張是「選哪個結構」的決策卡。每個結構的內部機制、複雜度推導、Go 實作細節 →
reference/演算法導論/（雜湊表、二元堆積、紅黑樹、堆疊與佇列、鏈結串列、併查集）。
當你要決定「一堆資料該用什麼結構存」，或發現查找/插入很慢時。選對結構，效能天差地別。
⚙️ 怎麼用（依「主要操作」選）
- 常隨機存取、少增刪 → 陣列（O(1) 索引）。
- 常在中間插入/刪除 → 鏈結串列。
- 常用鍵查值 / 去重 → 雜湊表（平均 O(1)）。
- 需要保持有序 + 範圍查詢 → 平衡樹 / 有序結構（O(log n)）。
- 常取最大/最小 → 堆積（Heap / 優先佇列）。
- 關係/連通/最短路 → 圖。
先問：這份資料最常做哪個操作？ 那個操作要快，就選對應結構。
★ Go 裡的實際對照表
Go 標準函式庫沒有內建的有序 map、樹、集合型別。實際可用的選項：
| 需求 | Go 的做法 | 備註 |
|---|---|---|
| 有序、按索引存取 | []T | 預設選擇。連續記憶體，快取友善 |
| 用鍵查值 | map[K]V | 走訪順序刻意隨機，不要依賴 |
| 集合（去重） | map[T]struct{} | struct{} 不佔空間 |
| 有序 + 範圍查詢 | 排序好的 slice + slices.BinarySearch | 讀多寫少時最實用；插入是 O(n) 的搬移 |
| 有序 + 頻繁插入刪除 | 第三方 B-tree（如 github.com/google/btree） | 標準函式庫沒有 |
| 取最小／最大 | container/heap（實作 5 個方法的介面） | 優先佇列、Top-K、Dijkstra |
| FIFO 佇列 | slice（q = q[1:]）或 channel（跨 goroutine 時） | q[1:] 不會釋放前面的記憶體，長期運作的佇列要定期重新配置或用環形緩衝區 |
| 雙向鏈結串列 | container/list | 幾乎永遠不該用：每個節點獨立配置、快取極不友善（見 鏈結串列） |
TS 對應：Array、Map（保留插入順序）、Set；沒有內建堆積，需要自己寫或用套件。用 Map 而不是一般物件當字典——物件會繼承原型上的鍵，也只能用字串當鍵。
★ 小資料量時，Big-O 會說謊
Big-O 只描述「n 很大時」的趨勢。n 很小時，常數與記憶體存取模式才是主角。實測（Apple M4、Go 1.26.4，字串鍵、查詢都命中，2026-09-25）：
| n | slice 線性搜尋 | 排序 slice + 二分搜尋 | map |
|---|---|---|---|
| 4 | 4.6 ns | 8.7 ns | 6.1 ns |
| 8 | 7.9 ns | 11.4 ns | 7.5 ns |
| 16 | 14.0 ns | 14.9 ns | 5.3 ns |
| 64 | 53.0 ns | 18.9 ns | 5.6 ns |
| 1024 | 627 ns | 30.9 ns | 5.4 ns |
讀法：
- n ≤ 8 左右，線性搜尋和 map 打平甚至更快——不用為了 5 個元素建 map。
- map 的查詢時間幾乎不隨 n 變（O(1) 的實際樣子）；線性搜尋隨 n 線性上升（O(n)）；二分搜尋緩慢上升（O(log n)）。
- 交叉點會隨鍵的型別、CPU、快取狀態移動，所以要自己量，不要背數字。
★ 選擇的決策順序
- 最常做的操作是什麼？ 查、插、刪、排序、取極值、範圍查詢。
- 資料量級？ 小於幾十個 → 幾乎用什麼都行，選最簡單的（通常是 slice）。
- 讀寫比例？ 讀遠多於寫 → 可以接受寫入慢的結構（排序 slice），換取查詢快又省記憶體。
- 需要有序嗎？ Go 的 map 不保證順序；需要穩定輸出（例如產生 JSON、測試比對）時，先把鍵取出來排序：
slices.Sorted(maps.Keys(m))。 - 會被多個 goroutine 同時存取嗎？ 內建 map 不是併發安全的，同時讀寫會直接讓程式 fatal error。加
sync.RWMutex，或在「寫一次、讀很多次」的情況用sync.Map。
🧪 我實際套用的紀錄
- 2026-07-15：（待填）
⚠️ 注意
-
選擇是「操作頻率」的取捨，沒有全能結構；查得快的常插得慢，反之亦然。
-
記憶體也是成本：map 每個條目有額外的桶與中繼資料開銷；存一億個小整數時，排序 slice 可能只用 map 的幾分之一記憶體。選結構時要同時看時間與空間（見 工具-時間複雜度分析）。
🔗 相關工具
- 工具-時間複雜度分析、工具-儲存引擎B-Tree與LSM-Tree（DB 層的資料結構取捨）