golang-data-structures

角色設定： 你是一位了解資料結構內部機制的 Go 工程師。你會根據記憶體佈局、分配成本和存取模式來選擇最適合的資料結構，而不是最熟悉的那個。

Go 資料結構

內建與標準函式庫的資料結構：內部機制、正確用法與選擇指南。關於安全性陷阱（nil map、append 別名、防禦性複製）請參閱 samber/cc-skills-golang@golang-safety 技能。關於 channel 與同步原語請參閱 samber/cc-skills-golang@golang-concurrency 技能。關於字串/位元組/符文選擇請參閱 samber/cc-skills-golang@golang-design-patterns 技能。

最佳做法摘要

1. 預先分配 slice 和 map，當大小已知或可估計時使用 make(T, 0, n) / make(map[K]V, n) — 避免重複的成長複製與重新雜湊
2. 陣列 僅在固定、編譯期已知大小的情況下應優先於 slice（例如雜湊摘要、IPv4 位址、矩陣維度）
3. 絕對不要依賴 slice 容量成長的時機 — 成長演算法在不同 Go 版本間已改變且可能再次改變；你的程式碼不應依賴何時分配新的底層陣列
4. 使用 container/heap 實作優先佇列，container/list 僅在需要頻繁中間插入時使用，container/ring 用於固定大小的環形緩衝區
5. strings.Builder 必須優先使用於建構字串；bytes.Buffer 必須優先使用於雙向 I/O（實作 io.Reader 和 io.Writer）
6. 泛型資料結構應使用 最嚴格的約束 — comparable 用於鍵，自訂介面用於排序
7. unsafe.Pointer 只能遵循 Go 規格中的 6 種有效轉換模式 — 絕不要跨陳述式儲存在 uintptr 變數中
8. weak.Pointer[T]（Go 1.24+）應用於快取和正規化 map，讓 GC 可以回收條目

Slice 內部機制

Slice 是一個 3 字元的標頭：指標、長度、容量。多個 slice 可以共享同一個底層陣列（→ 關於別名陷阱和標頭圖表，請參閱 samber/cc-skills-golang@golang-safety）。

容量成長

• < 256 個元素：容量加倍

• = 256 個元素：成長約 25%（newcap += (newcap + 3*256) / 4）

• 每次成長都會複製整個底層陣列 — O(n)

預先分配

// 確切大小已知
users := make([]User, 0, len(ids))

// 近似大小已知
results := make([]Result, 0, estimatedCount)

// 大量 append 前預先成長（Go 1.21+）
s = slices.Grow(s, additionalNeeded)

slices 套件（Go 1.21+）

主要函式：Sort/SortFunc、BinarySearch、Contains、Compact、Grow。關於 Clone、Equal、DeleteFunc → 請參閱 samber/cc-skills-golang@golang-safety 技能。

Slice 內部機制深入探討 — 完整的 slices 套件參考、成長機制、len 與 cap、標頭複製、底層陣列別名。

Map 內部機制

Map 是雜湊表，具有 8 個條目的桶子和溢位鏈。它們是參考型別 — 賦值 map 會複製指標，而非資料。

預先分配

m := make(map[string]*User, len(users)) // 避免在填入時重新雜湊

maps 套件快速參考（Go 1.21+）

函式	用途
Collect (1.23+)	從迭代器建立 map
Insert (1.23+)	從迭代器插入條目
All (1.23+)	迭代所有條目
Keys、Values	迭代鍵/值

關於 Clone、Equal、排序迭代 → 請參閱 samber/cc-skills-golang@golang-safety 技能。

Map 內部機制深入探討 — Go map 如何儲存和雜湊資料、桶子溢位鏈、為何 map 永不縮小（以及如何處理）、比較 map 效能與替代方案。

陣列

固定大小、值型別。賦值時完整複製。用於編譯期已知的大小：

type Digest [32]byte           // 固定大小、值型別
var grid [3][3]int             // 多維
cache := map[[2]int]Result{}   // 陣列是可比較的 — 可作為 map 鍵

其他情況優先使用 slice — 陣列無法成長且按值傳遞（對大型陣列成本高）。

container/ 標準函式庫

套件	資料結構	最佳用途
container/list	雙向鏈結串列	LRU 快取、頻繁的中間插入/移除
container/heap	最小堆積（優先佇列）	Top-K、排程、Dijkstra
container/ring	環形緩衝區	滾動視窗、循環輪詢
bufio	緩衝讀取器/寫入器/掃描器	小量讀寫的高效 I/O

容器型別使用 any（無型別安全）— 考慮使用泛型包裝器。容器模式、bufio 與範例 — 何時使用每種容器型別、加入型別安全的泛型包裝器，以及高效 I/O 的 bufio 模式。

strings.Builder 與 bytes.Buffer 比較

純字串串接使用 strings.Builder（避免 String() 時的複製），需要 io.Reader 或位元組操作時使用 bytes.Buffer。兩者都支援 Grow(n)。詳細資訊與比較

泛型集合（Go 1.18+）

使用最嚴格的約束。comparable 用於 map 鍵，cmp.Ordered 用於排序，自訂介面用於領域特定排序。

type Set[T comparable] map[T]struct{}

func (s Set[T]) Add(v T)          { s[v] = struct{}{} }
func (s Set[T]) Contains(v T) bool { _, ok := s[v]; return ok }

撰寫泛型資料結構 — 使用 Go 1.18+ 泛型實作型別安全的容器、理解約束滿足、建構領域特定的泛型型別。

指標型別

型別	使用情境	零值
*T	一般間接、修改、可選值	nil
unsafe.Pointer	FFI、低階記憶體佈局（僅 6 種規格模式）	nil
weak.Pointer[T] (1.24+)	快取、正規化、弱參考	N/A

指標型別深入探討 — 一般指標、unsafe.Pointer（6 種有效規格模式），以及用於 GC 安全快取（不阻止清理）的 weak.Pointer[T]。

複製語意快速參考

型別	複製行為	獨立性
int、float、bool、string	值（深複製）	完全獨立
array、struct	值（深複製）	完全獨立
slice	標頭複製，底層陣列共享	使用 slices.Clone
map	參考複製	使用 maps.Clone
channel	參考複製	同一個 channel
*T（指標）	位址複製	同一個底層值
interface	值複製（型別 + 值配對）	取決於持有的型別

第三方函式庫

對於標準函式庫之外的進階資料結構（樹、集合、佇列、堆疊）：

• emirpasic/gods — 全面的集合函式庫（樹、集合、串列、堆疊、map、佇列）
• deckarep/golang-set — 執行緒安全與非執行緒安全的集合實作
• gammazero/deque — 快速的雙端佇列

使用第三方函式庫時，請參考其官方文件和程式碼範例以取得最新的 API 簽名。Context7 可作為探索平台提供協助。關於 Go 套件文件、版本、符號和已知漏洞 → 請參閱 samber/cc-skills-golang@golang-pkg-go-dev 技能。

交叉參考

• → 請參閱 samber/cc-skills-golang@golang-performance 技能了解結構欄位對齊、記憶體佈局最佳化和快取區域性
• → 請參閱 samber/cc-skills-golang@golang-safety 技能了解 nil map/slice 陷阱、append 別名、防禦性複製、slices.Clone/Equal
• → 請參閱 samber/cc-skills-golang@golang-concurrency 技能了解 channel、sync.Map、sync.Pool 和所有同步原語
• → 請參閱 samber/cc-skills-golang@golang-design-patterns 技能了解 string 與 []byte 與 []rune、迭代器、串流
• → 請參閱 samber/cc-skills-golang@golang-structs-interfaces 技能了解結構組合、嵌入和泛型與 any
• → 請參閱 samber/cc-skills-golang@golang-code-style 技能了解 slice/map 初始化風格

常見錯誤

錯誤	修正
在迴圈中成長 slice 但未預先分配	每次成長都會複製整個底層陣列 — 每次成長 O(n)。使用 make([]T, 0, n) 或 slices.Grow
使用 container/list 但 slice 就足夠	鏈結串列快取區域性差（每個節點是獨立的堆積分配）。先進行基準測試
純字串建構使用 bytes.Buffer	Buffer 的 String() 會複製底層位元組。strings.Builder 避免此複製
unsafe.Pointer 跨陳述式儲存為 uintptr	GC 可能在陳述式之間移動物件 — uintptr 變成懸空參考
map 中的大型結構值（複製開銷）	Map 存取會複製整個值。對大型值型別使用 map[K]*V 以避免複製

參考資料

• Go Data Structures (Russ Cox)
• The Go Memory Model
• Effective Go