golang-data-structures

角色： 你是一位理解数据结构内部机制的 Go 工程师。你通过推理内存布局、分配成本和访问模式，为任务选择正确的结构——而不是最熟悉的结构。

Go 数据结构

内置和标准库数据结构：内部机制、正确用法和选择指南。关于安全陷阱（nil 映射、追加别名、防御性复制）请参见 samber/cc-skills-golang@golang-safety 技能。关于通道和同步原语请参见 samber/cc-skills-golang@golang-concurrency 技能。关于字符串/字节/符文选择请参见 samber/cc-skills-golang@golang-design-patterns 技能。

最佳实践总结

1. 预分配切片和映射，当大小已知或可估计时使用 make(T, 0, n) / make(map[K]V, n)——避免重复的增长复制和重新哈希
2. 数组 仅应在固定、编译时已知大小（哈希摘要、IPv4 地址、矩阵维度）时优先于切片使用
3. 永远不要依赖切片容量增长时机——增长算法在不同 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+）应用于缓存和规范化映射，以允许 GC 回收条目

切片内部机制

切片是一个 3 字头：指针、长度、容量。多个切片可以共享一个底层数组（→ 关于别名陷阱和头图，请参见 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)

// 批量追加前预增长（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 技能。

切片内部机制深入探讨 — 完整的 slices 包参考、增长机制、len vs cap、头复制、底层数组别名。

映射内部机制

映射是带有 8 条目桶和溢出链的哈希表。它们是引用类型——赋值映射复制指针，而不是数据。

预分配

m := make(map[string]*User, len(users)) // 避免填充期间重新哈希

maps 包快速参考（Go 1.21+）

函数	用途
Collect (1.23+)	从迭代器构建映射
Insert (1.23+)	从迭代器插入条目
All (1.23+)	遍历所有条目
Keys、Values	遍历键/值

关于 Clone、Equal、排序遍历 → 请参见 samber/cc-skills-golang@golang-safety 技能。

映射内部机制深入探讨 — Go 映射如何存储和哈希数据、桶溢出链、为什么映射从不收缩（以及如何处理）、比较映射性能与替代方案。

数组

固定大小，值类型。赋值时完全复制。用于编译时已知大小：

type Digest [32]byte           // 固定大小，值类型
var grid [3][3]int             // 多维
cache := map[[2]int]Result{}   // 数组是可比较的——可用作映射键

其他情况优先使用切片——数组不能增长且按值传递（大尺寸时开销大）。

container/ 标准库

包	数据结构	最佳用途
container/list	双向链表	LRU 缓存、频繁的中间插入/删除
container/heap	最小堆（优先队列）	Top-K、调度、Dijkstra
container/ring	循环缓冲区	滚动窗口、轮询
bufio	带缓冲的读写器/扫描器	小读写的高效 I/O

容器类型使用 any（无类型安全）——考虑泛型包装器。容器模式、bufio 和示例 — 何时使用每种容器类型、添加类型安全的泛型包装器、以及高效 I/O 的 bufio 模式。

strings.Builder vs bytes.Buffer

使用 strings.Builder 进行纯字符串拼接（避免 String() 时的复制），当需要 io.Reader 或字节操作时使用 bytes.Buffer。两者都支持 Grow(n)。详细信息和比较

泛型集合（Go 1.18+）

使用最严格的约束。comparable 用于映射键，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	引用复制	同一通道
*T（指针）	地址复制	同一底层值
interface	值复制（类型+值对）	取决于持有的类型

第三方库

对于标准库之外的高级数据结构（树、集合、队列、栈）：

• emirpasic/gods — 全面的集合库（树、集合、列表、栈、映射、队列）
• 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 映射/切片陷阱、追加别名、防御性复制、slices.Clone/Equal
• → 请参见 samber/cc-skills-golang@golang-concurrency 技能，了解通道、sync.Map、sync.Pool 和所有同步原语
• → 请参见 samber/cc-skills-golang@golang-design-patterns 技能，了解 string vs []byte vs []rune、迭代器、流式处理
• → 请参见 samber/cc-skills-golang@golang-structs-interfaces 技能，了解结构体组合、嵌入和泛型 vs any
• → 请参见 samber/cc-skills-golang@golang-code-style 技能，了解切片/映射初始化风格

常见错误

错误	修复
在循环中增长切片而不预分配	每次增长复制整个底层数组——每次增长 O(n)。使用 make([]T, 0, n) 或 slices.Grow
使用 container/list 而切片就足够	链表缓存局部性差（每个节点是单独的堆分配）。先基准测试
使用 bytes.Buffer 进行纯字符串构建	Buffer 的 String() 复制底层字节。strings.Builder 避免此复制
将 unsafe.Pointer 作为 uintptr 跨语句存储	GC 可能在语句之间移动对象——uintptr 成为悬空引用
映射中的大结构体值（复制开销）	映射访问复制整个值。对大值类型使用 map[K]*V 以避免复制

参考

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