Go map 底层实现原理全解析
· 2866 words · ~ 14 min read
Last modified:
Go 的 map 用起来很简单：m[k] 查询，m[k] = v 写入，delete(m, k) 删除。但它背后的实现并不简单，尤其是 Go 1.26.3 这版已经不是很多老文章里讲的 hmap、bucket、overflow bucket 那套结构。
本文基于 Go 1.26.3 源码中的 src/runtime/map.go 和 src/internal/runtime/maps，按数据结构、创建、查询、写入、删除、扩容和遍历几个路径梳理 map 的真实执行过程。
核心结论先放前面：
- Go 1.26.3 的 map 核心实现位于
internal/runtime/maps，runtime/map.go主要是编译器、reflect 和 runtime 之间的转发层。 - 新实现基于 Abseil Swiss Table 思路，每 8 个 key/value slot 组成一个 group，用 8 字节 control word 加速匹配。
- hash 被拆成两部分：高位 H1 用来定位 group，低 7 位 H2 存进 control byte，用来快速筛候选 slot。
- 小 map 最多 8 个元素时可以只用一个 group；更大时使用 table；再大时用 directory 管理多个 table。
- 扩容不是旧实现里的渐进搬迁 bucket，而是 table 级重建；为了限制单次重建成本，大 map 会用 extendible hashing 拆成多个 table。
整体结构
runtime/map.go 里已经看不到旧的 hmap 定义，它引入的是：
|
|
makemap、mapaccess1、mapassign、mapdelete 等入口最终都落到 maps.Map 上：
|
|
maps.Map 是 map 的顶层结构：
|
|
几个字段的含义：
| 字段 | 含义 |
|---|---|
used |
map 中真实存在的元素数量，也是 len(m) 读取的字段 |
seed |
每个 map 独立的 hash 种子，降低碰撞攻击风险 |
dirPtr |
小 map 时指向单个 group；大 map 时指向 table 指针数组 |
dirLen |
directory 长度；为 0 表示 small map 模式 |
globalDepth/globalShift |
extendible hashing 用来从 hash 高位选择 table |
writing |
写入期间切换的标志，用来尽量发现并发读写/并发写 |
tombstonePossible |
是否可能存在删除留下的 tombstone |
clearSeq |
clear(m) 的序号，遍历期间用它识别 clear |
可以把 Go 1.26.3 的 map 看成下面这个层次：
|
|
这和 slice 的区别很明显：slice 变量本身就是三字段描述符；map 变量更像一个指向 runtime map 头部的指针。var m map[string]int 的零值是 nil，查询没问题，写入会 panic。
当前底层结构图
Go 1.26.3 的 map 可以分成两条路径：小 map 只挂一个 group；大 map 通过 directory 找到 table，再在 table 的 groups 里查 slot。
flowchart TD
A["用户代码里的 map 变量"] --> B["*maps.Map"]
B --> C["used<br/>元素数量，len(m) 读取它"]
B --> D["seed<br/>每个 map 独立的 hash 种子"]
B --> E["dirPtr / dirLen"]
B --> F["globalDepth / globalShift<br/>directory 选 table"]
B --> G["writing<br/>并发写检测"]
E --> H{"dirLen == 0?"}
H -->|是，小 map| I["dirPtr -> group"]
I --> J["ctrlGroup<br/>8 个 control byte"]
I --> K["8 个 slot<br/>key/elem key/elem ..."]
H -->|否，大 map| L["dirPtr -> directory []*table"]
L --> M["table A"]
L --> N["table B"]
L --> O["table C"]
M --> P["groups[]"]
P --> Q["group 0"]
P --> R["group 1"]
Q --> S["ctrlGroup"]
Q --> T["8 个 key/elem slot"]
对应到一次 m[key] 查询，可以简化成下面这条路径：
flowchart TD
A["m[key]"] --> B{"m == nil 或 used == 0?"}
B -->|是| Z["返回元素零值 / ok=false"]
B -->|否| C["hash = Hasher(key, seed)"]
C --> D["拆分 hash<br/>H1 = 高位<br/>H2 = 低 7 位"]
D --> E{"small map?"}
E -->|是| F["直接检查单个 group"]
E -->|否| G["用 hash 高位选择 directory index"]
G --> H["拿到 table"]
H --> I["用 H1 创建 probeSeq"]
I --> J["定位 group"]
F --> K["ctrlGroup.matchH2(H2)"]
J --> K
K --> L{"有 H2 候选 slot?"}
L -->|有| M["对候选 key 做完整 Equal 比较"]
M --> N{"key 相等?"}
N -->|是| O["返回 elem"]
N -->|否| P["检查下一个候选"]
P --> L
L -->|没有| Q{"group 有 empty?"}
Q -->|是| Z
Q -->|否| R["probeSeq.next()<br/>继续下一个 group"]
R --> J
写入和删除也是同一套定位逻辑：先 hash，再选 table/group，再通过 matchH2 缩小候选范围。区别在于写入找不到 key 时要找 empty/deleted slot，空间不够会触发 rehash；删除找到 key 后要清理 key/elem，并把 control byte 改成 empty 或 deleted。
Abseil Swiss Table 是什么
Swiss Table 是 Abseil 提供的一组高性能哈希表设计，官方设计说明在 Swiss Tables Design Notes。它的核心不是发明一种新的哈希函数，而是把「怎么在哈希冲突下更快找到候选位置」这件事做得更紧凑。
传统开放寻址哈希表通常是这样查找：
|
|
这种方式的问题是，每走一个 slot 都可能要访问 key，并调用一次完整相等比较。key 如果是字符串或复杂结构，这个成本不低。
Swiss Table 多加了一层 metadata，也就是 control byte。每个 slot 除了存 key/value，还对应 1 字节 metadata。这个 byte 记录两类信息：
- slot 状态：empty、deleted、full；
- hash 的一小段指纹：H2，也就是 hash 的低 7 位。
于是一次查询变成两阶段：
|
|
用图表示：
|
|
这就是 Swiss Table 快的主要原因：它先在很小、连续、容易被 CPU 处理的 metadata 上做筛选，再访问真正的 key/value。Abseil 的 C++ 实现会用 SIMD 一次检查更多 metadata；Go 1.26.3 的实现固定一个 group 8 个 slot，用一个 8 字节 control word 表示 8 个 control byte。源码里也保留了同样的抽象：
|
|
Go 这里借用的是 Swiss Table 的核心思路：
| Swiss Table 思路 | Go 1.26.3 map 中的对应实现 |
|---|---|
| metadata/control byte | ctrlGroup，8 个 control byte 打包成 uint64 |
| H1/H2 拆分 hash | h1(hash) 取高位，h2(hash) 取低 7 位 |
| 批量筛候选 slot | matchH2 返回 bitset，再逐个校验候选 key |
| empty/deleted/full 状态 | ctrlEmpty、ctrlDeleted、full = H2 |
| 开放寻址 + probing | probeSeq 按二次探测继续找 group |
但 Go 没有直接照搬 Abseil 的 C++ 容器。Go 还要满足自己的语言语义：内置 map 的零值、len、delete、clear、range、GC 扫描、写屏障、反射、并发错误检测，以及遍历期间修改 map 的规则。所以 Go 在 Swiss Table 的 table/group 结构之外，又加了 Map、directory、extendible hashing、iterator 兼容逻辑这些 runtime 层设计。
简单说：Swiss Table 解决的是「单个哈希表内部怎么查得快、放得紧凑」；Go 的 maps.Map 还要解决「内置 map 如何创建、扩容、拆分、遍历、配合 GC 和语言规范」。
group 与 control byte
Swiss Table 的基本单位是 group。Go 这里固定一个 group 有 8 个 slot：
|
|
一个 group 的逻辑布局是：
|
|
源码里没有直接写出这个 Go 结构体，而是由编译器根据 key/elem 类型生成对应布局。groupReference 通过偏移拿到 key 和 elem：
|
|
control word 是 8 字节，每个字节对应一个 slot。control byte 有三种状态：
|
|
查找时不会直接逐个比较 8 个 key，而是先用 control word 一次筛出 H2 相同的候选 slot：
|
|
这一步可能有假阳性，因为 H2 只有 7 bit，平均每 128 个 slot 会有一个控制字节碰上。但这没关系，runtime 会继续调用 key 的 Equal 函数做完整比较。control word 的价值是先把绝大多数不可能匹配的 slot 排除掉。
内存布局可以这样理解：
|
|
hash：H1 与 H2
map 查询、写入、删除都会先算 hash：
|
|
Go 把 hash 拆成 H1 和 H2：
|
|
两者分工不同：
- H1：高位，用来选择 table 和 group，决定从哪里开始探测。
- H2：低 7 位，写进 control byte，用来快速筛候选 slot。
完整查询路径大致是：
flowchart TD
A["m[key]"] --> B{"m == nil 或 used == 0?"}
B -->|是| Z["返回 zeroVal / ok=false"]
B -->|否| C{"writing != 0?"}
C -->|是| X["fatal: concurrent map read and map write"]
C -->|否| D["hash = Hasher(key, seed)"]
D --> E{"dirLen == 0?"}
E -->|是，小 map| F["在单个 group 内 matchH2 + Equal"]
E -->|否，大 map| G["用 hash 高位选择 table"]
G --> H["用 H1 构造 probeSeq"]
H --> I["逐 group 探测"]
I --> J["matchH2 找候选 slot"]
J --> K{"Equal(key, slotKey)?"}
K -->|是| L["返回 elem"]
K -->|否| M{"group 有 empty slot?"}
M -->|是| Z
M -->|否| I
注意查询缺失 key 时，mapaccess1 返回的是 zeroVal 的地址，不是 nil；mapaccess2 才额外返回 ok=false。这就是 v := m[k] 和 v, ok := m[k] 的底层差异。
创建 map
常见创建方式：
|
|
入口是 makemap，它会调用 maps.NewMap。关键逻辑是：
|
|
如果 hint 不超过 8，runtime 不急着分配 group，只创建 Map 头部并设置 hash seed。第一次写入时才会走 growToSmall 分配一个 group。
执行路径：
flowchart TD
A["make(map[K]V, hint)"] --> B["runtime.makemap"]
B --> C["maps.NewMap"]
C --> D["创建或复用 *maps.Map"]
D --> E["seed = rand()"]
E --> F{"hint <= 8?"}
F -->|是| G["返回空 Map\n暂不分配 group"]
F -->|否| H["按 7/8 负载因子计算 targetCapacity"]
H --> I["创建 directory"]
I --> J["创建一个或多个 table"]
J --> K["返回 Map"]
小 map 第一次写入时：
|
|
也就是说，make(map[K]V) 本身可能只分配 map 头部，真正的 slot 存储可以延迟到第一次写入。
写入 map
写入入口是 mapassign，最终会调用 Map.PutSlot 或 fast path。先看几个关键点：
- nil map 写入直接 panic：
assignment to entry in nil map。 - 写入前会计算 hash，然后把
writing标志切换为写入中。 - 小 map 未满时直接在一个 group 里插入。
- 小 map 超过 8 个元素后会转成 full map。
- full map 中，如果当前 table 没有足够空间，会 rehash：要么 table 扩容，要么 table split。
简化后的写入路径：
flowchart TD
A["m[key] = value"] --> B{"m == nil?"}
B -->|是| P["panic: assignment to entry in nil map"]
B -->|否| C{"writing != 0?"}
C -->|是| X["fatal: concurrent map writes"]
C -->|否| D["hash = Hasher(key, seed)"]
D --> E["writing ^= 1"]
E --> F{"dirPtr == nil?"}
F -->|是| G["growToSmall: 分配 1 个 group"]
F -->|否| H
G --> H{"dirLen == 0?"}
H -->|是，小 map| I{"used < 8?"}
I -->|是| J["putSlotSmall"]
I -->|否| K["growToTable: 转 full map"]
H -->|否| L["按 hash 选择 table"]
K --> L
L --> M["table.PutSlot"]
M --> N{"找到已有 key?"}
N -->|是| O["返回 elem slot，覆盖 value"]
N -->|否| Q{"有 empty/deleted slot 且 growthLeft > 0?"}
Q -->|是| R["写入 key，返回 elem slot"]
Q -->|否| S["rehash 后重试"]
J --> T["写 elem"]
O --> T
R --> T
T --> U["writing ^= 1"]
PutSlot 只负责找到 elem 的存储位置并返回指针，真正把 value 写进去是外层做的：
|
|
这也解释了为什么 map 元素不能取地址：
|
|
map 写入可能触发 table 重建，元素位置并不稳定。允许用户长期持有元素地址，会让 runtime 无法移动和重排 slot。
探测序列
full map 查找一个 key 时，不一定一次就落到正确 group。碰撞时需要继续探测后续 group。
Go 1.26.3 使用二次探测，源码注释给出的形式是：
|
|
实现很短：
|
|
因为 group 数量总是 2 的幂，& mask 可以替代取模。探测过程有一个重要不变量：table 不能 100% 填满，探测序列最终必须遇到 empty slot。遇到 empty slot 就说明 key 不存在，可以停止。
删除 map 元素
删除入口是：
|
|
删除和查询类似，也会先 hash，再定位 table/group/slot。找到 key 后要做三件事：
used--，更新 map 和 table 的元素数量。- 清理 key/elem 内存，尤其是包含指针的对象，避免 GC 继续把它们当成可达对象。
- 更新 control byte：设为 empty 或 deleted。
为什么有时不能直接设为 empty？因为开放寻址里查找遇到 empty 就会停止。如果一个 slot 位于某个探测链中间，直接设 empty 可能让后面的 key 永远查不到。
所以 full map 删除时有两种情况：
|
|
流程图：
flowchart TD
A["delete(m, key)"] --> B{"m == nil 或 used == 0?"}
B -->|是| Z["返回"]
B -->|否| C["hash = Hasher(key, seed)"]
C --> D{"small map?"}
D -->|是| E["单 group 查找"]
D -->|否| F["选择 table 并探测"]
E --> G{"找到 key?"}
F --> G
G -->|否| Z
G -->|是| H["清理 key/elem"]
H --> I["used--"]
I --> J{"删除后 group 有 empty slot?"}
J -->|是| K["control = empty"]
J -->|否| L["control = deleted tombstone"]
K --> M{"map used == 0?"}
L --> M
M -->|是| N["重置 hash seed"]
M -->|否| Z
删除到 map 为空时，runtime 会重置 seed，降低反复构造碰撞的攻击面。
扩容与拆分
table 有三个和容量相关的字段：
|
|
capacity 是 slot 总数，必须是 2 的幂。最大平均负载因子是 7/8：
|
|
正常 table 的可继续插入数量是：
|
|
当 growthLeft == 0 时，插入会触发 rehash：
|
|
Go 1.26.3 里单个 table 的最大容量是 1024：
|
|
因此扩容有两种：
flowchart TD
A["table 没有 growthLeft"] --> B["newCapacity = 2 * capacity"]
B --> C{"newCapacity <= 1024?"}
C -->|是| D["grow: 创建更大的 table"]
D --> E["重新 hash 并搬迁旧元素"]
E --> F["directory 指向新 table"]
C -->|否| G["split: 拆成 left/right 两个 table"]
G --> H["按 localDepth 对应的 hash 高位分流"]
H --> I{"localDepth == globalDepth?"}
I -->|是| J["directory 扩大一倍"]
I -->|否| K["复用现有 directory 空间"]
J --> L["安装 left/right"]
K --> L
这和旧 map 实现差别很大。旧实现强调 bucket 逐步搬迁；新实现里 table 重建是一次性的。为了避免一个超大 table 一次重建太贵，map 会把数据分散到多个 table。某个 table 满了，只重建或拆分这个 table。
directory 选择 table 的方式是 extendible hashing。globalDepth 表示用 hash 的多少个高位做 table 索引：
|
|
示意：
|
|
一个 table split 后，directory 中原来指向它的一段索引会改成分别指向 left/right。如果当前 directory 深度不够，先扩一倍。
遍历 map
for k, v := range m 对 map 的要求比看上去复杂。语言规范允许遍历期间修改 map，并规定了几个语义：
- 不保证遍历顺序。
- 遍历期间新增的元素可能出现，也可能不出现。
- 遍历期间删除还没访问到的元素，不应该再被返回。
- 同一个元素不能返回两次。
runtime 用 maps.Iter 保存遍历状态：
|
|
初始化时会随机化起点：
|
|
所以 map 遍历顺序不是插入顺序，也不是 hash 顺序。它是有意随机化的。
为什么遍历不按顺序返回
map 没有「顺序」这个语义。它不是数组、slice 或链表，内部也不会记录 key 的插入先后。元素放在哪个 slot，主要取决于：
- key 的 hash 值；
- 每个 map 独立的随机 hash seed；
- 当前 table/directory 的大小；
- 碰撞后探测序列找到的空 slot；
- 后续 grow、split、delete 留下的 tombstone。
同一批 key，只要 map 的 seed 不同，hash 结果就可能不同；同一个 map，只要扩容或 split 发生，元素也可能被重新分布到新的 table/group 中。所以 runtime 没有稳定的「从第一个插入的元素开始遍历」这种信息可用。
即使暂时不考虑扩容，遍历也不是从第 0 个 directory、第 0 个 group、第 0 个 slot 固定开始。Iter.Init 会设置两个随机偏移：
|
|
后续遍历 directory 和 slot 时都会带上这两个偏移：
|
|
因此，同一个 map 连续 range 两次，也可能得到不同顺序。这个设计有两个直接效果：
- 避免开发者误以为 map 有稳定顺序，并在业务代码里依赖这个实现细节；
- 让不同 hash seed、不同扩容状态下的遍历行为更接近语言规范里的「顺序未指定」。
如果业务上需要顺序，必须自己定义顺序。最常见做法是先收集 key，再排序，然后按排序后的 key 访问 map：
|
|
遍历最麻烦的是扩容期间的语义。源码里的策略是：
- 如果遍历开始时的 table 后续被 grow/split，iterator 仍然保留旧 table，用旧 table 决定哪些 key 已经走过。
- 返回元素前，再去当前 map 里按 key 查一次。
- 如果 key 已删除，就跳过。
- 如果 value 被更新，就返回最新 value。
这样可以避免扩容后同一个 key 被返回两次，也能尽量符合「删除不再返回、更新返回最新值」的语义。
clear(m) 期间的语义
前面 Map 和 Iter 结构里都出现了 clearSeq，它就是给 clear(m) 准备的。clear 不是逐个 delete，而是一次性把 map 逻辑上清空，所以 iterator 需要一个更便宜的方式知道“从我开始遍历之后，这个 map 已经被整表清掉了”。
做法是：clear(m) 时递增 Map.clearSeq；迭代器初始化时把当时的序号快照到 Iter.clearSeq。后续 Next() 推进时，如果发现两者不相等，就说明遍历过程中发生过 clear。这时 iterator 不需要再按旧快照继续吐元素，而是可以直接按“这些元素已经在遍历前被批量删除”的语义处理。
从使用者角度看，range 期间执行 clear(m) 是安全且有定义的：它不会把 pre-clear 的元素继续完整吐完，也不会因为 bulk delete 打破“已删除元素不该再返回”的约束。clearSeq 就是 runtime 用来低成本维持这条语义的版本号。
fast path
源码里有几类 fast path：
|
|
它们分别服务于常见 key 类型：
- 32 位 key
- 64 位 key
- string key
以 string 为例，runtime/map_faststr.go 只是 linkname 声明，真正实现被推到 internal/runtime/maps/runtime_faststr.go。这样可以绕开一层普通函数调用，也可以针对字符串做更具体的比较和 hash 优化。
对业务代码来说不需要手动使用这些 fast path。编译器会在合适场景把 m[k]、m[k] = v、delete(m, k) 降到对应 runtime 入口。
常见陷阱
nil map 可以读，不能写
|
|
查询 nil map 会返回元素零值；写入 nil map 会 panic。修复方式是先 make：
|
|
判断 key 是否存在必须用 ok
|
|
只看返回值分不清 key 存在且值为零，还是 key 不存在。应该写：
|
|
底层上，缺失 key 会返回 zeroVal，ok 才是存在性信息。
map 不是并发安全的
runtime 里有 writing 标志，会尽量发现并发问题：
|
|
这只是运行时检测，不是同步机制。并发读写 map 必须用 sync.Mutex、sync.RWMutex，或者在适合的读多写少场景使用 sync.Map。
map 元素不能取地址
|
|
根本原因是 map 扩容、rehash、split 都可能移动元素位置。允许用户拿到元素地址会破坏 runtime 对内部存储的管理。
如果值是结构体，不能直接改字段：
|
|
常见写法是取出、修改、再放回：
|
|
或者让 map 存指针：
|
|
遍历顺序不稳定
|
|
不要依赖输出顺序。需要稳定顺序时，先把 key 拿出来排序：
|
|
delete 不会缩容
delete 会清理 slot，并可能留下 tombstone。后续插入可能复用这些位置，rehash 也会清理 tombstone，但 map 不会因为大量删除自动把 directory/table 缩小。
如果一个大 map 删到很小且长期保留，想释放内存，通常直接新建一个 map：
|
|
如果只是清空并复用，可以用 Go 1.21 引入的内置函数：
|
|
clear 会删除所有元素，但它的目标是清空内容，不是保证缩容。
大 key / 大 value 可能间接存储
abi.MapType 里有两个标志：
|
|
Go 的常量里也能看到阈值：
|
|
超过阈值的 key 或 value 可能不直接放在 slot 里，而是 slot 保存指针，实际对象单独分配。这会增加一次间接访问和 GC 压力。实践上，map 的 key 应尽量小、可比较、稳定；value 很大时要明确选择存值还是存指针。
小结
Go 1.26.3 的 map 可以用一句话概括：顶层是 Map，小 map 直接挂一个 8-slot group；大 map 通过 directory 选择 table；table 内部是 Swiss Table 风格的 groups；每个 group 用 control word 一次筛 8 个 slot；扩容时 table 级重建，超过上限后通过 extendible hashing 拆分。
理解这些细节后，很多日常现象就不再神秘：
- nil map 能读不能写，是因为 nil map 没有 runtime 头部可写。
- 缺失 key 返回零值，是因为
mapaccess1返回zeroVal。 - map 遍历顺序不稳定，是因为 iterator 起点随机化。
- map 元素不能取地址，是因为 rehash/split 会移动元素。
- 并发读写会崩，是因为 map 内部结构写入期间没有同步保护。
- 大量 delete 不一定释放内存，是因为 table/directory 不按删除自动缩容。
map 的接口很小，但 runtime 为了把平均 O(1)、内存局部性、删除语义、遍历语义和并发错误检测同时做好，内部复杂度并不低。写业务代码时，不需要记住所有字段；真正有用的是记住它的边界：不要依赖遍历顺序，不要并发读写，不要拿元素地址，容量和删除行为要按 runtime 的实现去理解。