Go map 源码详解
Go 的 map 查找过程是 Go 运行时（runtime）中非常经典的一部分。
如果从源码角度看，核心文件主要在：
src/runtime/map.go
其中最重要的数据结构是：
type hmap struct {
count int
flags uint8
B uint8
noverflow uint16
hash0 uint32
buckets unsafe.Pointer
oldbuckets unsafe.Pointer
nevacuate uintptr
extra *mapextra
}
1. map 的整体结构
假设：
m := map[string]int{
"a": 1,
"b": 2,
"c": 3,
}
底层类似：
hmap
│
├── bucket0
│ ├── key
│ ├── value
│ ├── key
│ ├── value
│ └── ...
│
├── bucket1
│
├── bucket2
│
└── bucket3
bucket 数量：
2^B
例如：
B = 3
则：
2³ = 8 个 bucket
2. bucket 长什么样
源码：
type bmap struct {
tophash [8]uint8
}
注意这里看起来只有：
tophash
实际上后面通过内存布局紧跟：
┌─────────────┐
│ tophash[8] │
├─────────────┤
│ key[8] │
├─────────────┤
│ value[8] │
├─────────────┤
│ overflow │
└─────────────┘
一个 bucket 最多存：
8 个 kv
这是 Go 的设计：
bucketCnt = 8
3. 查找过程入口
代码：
v := m[key]
编译后：
mapaccess1()
或者：
v, ok := m[key]
变成：
mapaccess2()
源码：
func mapaccess1(
t *maptype,
h *hmap,
key unsafe.Pointer,
) unsafe.Pointer
4. 第一步：计算 Hash
例如：
m["hello"]
首先：
hash := t.Hasher(key, uintptr(h.hash0))
实际上：
hash("hello")
得到：
110101010101101011...
注意：
hash0
是随机种子。
目的：
防止 Hash DoS 攻击
每个 map 都不同。
5. 第二步：定位 Bucket
源码：
bucket := hash & bucketMask(h.B)
而：
bucketMask(B)
=
(1<<B)-1
例如：
B=3
那么：
mask = 111b
假设：
hash = 1101010110
取低 3 位：
1101010110
110
得到：
bucket = 6
直接定位：
bucket[6]
时间复杂度：
O(1)
6. 第三步：取 TopHash
Go 不会直接比较 Key。
先比较：
top := uint8(hash >> (PtrSize*8 - 8))
即：
Hash 高 8 位
例如：
Hash:
10101100 11101010 ...
↑
TopHash
存进：
bmap.tophash[i]
为什么这么设计？
如果 bucket 里面：
8个 key
直接比较：
key == key
可能很贵。
例如：
string
需要逐字节比较。
所以：
先比较 TopHash
只有：
tophash相同
才继续比较 Key。
7. 第四步：扫描 Bucket
源码逻辑类似：
for i := 0; i < 8; i++ {
if b.tophash[i] != top {
continue
}
if key == keys[i] {
return values[i]
}
}
例如：
Bucket 6
tophash:
[10][35][77][88][99][0][0][0]
查找：
top = 77
那么：
10 ×
35 ×
77 √
只比较第三个 Key。
8. 第五步：比较 Key
源码：
if t.Key.Equal(key, k) {
return value
}
对于：
string
最终：
memequal()
比较字符串内容。
如果：
int
直接：
==
即可。
9. Bucket 满了怎么办
每个 bucket：
只能存 8 个元素
超过：
8
会创建：
overflow bucket
结构：
bucket0
↓
overflow1
↓
overflow2
查找时：
for b != nil {
scan bucket
b = b.overflow
}
类似：
链表
10. 扩容时如何查找
Go 的 map 是渐进式扩容。
扩容期间：
oldbuckets != nil
表示：
正在搬迁
此时查找流程：
if oldbuckets != nil {
先判断 bucket 是否已搬迁
}
源码：
if !evacuated(oldb) {
b = oldb
} else {
b = newb
}
因此：
查找期间也能正常访问
无需停机迁移。
11. 一个完整例子
假设：
m["golang"]
计算：
hash("golang")
=
0x123456789ABCDEF0
Step1
取 Bucket
B=4
bucket = hash & 1111
结果：
bucket = 0
Step2
取 TopHash
0x12
=
18
Step3
扫描 bucket0
tophash
[3][18][77][88][0][0][0][0]
找到：
18
Step4
比较 Key
keys[1] == "golang"
成立。
Step5
返回
values[1]
时间复杂度为什么接近 O(1)
因为查找路径基本固定：
Hash计算
↓
定位Bucket
↓
最多扫描8个槽位
↓
比较Key
即：
O(1)
而不是：
O(logN)
像红黑树那样逐层查找。
Go Map 查找流程总结
mapaccess1/mapaccess2
│
▼
计算Hash
│
▼
bucket = hash & ((1<<B)-1)
│
▼
找到Bucket
│
▼
提取TopHash
│
▼
遍历8个槽位
│
▼
TopHash匹配？
│
▼
Key比较
│
▼
返回Value
理解这套流程后，再看 Go Map 的扩容（growWork）、渐进迁移（evacuate）、overflow bucket 管理、为什么 bucket 固定为 8 个槽位，就能把整个 runtime/map.go 的设计思路串起来。
删除一个值
Go 的 map delete 比查找更有意思，因为 Go 并不会像链表那样真正把元素从内存中移除，而是采用一种「标记删除 + 后续复用槽位」的设计。
源码主要看：
src/runtime/map.go
删除入口：
delete(m, key)
编译器会转换成：
mapdelete()
源码：
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)
整体流程图
delete(m, key)
│
▼
mapdelete()
│
▼
计算 Hash
│
▼
定位 Bucket
│
▼
找到 Key
│
▼
清空 Key
清空 Value
│
▼
修改 TopHash
│
▼
count--
先回顾 Bucket 结构
一个 Bucket：
┌───────────────────┐
│ tophash[8] │
├───────────────────┤
│ keys[8] │
├───────────────────┤
│ values[8] │
├───────────────────┤
│ overflow │
└───────────────────┘
例如：
Bucket0
tophash:
[12][45][88][99][00][00][00][00]
keys:
["a"]["b"]["c"]["d"]
values:
[1][2][3][4]
第一步：计算 Hash
与查找完全一致：
hash := t.Hasher(key, uintptr(h.hash0))
例如：
delete(m, "c")
得到：
hash("c")
=
0x12345678
第二步：定位 Bucket
bucket := hash & ((1<<B)-1)
例如：
B=3
则：
bucket = hash & 111
找到：
bucket[5]
第三步：扫描 Bucket
源码逻辑和查找几乎一样：
for b != nil {
for i := 0; i < 8; i++ {
...
}
b = overflow
}
首先比较：
tophash
再比较：
key
找到目标元素。
找到 Key 后发生什么
假设：
slot2
key = "c"
value = 3
Go 不会移动后面的元素。
不会变成：
[a][b][d]
因为这样代价太大。
而是：
[a][b][ ][d]
留下空洞。
第一步：清空 Key
源码：
memclrHasPointers(...)
或者：
memclrNoHeapPointers(...)
根据 Key 类型决定。
例如：
string
删除后：
key = nil
第二步：清空 Value
例如：
int
删除后：
value = 0
删除前：
keys:
[a][b][c][d]
values:
[1][2][3][4]
删除后：
keys:
[a][b][ ][d]
values:
[1][2][0][4]
第三步：修改 TopHash
这是关键。
Go 用特殊状态表示：
emptyOne
源码常量：
const (
emptyRest = 0
emptyOne = 1
)
删除后：
b.tophash[i] = emptyOne
变成：
tophash
[12][45][1][99]
这里：
1 = emptyOne
表示：
这里曾经有元素
现在被删除了
为什么不用 0？
因为：
0 = emptyRest
代表：
从这里开始后面全是空的
查找时可以直接停止。
例如：
[12][45][0][0][0]
扫描到：
0
立刻结束。
而删除场景：
[12][45][1][99]
如果写成：
[12][45][0][99]
查找：
m["d"]
看到：
0
会误认为：
后面没有元素
导致找不到 d。
因此必须区分：
emptyOne
emptyRest
删除后如何复用
后续插入：
m["x"] = 100
插入逻辑会优先找：
emptyOne
槽位。
例如：
删除后：
[12][45][1][99]
插入：
[12][45][55][99]
直接复用 slot2。
无需新建 bucket。
count–
删除成功后：
h.count--
例如：
删除前：
len(m) = 100
删除后：
len(m) = 99
Overflow Bucket 不会立即释放
假设：
bucket0
↓
overflow1
↓
overflow2
删除了很多元素：
bucket0
↓
overflow1
↓
overflow2
链表仍然存在。
Go 不会：
立即回收 overflow bucket
原因：
避免频繁申请释放内存。
Go Map 不会因为删除而缩容
这是很多人不知道的。
例如：
m := make(map[int]int)
插入：
100万个元素
扩容后：
2048 buckets
然后：
删除999999个元素
剩：
1个元素
Map 仍然保持：
2048 buckets
不会缩容。
为什么不缩容
如果自动缩容：
删除
缩容
插入
扩容
删除
缩容
会出现：
频繁搬迁
性能震荡严重。
Go 团队选择：
只扩容
不缩容
保证稳定性能。
删除期间的 GC 处理
假设：
type User struct {
Name string
}
Map：
map[string]*User
删除：
delete(m, "tom")
运行时：
key = nil
value = nil
这样 GC 才能发现：
已经没有引用
后续回收 User 对象。
否则会产生内存泄漏。
源码中的关键逻辑（简化版）
可以近似理解成：
func mapdelete(key) {
hash := hash(key)
bucket := buckets[hash&mask]
for bucket != nil {
for i := 0; i < 8; i++ {
if tophash[i] != top {
continue
}
if keys[i] == key {
clear(keys[i])
clear(values[i])
tophash[i] = emptyOne
count--
return
}
}
bucket = bucket.overflow
}
}
删除后的 Bucket 示意图
删除前
┌──────────────────────────┐
│ TopHash │
│ 12 45 88 99 00 00 00 00 │
├──────────────────────────┤
│ Keys │
│ a b c d │
├──────────────────────────┤
│ Values │
│ 1 2 3 4 │
└──────────────────────────┘
删除 c：
┌──────────────────────────┐
│ TopHash │
│ 12 45 01 99 00 00 00 00 │
├──────────────────────────┤
│ Keys │
│ a b - d │
├──────────────────────────┤
│ Values │
│ 1 2 0 4 │
└──────────────────────────┘
其中：
01 = emptyOne
表示：
这里曾经有元素
已删除
可以复用
一句话总结
Go Map 删除元素的本质不是“移除节点”，而是：
找到 Key
↓
清空 Key/Value
↓
TopHash 标记为 emptyOne
↓
count--
↓
后续插入复用该槽位
因此删除的时间复杂度仍然接近：
O(1)
而且不会触发元素搬移、Bucket 重排或 Map 缩容，这也是 Go delete() 性能非常稳定的重要原因。
扩容机制
Go Map 的扩容（Grow）是整个 runtime/map.go 最精彩的部分之一。
因为 Go 采用的是：
渐进式扩容（Incremental Rehash）
而不是：
一次性扩容（Stop-The-World Rehash）
所以即使一个 Map 有几百万个元素，扩容时也不会卡顿很久。
1. 为什么需要扩容
Map 本质：
bucket
↓
bucket
↓
bucket
每个 bucket：
bucketCnt = 8
最多存：
8个 kv
假设：
B = 2
则：
2² = 4 个 bucket
结构：
bucket0
bucket1
bucket2
bucket3
继续插入：
for i:=0;i<100;i++{
m[i]=i
}
越来越多元素落入：
overflow bucket
变成：
bucket0
↓
overflow1
↓
overflow2
查找性能开始下降。
因此需要扩容。
2. Go 的扩容条件
源码：
func overLoadFactor(count int, B uint8) bool
核心：
count > bucketCnt &&
count > loadFactorNum*(bucketShift(B)/loadFactorDen)
Go 当前负载因子约：
6.5
即：
平均每个bucket约6.5个元素
就触发扩容。
例如：
8 个 bucket
容量：
8 × 6.5
=
52
插入第53个元素：
触发扩容
3. 第二种扩容条件
源码：
tooManyOverflowBuckets()
即：
overflow bucket 太多
例如：
bucket0
↓
overflow1
↓
overflow2
↓
overflow3
虽然总元素不多：
20个
但哈希分布极差。
查找变慢。
也会扩容。
4. 两种扩容类型
源码：
sameSizeGrow
标志位：
h.flags
Go 有两种扩容。
第一种：翻倍扩容
正常情况：
bucket数量 ×2
例如：
B = 3
当前：
2³ = 8 bucket
扩容后：
B = 4
变成：
2⁴ = 16 bucket
第二种：等量扩容
当：
overflow太多
时：
bucket数量不变
例如：
8 bucket
扩容后仍然：
8 bucket
只是：
重新分布元素
清理 overflow。
5. 开始扩容
核心函数：
func hashGrow(t *maptype, h *hmap)
扩容前：
hmap
buckets
│
▼
old bucket array
扩容后：
hmap
buckets
│
▼
new bucket array
oldbuckets
│
▼
old bucket array
源码：
h.oldbuckets = oldbuckets
h.buckets = newbuckets
此时：
新旧 bucket 同时存在
6. 为什么不直接搬迁
传统 HashMap：
扩容
↓
搬迁全部元素
↓
恢复服务
例如：
100万元素
可能搬：
100万次
造成长时间暂停。
Go 不这么做。
Go：
先申请新桶
然后：
边访问边搬
7. 渐进式迁移
hmap：
oldbuckets
nevacuate
例如：
old bucket:
0
1
2
3
4
5
6
7
开始扩容：
nevacuate = 0
表示：
0之前已迁移
8. growWork()
每次：
mapassign()
或者：
mapdelete()
都会执行：
growWork()
源码：
growWork(t, h, bucket)
作用：
顺便搬迁几个bucket
例如：
第一次插入：
迁移 bucket0
第二次：
迁移 bucket1
第三次：
迁移 bucket2
逐步完成。
9. evacuate()
真正搬迁函数：
evacuate()
源码：
func evacuate(t *maptype,h *hmap, oldbucket uintptr)
负责：
old bucket
↓
new bucket
迁移。
10. 元素搬到哪里
扩容前：
B=3
000
001
010
011
100
101
110
111
8 个 bucket。
扩容后：
B=4
16 个 bucket。
新增了一位：
0000
0001
0010
...
1111
因此旧 bucket 中元素：
要么留在原位置
要么移动到新位置
举例
原来：
bucket 3
011
扩容后：
新增一位：
0 011
1 011
即：
3
11
所以：
旧bucket3
中的元素：
部分去3
部分去11
11. x / y 分流
源码：
x
y
两个目标桶。
示意：
old bucket 3
│
▼
hash新位
0 ?
/ \
▼ ▼
bucket3
bucket11
判断逻辑：
if hash & newbit == 0
进入：
x
否则：
y
这就是扩容时的再哈希。
12. 如何保证查找正确
扩容期间：
oldbuckets != nil
查找：
mapaccess()
会先判断：
evacuated()
如果：
bucket未迁移
查：
old bucket
如果：
bucket已迁移
查：
new bucket
因此：
扩容期间依然可读
13. 搬迁完成
当：
nevacuate == oldBucketCount
说明：
全部搬完
源码：
h.oldbuckets=nil
释放：
old bucket array
最终：
只有新桶
存在。
14. 扩容过程完整图
插入元素
│
▼
达到负载因子
│
▼
hashGrow()
│
├──── 创建新桶
│
├──── oldbuckets=旧桶
│
└──── buckets=新桶
│
▼
growWork()
│
▼
evacuate()
│
▼
bucket0迁移
bucket1迁移
bucket2迁移
bucket3迁移
...
│
▼
oldbuckets=nil
一个具体例子
扩容前：
B=2
bucket0
bucket1
bucket2
bucket3
共：
4 bucket
扩容：
B=3
变：
8 bucket
旧 bucket2：
010
里面：
A
B
C
看 hash 新增位：
A -> 0010
B -> 1010
C -> 0010
结果：
bucket2:
A,C
bucket6:
B
完成分流。
为什么 Go Map 扩容性能好
Java HashMap（传统实现）：
扩容
↓
一次搬迁所有元素
↓
暂停较久
Go Map：
扩容
↓
创建新桶
↓
每次操作顺便搬一点
↓
逐步完成
因此：
单次延迟极低
这就是 Go Runtime Map 最核心的设计之一。
一句话总结
Go Map 扩容的本质是：
达到负载因子
↓
创建新 bucket 数组
↓
oldbuckets 保存旧桶
↓
growWork() 驱动
↓
evacuate() 逐桶迁移
↓
元素按新增 hash 位分流
↓
全部迁移完成后释放旧桶
也就是说，Go Map 采用的是 渐进式扩容（Incremental Rehash），把一次巨大的迁移成本拆分到后续的插入、删除操作中，从而避免长时间停顿。