数据结构深入
数据结构深入
一、 slice
1.1 什么是 slice？
slice 是 Go 中基于数组的一个轻量级封装。 本质上，slice 是对底层数组的一个“窗口”。
slice 的三个属性
ptr：指向底层数组的指针
len：当前 slice 长度（元素个数）
cap：底层数组容量（从 ptr 开始算到结尾）
1.2 cap 的计算
slice 的 cap 是怎么计算的？
从起始位置到底层数组末尾算。不是 len。
举个栗子：
arr := [5]int{10, 20, 30, 40, 50}
s := arr[1:3] // s = [20, 30]
s[0] == 20s[1] == 30
len(s) == 2// 只切了 2 个元素（1~2位置）
cap(s) == 4// 从下标1（20）到数组末尾下标4（50），一共有4个位置。
底层示意图：
索引 0 1 2 3 4
数组 [10][20][30][40][50]
s起点 -> [20][30][40][50]
len=2，cap=4
1.3 slice 扩容机制
追加元素（append）时，如果超出当前 cap，Go 会创建一个新的底层数组，并拷贝数据。
扩容策略（大概规律）
小于 1024 个元素时，一般是每次翻倍扩容。
超过 1024 元素后，增长比例变为每次增加 25%。
举个栗子
s := make([]int, 0, 2)
s = append(s, 1) // cap = 2
s = append(s, 2) // cap = 2
s = append(s, 3) // cap = 4 (翻倍)
s = append(s, 4, 5, 6) // cap = 8 (再次翻倍)
扩容后，旧的 slice 仍然指向原数组，新 slice 指向新数组。
package main
import "fmt"
func main() {
s1 := make([]int, 2, 2) // len=2, cap=2
s1[0] = 1
s1[1] = 2
s2 := append(s1, 3) // cap 不够，触发扩容，新建数组
s2[0] = 100 // 修改数据，观察变化
fmt.Println("s1:", s1) // s1: [1 2]
fmt.Println("s2:", s2) // s2: [100 2 3]
}
s1还是指向原来的底层数组[1 2]
s2指向新建的底层数组[100 2 3]
s1没被修改，s2单独用了新的内存。
slice 扩容时发生了什么？
重新申请更大数组，复制旧数据，更新指针。
1.4 slice 引用关系
slice 是引用类型。多个 slice 可以共享同一个底层数组。
示例
arr := [5]int{1, 2, 3, 4, 5}
s1 := arr[1:3] // [2 3]
s2 := arr[2:4] // [3 4]
s1[1] = 99 // 修改 s1 的第二个元素
fmt.Println(arr) // [1 2 99 4 5]
fmt.Println(s2) // [99 4]
因为 s1 和 s2 都引用了 arr，所以修改 arr 也影响了 s2！
slice 之间如何避免互相影响？
可以使用 copy()，主动复制一份数据。
newS := make([]int, len(oldS))
copy(newS, oldS)
1.5 空 slice 与 nil 的区别
var s1 []int // s1 == nil
s2 := make([]int, 0) // s2 != nil，但长度为0
| nil slice | 空 slice | |
|---|---|---|
| 定义 | var s []int | s := make([]int, 0) |
| len | 0 | 0 |
| cap | 0 | 0 |
| 是否为 nil | 是 | 否 |
二、map
2.1 map 是什么？
基础概念：
- map 是哈希表（Hash Table）实现的。
- 它是无序的键值对集合（key-value pairs）。
- 通过 key 查找 value，时间复杂度接近 O(1)。
- 内部依靠哈希算法定位存储位置。
简单栗子
m := map[string]int{
"apple": 5,
"banana": 3,
}
fmt.Println(m["apple"]) // 5
2.2 map 的内部结构（底层）
| 组成部分 | 说明 |
|---|---|
| hmap | map 的整体结构体（元数据） |
| buckets | 底层的桶数组，每个桶存多个 key-value 对 |
| overflow buckets | 桶装满了以后，链式增加溢出桶 |
| 哈希函数 | 通过 key 计算 hash 值 |
简单图示
hmap
├── buckets（数组）
│ ├── bucket[0] -> [k1,v1], [k2,v2], ...
│ ├── bucket[1] -> [k3,v3], ...
│ └── ...
└── overflow（扩展链表）
2.3 map的特点
1. 自动扩容
- 当负载因子（load factor，大约是 6.5）太高时，map 会自动扩容。
- 扩容时会重新分配更大的 bucket 数组，并且 逐步搬迁数据（不是一瞬间搬完，叫“渐进式扩容”）。
负载因子
每个桶（bucket）中存放元素的平均数量。
负载因子 = 元素总数 / 桶总数
在Go里，负载因子接近 6.5 左右时，Go 决定扩容。
渐进式扩容流程
新建两倍大小的新桶数组。
每次对 map 做 读、写、删除 操作时，顺便 挪一小部分桶的数据。
直到慢慢把所有老数据都搬迁完毕。
搬迁完成后，旧桶会被垃圾回收（GC）回收，内存释放 。
简单图示：
扩容中：
hmap
├── buckets -> 新桶数组
└── oldbuckets -> 旧桶数组（正在搬迁）
搬完后：
hmap
├── buckets -> 新桶数组
└── oldbuckets = nil（旧桶丢弃）
GC 发现没有人引用 oldbuckets -> 回收内存
2. 无序性
map 元素的遍历顺序是随机的，每次运行程序顺序可能不同。
目的是防止依赖遍历顺序写代码（安全性考虑）。
3. key 必须是可比较的类型
- 支持 == 运算符的类型才能作为 key，比如 int、string、struct（字段可比较）。
- 切片（slice）、map、函数（func）因为不可比较，不能当 key。
4. value 可以是任意类型
- 甚至可以是另一个 map 或 slice。
2.4 常用操作
1. 创建 map
make 创建
m := make(map[string]int)
字面量创建
m := map[string]int{"one": 1, "two": 2}
2. 访问元素
v := m["key"]
若 key 不存在，返回零值
// 通过第二个值判断是否存在
v, ok := m["key"]
if ok {
fmt.Println("found:", v)
} else {
fmt.Println("not found")
}
3. 删除元素
delete(m, "key")
即使删除不存在的 key 也不会报错
4. 遍历 map
for k, v := range m {
fmt.Println(k, v)
}
注意：遍历顺序是随机的。
2.5 map 并发安全处理
当多个goroutine并发读写同一个 map 时，容易出现：崩溃、数据不一致等问题。
1. 加锁保护
最经典、最常见的方式：
type SafeMap struct {
mu sync.RWMutex
m map[string]int
}
// 写操作（加写锁）
func (s *SafeMap) Set(key string, value int) {
s.mu.Lock()
defer s.mu.Unlock()
s.m[key] = value
}
// 读操作（加读锁）
func (s *SafeMap) Get(key string) (int, bool) {
s.mu.RLock()
defer s.mu.RUnlock()
val, ok := s.m[key]
return val, ok
}
2. 使用 sync.Map
从 Go 1.9 开始，标准库里专门增加了一个「并发安全」的 map：sync.Map。
var m sync.Map
// 存数据
m.Store("foo", 42)
// 取数据
value, ok := m.Load("foo")
// 删除数据
m.Delete("foo")
3. 对比表
| 方法 | 特点 | 使用场景 |
|---|---|---|
| 手动加锁(sync.Mutex / sync.RWMutex) | 最灵活，适合读写都频繁的场景 | 多写多读，复杂场景 |
| sync.Map | 内置优化，适合读多写少；写特别频繁的话，没原生 map + 手动锁快。 | 缓存、共享配置 |
三、struct
3.1 struct 的定义和基本使用
最基本的用法 :
type Person struct {
Name string
Age int
}
创建对象的方式：
p1 := Person{"Tom", 30} // 顺序赋值
p2 := Person{Name: "Jerry"} // 指定字段赋值，Age = 0
p3 := new(Person) // 返回 *Person，指针
p4 := &Person{Name: "Spike"} // 直接取地址
四、string
4.1 string 的本质
string 本质是一个 只读的字节数组（[]byte）
4.2 string 的特点
| 特性 | 说明 |
|---|---|
| 只读 | 不能修改，任何修改操作都要生成新字符串 |
| 内存管理 | 分配在堆上，受 GC 管理 |
| 不可变 | 修改时必须重新拷贝 |
| 支持 UTF-8 | 默认支持 UTF-8 编码，多字节字符处理 |
4.3 修改字符串
Go 中 string 是 只读的，不能直接修改，比如：
s := "hello"
s[0] = 'H' // 编译错误！
正确的修改的方法是：转成 []byte 或 []rune 再改 ，比如：
s := "hello"
b := []byte(s)
b[0] = 'H'
s2 := string(b)
fmt.Println(s2) // "Hello"
为什么 string 是只读的
- 安全性：避免意外篡改共享数据
- 性能优化：可以放心做引用共享，减少拷贝
- GC友好：只读数据生命周期简单，容易管理
4.4 len 计算的是什么？
len(s) 返回的是 字节数，不是字符数！
如果要按字符数算，要转成 []rune：
s := "你好"
fmt.Println(len(s)) // 输出 6
r := []rune(s)
fmt.Println(len(r)) // 输出 2
4.5 字符串拼接
4.6 复制 string 和浅拷贝
在 Go 里，赋值 string 不会复制底层数据，只是拷贝指针和长度！
s1 := "hello"
s2 := s1
s1 和 s2 共用一块底层内存（只读的，所以安全）。