go-data-structures

Go 数据结构

切片和映射看起来简单，却藏着 Go 语言中最棘手的问题。 这些规则可以避免那些即使经过代码审查仍会遗留下来的别名、nil 和迭代错误。

按需加载的详细参考资料：

• references/containers.md — container/heap 优先级队列、使用 container/list 实现的 LRU、回收映射内存、weak.Pointer 缓存。

只有当以下摘要不够用时，才阅读参考文件。

1. nil 切片与空切片

var a []int          // nil slice — len 0, cap 0, no allocation
b := []int{}         // empty slice — len 0, allocated header
c := make([]int, 0)  // empty slice — same as b

• len、cap、range 和 append 对这三者的处理完全相同。
• 优先使用 nil 切片表示“没有元素”；不要仅仅为了返回“空”而分配内存。
• 例外：JSON。使用 encoding/json 时，nil 会编码为 null，空切片会编码为 []；如果接口约定要求返回 []，就返回空切片。Go 1.27 的 encoding/json/v2 API 默认会将 nil 编码为 []。
• 逻辑中绝不要区分 nil 和空切片——检查 len(s) == 0。

2. append 语义与别名

append 可能返回同一个底层数组，也可能返回一个新数组。这两种情况都可能引发问题：

// ❌ Bad — result may alias the input
func addSuffix(base []string) []string {
    return append(base, "suffix") // if cap(base) > len(base),
}                                 // this WRITES INTO base's array

// ✅ Good — force a copy when the input must not be touched
func addSuffix(base []string) []string {
    out := make([]string, len(base), len(base)+1)
    copy(out, base)
    return append(out, "suffix")
}

// ❌ Bad — subslice keeps the whole 64 MB alive
func header(big []byte) []byte {
    return big[:512] // backing array is still the full big
}

// ✅ Good — copy the window you keep
func header(big []byte) []byte {
    return slices.Clone(big[:512]) // Go 1.21+; or copy() manually
}

规则：函数要么拥有切片，要么复制切片。返回调用方切片的子切片，或向其追加内容，都会在不知不觉间共享内存。

3. 预分配

如果最终大小已知或有上限，就一次性分配：

// ✅ Good — one allocation
names := make([]string, 0, len(users))
for _, u := range users {
    names = append(names, u.Name)
}

// ❌ Bad — repeated growth and copying
var names []string
for _, u := range users {
    names = append(names, u.Name)
}

映射也一样：make(map[string]int, len(items))。 大小未知时不要预分配——错误地设置过大的容量会浪费内存；在低频路径中，让 append 自动扩容即可。

4. 映射要点

// Comma-ok distinguishes "missing" from "zero value"
count, ok := hits[key]
if !ok { /* key absent */ }

// Zero value reads are safe; writes to a nil map PANIC
var m map[string]int
_ = m["x"]      // 0, fine
m["x"] = 1      // panic: assignment to entry in nil map — make() first

// Iteration order is RANDOM and differs between runs.
// Sort keys when output must be deterministic:
keys := slices.Sorted(maps.Keys(m)) // Go 1.23+
for _, k := range keys {
    fmt.Println(k, m[k])
}

• 映射中的值不可寻址：对于结构体值，m[k].Field = v 无法编译。应使用指针映射，或采用读取—修改—写回的方式。
• 在 range 期间删除元素是安全的；在 range 期间插入元素则未作规定（新键可能会被遍历到，也可能不会）。

5. 集合

惯用的集合是值为零大小结构体的映射：

seen := make(map[string]struct{}, len(items))
for _, it := range items {
    if _, dup := seen[it.ID]; dup {
        continue
    }
    seen[it.ID] = struct{}{}
    process(it)
}

struct{} 占用零字节；map[string]bool 也可用，而且如果要通过 if seen[id] 检查成员资格，读起来更直观。

6. 数组与切片

• 数组（[4]byte）是值：赋值和传递都会复制整个数组。若元素可比较，则可用 == 比较。
• 对于需要值语义的固定大小数据，使用数组：哈希值 （[32]byte）、IPv4 地址、固定矩阵、映射键。
• 其他情况都使用切片。接收 [100]int 的函数每次调用都会复制 800 字节——几乎总是不合适。

7. 选择数据结构

需求	使用
有序、可增长的集合	[]T
成员检查／去重	map[K]struct{}
键→值查找	map[K]V
固定大小、值语义、可比较	[N]T 数组
FIFO 队列（单个 goroutine）	带头部索引的切片；频繁增删时使用 container/list
栈	切片 + append / s[:len(s)-1]
并发映射，键只写一次、读取多次	sync.Map——否则使用互斥锁 + 映射
优先级队列、Top-K、调度器	container/heap
固定大小的滚动窗口	将切片用作环形缓冲区（索引取模 len），或使用 container/ring
LRU 缓存	map[K]*list.Element + container/list
不应让值保持存活的缓存	map[K]weak.Pointer[V]（Go 1.24+）
对大量相同字符串去重	unique.Make（Go 1.23+）
自定义哈希表的键类型	maphash.Comparable / maphash.Hasher（1.24 / 1.27）

sync.Map 是一种适用于特殊情况的工具（只追加的缓存、不相交的键集合）。默认使用 map + sync.RWMutex；锁定模式请参阅并发技能文档。

8. 内存行为

• 映射永远不会缩小。 delete 和 clear 会保留桶。映射曾经容纳数百万个条目，如今大部分为空时，重新构建它（m = maps.Clone(m)）以释放内存。
• clear(s) 会将切片元素清零，但保留其长度；s = s[:0] 会保留底层数组以便复用。两者都不会释放内存。
• 从指针切片中弹出元素——将腾出的槽位置为 nil（s[n-1] = nil），否则 GC 仍会认为该对象可达。
• strings.Builder 构建字符串时无需最终复制；写入后不得复制它。bytes.Buffer 用于面向字节的 I/O（它同时是 io.Reader 和 io.Writer）；其 String() 会进行复制。

9. 复制语义

类型	赋值时复制的内容	独立副本
基本类型、数组、值组成的结构体	所有内容	本身已独立
切片	头部（ptr、len、cap）	slices.Clone
映射	引用	maps.Clone（浅复制）
指针、通道、函数	引用	—
接口	类型 + 值字	取决于动态类型

克隆是浅复制：克隆后的 []*User 仍与原切片共享每一个 User。 第 7-9 节的示例：references/containers.md。

验证清单

1. 没有逻辑区分 nil 切片和空切片；使用 len() 判断是否为空
2. JSON 切片在契约要求为 [] 时，显式初始化为空（而不是 nil）
3. 不向函数不拥有的切片执行 append；显式创建副本
4. 不对大型数组创建长期存续的子切片，除非使用 slices.Clone/copy
5. 已知容量时，预分配切片和映射
6. 当“缺失”与零值不同时，使用 comma-ok
7. 不向可能为 nil 的映射写入
8. 确定性输出路径在遍历映射前先对键排序
9. 使用 map[K]struct{} 构建集合（为便于阅读，也可使用 map[K]bool）
10. 仅在需要值语义或可比较性时使用数组
11. 大幅缩小的长期存续映射应重新构建，而不只是删除其中的条目
12. 优先队列和 LRU 使用 container/heap / container/list，而非临时排序