跳到主要内容

Go 数据结构

本章将深入介绍 Go 语言中的核心数据结构：数组、切片和映射。理解这些数据结构的内部原理和使用场景，对于编写高效的 Go 程序至关重要。

数据结构概述​

Go 语言提供了三种主要的容器类型来存储元素集合：

类型特点适用场景
数组固定长度、值类型已知固定数量的元素
切片动态长度、引用类型大多数场景，最常用
映射键值对、引用类型需要快速查找的场景

数组​

数组是具有固定长度且元素类型相同的序列。在 Go 中，数组的长度是类型的一部分，这意味着 [5]int 和 [10]int 是完全不同的类型。

数组的内部结构​

数组在内存中是连续存储的，每个元素占用相同大小的空间。这种连续存储方式使得数组具有以下特点：

  • O(1) 时间复杂度的随机访问：可以通过索引直接计算出元素的内存地址
  • 缓存友好：连续内存布局对 CPU 缓存友好，遍历效率高
  • 内存效率高：没有额外的指针开销
数组内存布局示意：

内存地址:  1000    1004    1008    1012    1016
          ┌───────┬───────┬───────┬───────┬───────┐
索引:     │   0   │   1   │   2   │   3   │   4   │
          └───────┴───────┴───────┴───────┴───────┘
元素:        10      20      30      40      50

数组声明与初始化​

// 声明数组（元素为零值）
var arr1 [5]int           // [0 0 0 0 0]

// 声明并初始化全部元素
arr2 := [5]int{1, 2, 3, 4, 5}

// 让编译器推断长度
arr3 := [...]int{1, 2, 3, 4, 5}  // 长度为 5

// 指定索引初始化（未指定的元素为零值）
arr4 := [5]int{1: 10, 3: 30}     // [0 10 0 30 0]

// 混合初始化
arr5 := [5]int{10, 20, 3: 30}    // [10 20 0 30 0]

数组是值类型​

这是 Go 数组最重要的特性之一。当数组赋值给新变量或作为参数传递时，会复制整个数组：

func modifyArray(arr [3]int) {
    arr[0] = 100  // 修改的是副本
}

func main() {
    original := [3]int{1, 2, 3}
    
    // 赋值复制整个数组
    copy := original
    copy[0] = 99
    fmt.Println(original)  // [1 2 3] - 原数组不变
    fmt.Println(copy)      // [99 2 3]
    
    // 函数参数传递也是复制
    modifyArray(original)
    fmt.Println(original)  // [1 2 3] - 原数组不变
}

为什么这样设计？

值语义使得数组的行为可预测，避免了意外的副作用。当你传递数组给函数时，可以确信原数组不会被修改。但这种设计也有代价：大数组的复制开销较大。

数组指针​

如果需要在函数中修改原数组，可以传递数组指针：

func modifyArrayPtr(arr *[3]int) {
    arr[0] = 100  // 通过指针修改原数组
}

func main() {
    original := [3]int{1, 2, 3}
    modifyArrayPtr(&original)
    fmt.Println(original)  // [100 2 3] - 原数组被修改
}

数组遍历​

arr := [5]int{10, 20, 30, 40, 50}

// 方式一：传统 for 循环
for i := 0; i < len(arr); i++ {
    fmt.Printf("arr[%d] = %d\n", i, arr[i])
}

// 方式二：for range（推荐）
for index, value := range arr {
    fmt.Printf("arr[%d] = %d\n", index, value)
}

// 只需要值时
for _, value := range arr {
    fmt.Println(value)
}

// 只需要索引时
for index := range arr {
    fmt.Println(index)
}

range 的注意事项：

range 返回的 value 是元素的副本，修改它不会影响原数组：

arr := [3]int{1, 2, 3}
for _, value := range arr {
    value *= 2  // 只修改了副本
}
fmt.Println(arr)  // [1 2 3] - 原数组不变

// 正确的修改方式
for i := range arr {
    arr[i] *= 2
}
fmt.Println(arr)  // [2 4 6]

多维数组​

// 声明二维数组
var matrix [3][3]int

// 初始化
matrix = [3][3]int{
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9},
}

// 遍历
for i := 0; i < 3; i++ {
    for j := 0; j < 3; j++ {
        fmt.Printf("%d ", matrix[i][j])
    }
    fmt.Println()
}

数组的局限性​

数组的主要局限性在于固定长度，这限制了它的使用场景：

// 无法动态添加元素
arr := [3]int{1, 2, 3}
// arr[3] = 4  // 编译错误：索引越界

// 无法删除元素
// 数组长度是类型的一部分，无法改变

// 不同长度的数组是不同类型
func process(arr [5]int) {}
// process([3]int{1, 2, 3})  // 编译错误：类型不匹配

切片​

切片是对底层数组的一个引用，提供了更灵活、更强大的序列操作能力。切片是 Go 中最常用的数据结构。

切片的内部结构​

切片由三个部分组成，称为切片头（slice header）：

// 切片的内部结构（reflect.SliceHeader）
type SliceHeader struct {
    Data uintptr  // 指向底层数组的指针
    Len  int      // 切片长度（元素个数）
    Cap  int      // 切片容量（底层数组的大小）
}
切片结构示意：

切片变量 s
┌─────────────────────────────────────────┐
│  Data ──────────────────┐               │
│  Len  = 5               │               │
│  Cap  = 10              │               │
└─────────────────────────│───────────────┘
                          ▼
底层数组: ┌────┬────┬────┬────┬────┬────┬────┬────┬────┬────┐
         │ 1  │ 2  │ 3  │ 4  │ 5  │ 6  │ 7  │ 8  │ 9  │ 10 │
         └────┴────┴────┴────┴────┴────┴────┴────┴────┴────┘
           ↑    ↑    ↑    ↑    ↑
           │    │    │    │    │
           └────┴────┴────┴────┴──── 切片 s 引用的范围 (Len=5)
           └───────────────────────── 底层数组总大小 (Cap=10)

切片声明与创建​

// 方式一：声明 nil 切片
var s1 []int           // nil，没有底层数组
fmt.Println(s1 == nil) // true

// 方式二：切片字面量
s2 := []int{1, 2, 3, 4, 5}

// 方式三：make 函数
s3 := make([]int, 5)        // len=5, cap=5
s4 := make([]int, 3, 10)    // len=3, cap=10

// 方式四：从数组创建
arr := [5]int{1, 2, 3, 4, 5}
s5 := arr[1:4]    // [2 3 4]
s6 := arr[:3]     // [1 2 3]
s7 := arr[2:]     // [3 4 5]
s8 := arr[:]      // [1 2 3 4 5]

nil 切片 vs 空切片​

// nil 切片
var s1 []int
fmt.Println(s1 == nil)  // true
fmt.Println(len(s1))    // 0
fmt.Println(cap(s1))    // 0

// 空切片（不是 nil）
s2 := []int{}
fmt.Println(s2 == nil)  // false
fmt.Println(len(s2))    // 0
fmt.Println(cap(s2))    // 0

s3 := make([]int, 0)
fmt.Println(s3 == nil)  // false

实际影响：

在 JSON 序列化时，nil 切片编码为 null，空切片编码为 []。

切片是引用类型​

切片传递时不会复制底层数组，多个切片可以共享同一个底层数组：

func main() {
    arr := [5]int{1, 2, 3, 4, 5}
    
    // 两个切片共享同一个底层数组
    s1 := arr[0:3]  // [1 2 3]
    s2 := arr[2:5]  // [3 4 5]
    
    // 修改 s1 会影响 s2
    s1[2] = 100
    fmt.Println(s1)  // [1 2 100]
    fmt.Println(s2)  // [100 4 5] - s2 也被修改了！
}

理解切片共享：

修改前:
arr:  [1, 2, 3, 4, 5]
s1:   [1, 2, 3]        (索引 0-2)
s2:         [3, 4, 5]  (索引 2-4)

修改 s1[2] = 100 后:
arr:  [1, 2, 100, 4, 5]
s1:   [1, 2, 100]
s2:         [100, 4, 5]

append 函数​

append 是向切片添加元素的核心函数：

// 基本用法
s := []int{1, 2, 3}
s = append(s, 4)        // [1 2 3 4]
s = append(s, 5, 6, 7)  // [1 2 3 4 5 6 7]

// 追加另一个切片
s2 := []int{8, 9}
s = append(s, s2...)    // [1 2 3 4 5 6 7 8 9]

append 的工作原理：

  1. 如果容量足够，直接在底层数组末尾添加元素
  2. 如果容量不足，分配新的底层数组，复制旧元素，再添加新元素
s := make([]int, 0, 3)  // len=0, cap=3

s = append(s, 1)  // len=1, cap=3（容量足够，不扩容）
s = append(s, 2)  // len=2, cap=3
s = append(s, 3)  // len=3, cap=3（刚好用完容量）
s = append(s, 4)  // len=4, cap=6（容量不足，扩容）

fmt.Printf("len=%d, cap=%d\n", len(s), cap(s))

扩容机制​

Go 切片的扩容规则（Go 1.18+）：

  1. 如果新容量是当前容量的两倍以内，直接扩容到两倍
  2. 如果新容量超过当前容量的两倍，直接使用新容量
  3. 当容量超过 256 时，采用更平滑的增长公式
// 观察扩容过程
s := make([]int, 0)
for i := 0; i < 20; i++ {
    fmt.Printf("len=%2d cap=%2d\n", len(s), cap(s))
    s = append(s, i)
}

扩容后底层数组会改变：

arr := [5]int{1, 2, 3, 4, 5}
s := arr[0:3]  // [1 2 3]

// 扩容前，s 和 arr 共享底层数组
fmt.Printf("%p\n", &s[0])  // 与 arr[0] 地址相同

s = append(s, 6, 7, 8)  // 触发扩容

// 扩容后，s 指向新的底层数组
fmt.Printf("%p\n", &s[0])  // 新地址
fmt.Println(arr)           // [1 2 3 4 5] - 原数组不变

copy 函数​

copy 用于在切片之间复制元素：

src := []int{1, 2, 3, 4, 5}
dst := make([]int, len(src))

// 复制元素
n := copy(dst, src)
fmt.Println(n, dst)  // 5 [1 2 3 4 5]

// 部分复制
small := make([]int, 2)
copy(small, src)
fmt.Println(small)  // [1 2]

// 重叠复制（安全的）
s := []int{1, 2, 3, 4, 5}
copy(s[0:3], s[2:5])
fmt.Println(s)  // [3 4 5 4 5]

切片操作技巧​

s := []int{1, 2, 3, 4, 5}

// 删除元素（索引 i）
i := 2
s = append(s[:i], s[i+1:]...)  // [1 2 4 5]

// 删除首元素
s = s[1:]  // [2 4 5]

// 删除尾元素
s = s[:len(s)-1]  // [2 4]

// 在索引 i 处插入元素 x
i, x := 1, 100
s = append(s[:i], append([]int{x}, s[i:]...)...)  // [2 100 4]

// 清空切片（保留底层数组）
s = s[:0]  // len=0, cap 不变

// 完全清空（释放底层数组）
s = nil

切片表达式​

Go 支持两种切片表达式：

arr := [5]int{1, 2, 3, 4, 5}

// 简单切片表达式
s1 := arr[1:4]   // [2 3 4]
s2 := arr[:3]    // [1 2 3]
s3 := arr[2:]    // [3 4 5]

// 完整切片表达式（限制容量）
// arr[low:high:max]  // len = high-low, cap = max-low
s4 := arr[1:4:4]  // [2 3 4], len=3, cap=3

// 完整切片表达式的用途：防止意外修改
s5 := arr[1:3]     // len=2, cap=4（可以访问 arr[3], arr[4]）
s5 = append(s5, 0) // 会修改 arr[3]

s6 := arr[1:3:3]   // len=2, cap=2（容量限制）
s6 = append(s6, 0) // 会扩容，不会影响 arr

映射（Map）​

映射是键值对的无序集合，基于哈希表实现。它提供了 O(1) 平均时间复杂度的查找、插入和删除操作。

映射的内部结构​

Go 的 map 使用哈希表实现，主要包含：

  • 哈希函数：将键映射到桶
  • 桶数组：存储键值对
  • 溢出桶：处理哈希冲突
Map 结构示意：

┌─────────────────────────────────────────────────────────────┐
│                         Map                                  │
│  ┌─────────────────────────────────────────────────────┐    │
│  │ 哈希函数: hash(key) -> bucket_index                  │    │
│  └─────────────────────────────────────────────────────┘    │
│                                                              │
│  桶数组:                                                     │
│  ┌───────┬───────┬───────┬───────┬───────┬───────┐         │
│  │桶 0   │桶 1   │桶 2   │桶 3   │...    │桶 n   │         │
│  └───┬───┴───┬───┴───────┴───────┴───────┴───────┘         │
│      │       │                                              │
│      ▼       ▼                                              │
│   ┌─────┐ ┌─────┐                                           │
│   │k1:v1│ │k2:v2│  每个桶存储多个键值对                      │
│   │k3:v3│ │k4:v4│                                           │
│   └──┬──┘ └─────┘                                           │
│      │                                                       │
│      ▼ (溢出桶，处理冲突)                                    │
│   ┌─────┐                                                    │
│   │k5:v5│                                                    │
│   └─────┘                                                    │
└─────────────────────────────────────────────────────────────┘

映射声明与创建​

// 方式一：声明 nil map
var m1 map[string]int
fmt.Println(m1 == nil)  // true
// m1["a"] = 1  // panic: 赋值给 nil map

// 方式二：map 字面量
m2 := map[string]int{
    "apple":  5,
    "banana": 3,
    "orange": 8,
}

// 方式三：make 函数
m3 := make(map[string]int)       // 空 map
m4 := make(map[string]int, 100)  // 预分配容量

基本操作​

m := make(map[string]int)

// 添加元素
m["apple"] = 5
m["banana"] = 3

// 获取元素
count := m["apple"]  // 5

// 获取元素并检查是否存在
count, exists := m["apple"]
if exists {
    fmt.Println("apple:", count)
}

// 删除元素
delete(m, "banana")

// 获取长度
fmt.Println(len(m))

// 遍历（顺序随机）
for key, value := range m {
    fmt.Printf("%s: %d\n", key, value)
}

检查键是否存在​

这是 map 使用中最重要的技巧：

m := map[string]int{"a": 1, "b": 2}

// 错误方式：无法区分"键不存在"和"键存在但值为零值"
value := m["c"]  // 返回 0（int 的零值）
// 无法判断 "c" 是否存在

// 正确方式：使用 comma-ok 模式
value, ok := m["c"]
if ok {
    fmt.Println("存在:", value)
} else {
    fmt.Println("不存在")
}

// 常见模式
if value, ok := m["key"]; ok {
    // 使用 value
}

映射是引用类型​

func modifyMap(m map[string]int) {
    m["new"] = 100
}

func main() {
    m := map[string]int{"a": 1}
    modifyMap(m)
    fmt.Println(m)  // map[a:1 new:100] - 原映射被修改
}

映射的键类型限制​

映射的键必须是可比较的类型：

// 可以作为键的类型
m1 := map[int]string{}           // 基本类型
m2 := map[string]int{}           // 字符串
m3 := map[[3]int]string{}        // 数组
m4 := map[struct{x int}]int{}    // 结构体

// 不能作为键的类型
// m5 := map[[]int]int{}         // 切片（不可比较）
// m6 := map[map[string]int]int{} // 映射（不可比较）
// m7 := map[func()]int{}        // 函数（不可比较）

线程安全问题​

Go 的 map 不是并发安全的，并发读写会导致 panic：

// 错误：并发读写会 panic
var m = make(map[int]int)

go func() {
    m[1] = 1  // 写
}()

go func() {
    _ = m[1]  // 读
}()

// 正确方式一：使用互斥锁
var (
    mu sync.RWMutex
    m  = make(map[int]int)
)

func read(key int) int {
    mu.RLock()
    defer mu.RUnlock()
    return m[key]
}

func write(key, value int) {
    mu.Lock()
    defer mu.Unlock()
    m[key] = value
}

// 正确方式二：使用 sync.Map
var sm sync.Map

sm.Store("key", "value")        // 存储
value, ok := sm.Load("key")     // 读取
sm.Delete("key")                // 删除

预分配容量​

如果知道 map 的大致大小，预分配可以减少扩容开销：

// 不好的做法：频繁扩容
m := make(map[int]int)
for i := 0; i < 10000; i++ {
    m[i] = i  // 可能触发多次扩容
}

// 好的做法：预分配容量
m := make(map[int]int, 10000)
for i := 0; i < 10000; i++ {
    m[i] = i  // 无需扩容
}

数据结构选择指南​

数组 vs 切片​

场景推荐原因
元素数量固定且已知数组编译时确定大小，更安全
元素数量可变切片灵活，支持动态扩容
函数参数传递切片避免复制大数组
需要修改原数据切片指针或切片值语义保护原数组

切片 vs 映射​

场景推荐原因
有序集合切片保持插入顺序
需要快速查找映射O(1) 查找时间
键值对数据映射天然支持
允许重复元素切片映射键唯一
内存效率要求高切片映射有额外开销

性能优化建议​

切片预分配​

// 不好：频繁扩容
var s []int
for i := 0; i < 10000; i++ {
    s = append(s, i)
}

// 好：预分配
s := make([]int, 0, 10000)
for i := 0; i < 10000; i++ {
    s = append(s, i)
}

避免不必要的转换​

// 不好：字符串和字节切片频繁转换
s := "hello"
b := []byte(s)   // 分配新内存
s = string(b)    // 又分配新内存

// 好：使用 unsafe 或专门库（谨慎使用）

大切片传递​

// 切片本身只有 24 字节（指针 + len + cap）
// 传递切片不会复制底层数组
func process(s []int) {
    // s 是切片描述符的副本，但共享底层数组
}

// 如果需要保护原切片
func processSafe(s []int) {
    s = append([]int(nil), s...)  // 复制
    // 现在可以安全修改 s
}

小结​

本章我们深入学习了 Go 的三种核心数据结构：

  1. 数组：固定长度、值类型、内存连续，适合元素数量固定的场景
  2. 切片：动态长度、引用类型、基于数组，是最常用的序列类型
  3. 映射：键值对、引用类型、基于哈希表，适合快速查找场景

关键要点：

  • 理解值类型和引用类型的区别
  • 掌握切片的扩容机制和共享底层数组的特性
  • 知道 map 的键类型限制和线程安全问题
  • 学会预分配容量以优化性能

练习​

  1. 编写函数实现切片的反转
  2. 实现一个函数，从切片中删除所有等于指定值的元素
  3. 使用 map 实现一个简单的缓存系统，支持设置过期时间
  4. 实现一个函数，合并两个有序切片，结果仍有序
  5. 分析切片和 map 在大量数据下的内存使用差异

参考资源​