golang-data-structures

角色： 你是一名了解数据结构内部实现的 Go 工程师。你会根据具体需求选择合适的数据结构，而不是选择最熟悉的那个，并会从内存布局、分配成本和访问模式等方面进行推理。

Go 数据结构

内置和标准库数据结构：内部实现、正确用法和选择指南。

• 有关安全隐患（nil map、append 别名、保护性副本），请参阅 samber/cc-skills-golang@golang-safety 技能。
• 有关通道和同步原语，请参阅 samber/cc-skills-golang@golang-concurrency 技能。
• 有关字符串、字节和 rune 的选择，请参阅 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；进行双向 I/O 时必须优先使用 bytes.Buffer（同时实现 io.Reader 和 io.Writer）
6. 泛型数据结构应采用尽可能严格的约束——键使用 comparable，排序使用自定义接口
7. unsafe.Pointer 只能遵循 Go 规范中 6 种有效的转换模式——切勿在多条语句之间将其存储在 uintptr 变量中
8. 缓存和规范化映射应使用 weak.Pointer[T]（Go 1.24+），以便 GC 回收条目

Slice 内部实现

slice 是一个包含 3 个字的头部：指针、长度、容量。多个 slice 可以共享同一个底层数组（→ 有关别名陷阱和头部示意图，请参阅 samber/cc-skills-golang@golang-safety）。

容量增长

• 元素少于 256 个：容量翻倍
• 元素大于等于 256 个：容量增长约 25%（newcap += (newcap + 3*256) / 4）
• 每次增长都会复制整个底层数组——O(n)

预分配

// Exact size known
users := make([]User, 0, len(ids))

// Approximate size known
results := make([]Result, 0, estimatedCount)

// Pre-grow before bulk 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 个条目的桶和溢出链组成的哈希表。它是引用类型——赋值时复制的是指针，而不是数据。

预分配

m := make(map[string]*User, len(users)) // avoids rehashing during population

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           // fixed-size, value type
var grid [3][3]int             // multi-dimensional
cache := map[[2]int]Result{}   // arrays are comparable — usable as map keys

其他情况优先使用 slice——数组无法增长，并且按值传递（较大数组的开销很高）。

container/ 标准库

包	数据结构	最适合的场景
container/list	双向链表	LRU 缓存、频繁在中间插入或删除
container/heap	最小堆（优先级队列）	Top-K、调度、Dijkstra
container/ring	环形缓冲区	滚动窗口、轮询
bufio	缓冲读取器/写入器/扫描器	高效处理小块读写

容器类型使用 any（不提供类型安全）——可考虑使用泛型包装器。容器模式、bufio 和示例 — 介绍每种容器类型的适用场景、用于增加类型安全的泛型包装器，以及高效 I/O 的 bufio 模式。

strings.Builder 与 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+）	缓存、规范化、弱引用	不适用

指针类型深入解析 — 介绍常规指针、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 签名。

• 对于 Go 包文档、符号、版本、导入方和已知漏洞，→ 查看 samber/cc-skills-golang@golang-pkg-go-dev 技能（godig）——查询 Go 包事实时优先使用它，而非 Context7。
• 要在自己的代码中导航此库的用法（定义、调用位置、诊断），→ 查看 samber/cc-skills-golang@golang-gopls 技能（gopls）。
• 对于未在 pkg.go.dev 索引的文档，Context7 仍可作为后备选项。

交叉引用

• → 查看 samber/cc-skills-golang@golang-performance 技能，了解结构体字段对齐、内存布局优化和缓存局部性
• → 查看 samber/cc-skills-golang@golang-safety 技能，了解 nil 映射/切片陷阱、append 别名、防御性复制、slices.Clone/Equal
• → 查看 samber/cc-skills-golang@golang-concurrency 技能，了解通道、sync.Map、sync.Pool 和所有 sync 原语
• → 查看 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 技能，了解切片/映射初始化风格

常见错误

错误	修正方法
在循环中不断扩容切片，却没有预先分配容量	每次扩容都会复制整个底层数组——每次扩容的开销为 O(n)。使用 make([]T, 0, n) 或 slices.Grow
明明切片就够用，却使用 container/list	链表的缓存局部性较差（每个节点都是单独的堆分配）。先进行基准测试
仅用于构建字符串时使用 bytes.Buffer	Buffer 的 String() 会复制底层字节。strings.Builder 可以避免这次复制
在多个语句之间将 unsafe.Pointer 存储为 uintptr	GC 可能在语句之间移动对象——uintptr 会变成悬空引用
在 map 中存储大型结构体值（复制开销）	访问 map 时会复制整个值。对于大型值类型，使用 map[K]*V 来避免复制

参考资料

• Go 数据结构（Russ Cox）
• Go 内存模型
• Effective Go