Go map 底层实现原理全解析

2026-05-15 · 2866 words · ~ 14 min read

Last modified: 2026-05-16

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 定义，它引入的是：

1
import "internal/runtime/maps"

makemap、mapaccess1、mapassign、mapdelete 等入口最终都落到 maps.Map 上：

1
2
3
4
5
6
func makemap(t *abi.MapType, hint int, m *maps.Map) *maps.Map {
    if hint < 0 {
        hint = 0
    }
    return maps.NewMap(t, uintptr(hint), m, maxAlloc)
}

maps.Map 是 map 的顶层结构：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
type Map struct {
    used uint64
    seed uintptr

    dirPtr unsafe.Pointer
    dirLen int

    globalDepth uint8
    globalShift uint8
    writing uint8

    tombstonePossible bool
    clearSeq uint64
}

几个字段的含义：

字段	含义
`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 看成下面这个层次：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
map variable
    │
    ▼
*maps.Map
    ├── small map: dirPtr -> group
    │
    └── full map: dirPtr -> directory []*table
                         │
                         ├── table
                         │     └── groups[] -> group -> 8 slots + control word
                         └── table
                               └── groups[] -> group -> 8 slots + control word

这和 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。它的核心不是发明一种新的哈希函数，而是把「怎么在哈希冲突下更快找到候选位置」这件事做得更紧凑。

传统开放寻址哈希表通常是这样查找：

1
hash(key) -> 起始位置 -> 比较 slot0 -> 不匹配 -> 比较 slot1 -> 不匹配 -> ...

这种方式的问题是，每走一个 slot 都可能要访问 key，并调用一次完整相等比较。key 如果是字符串或复杂结构，这个成本不低。

Swiss Table 多加了一层 metadata，也就是 control byte。每个 slot 除了存 key/value，还对应 1 字节 metadata。这个 byte 记录两类信息：

slot 状态：empty、deleted、full；
hash 的一小段指纹：H2，也就是 hash 的低 7 位。

于是一次查询变成两阶段：

1
2
第一阶段：只看 metadata，快速筛出 H2 相同的候选 slot
第二阶段：只对候选 slot 做完整 key 比较

用图表示：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
hash(key)
   │
   ├── H1：定位起始 group / probe 位置
   │
   └── H2：和 control byte 批量比较，筛候选 slot

group:
  ctrls: [80][12][34][fe][12][80][7a][09]
             ▲           ▲
             └── H2 命中 ┘

只比较 H2 命中的 slot 对应的 key。

这就是 Swiss Table 快的主要原因：它先在很小、连续、容易被 CPU 处理的 metadata 上做筛选，再访问真正的 key/value。Abseil 的 C++ 实现会用 SIMD 一次检查更多 metadata；Go 1.26.3 的实现固定一个 group 8 个 slot，用一个 8 字节 control word 表示 8 个 control byte。源码里也保留了同样的抽象：

1
2
3
4
5
type ctrlGroup uint64

func (g ctrlGroup) matchH2(h uintptr) bitset {
    return ctrlGroupMatchH2(g, h)
}

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：

1
2
const MapGroupSlotsBits = 3
const MapGroupSlots = 1 << MapGroupSlotsBits // 8

一个 group 的逻辑布局是：

1
2
3
4
5
6
7
8
9
type group struct {
    ctrls ctrlGroup
    slots [8]slot
}

type slot struct {
    key  typ.Key
    elem typ.Elem
}

源码里没有直接写出这个 Go 结构体，而是由编译器根据 key/elem 类型生成对应布局。groupReference 通过偏移拿到 key 和 elem：

1
2
3
4
5
6
7
8
9
func (g *groupReference) key(typ *abi.MapType, i uintptr) unsafe.Pointer {
    offset := groupSlotsOffset + i*typ.SlotSize
    return unsafe.Pointer(uintptr(g.data) + offset)
}

func (g *groupReference) elem(typ *abi.MapType, i uintptr) unsafe.Pointer {
    offset := groupSlotsOffset + i*typ.SlotSize + typ.ElemOff
    return unsafe.Pointer(uintptr(g.data) + offset)
}

control word 是 8 字节，每个字节对应一个 slot。control byte 有三种状态：

1
2
3
empty:   1000 0000
deleted: 1111 1110
full:    0hhh hhhh   // h 是 hash 的低 7 位，也就是 H2

查找时不会直接逐个比较 8 个 key，而是先用 control word 一次筛出 H2 相同的候选 slot：

1
2
3
func (g ctrlGroup) matchH2(h uintptr) bitset {
    return ctrlGroupMatchH2(g, h)
}

这一步可能有假阳性，因为 H2 只有 7 bit，平均每 128 个 slot 会有一个控制字节碰上。但这没关系，runtime 会继续调用 key 的 Equal 函数做完整比较。control word 的价值是先把绝大多数不可能匹配的 slot 排除掉。

内存布局可以这样理解：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
group
┌─────────────────────────────────────────────┐
│ ctrls: [c0][c1][c2][c3][c4][c5][c6][c7]    │
├─────────────────────────────────────────────┤
│ slot0: key0, elem0                          │
│ slot1: key1, elem1                          │
│ ...                                         │
│ slot7: key7, elem7                          │
└─────────────────────────────────────────────┘

control byte:
  0x80  -> empty
  0xfe  -> deleted
  0x00~0x7f -> full，值为 H2

hash：H1 与 H2

map 查询、写入、删除都会先算 hash：

1
hash := typ.Hasher(key, m.seed)

Go 把 hash 拆成 H1 和 H2：

1
2
func h1(h uintptr) uintptr { return h >> 7 }
func h2(h uintptr) uintptr { return h & 0x7f }

两者分工不同：

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

常见创建方式：

1
2
m := make(map[string]int)
m2 := make(map[string]int, 100)

入口是 makemap，它会调用 maps.NewMap。关键逻辑是：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func NewMap(mt *abi.MapType, hint uintptr, m *Map, maxAlloc uintptr) *Map {
    if m == nil {
        m = new(Map)
    }

    m.seed = uintptr(rand())

    if hint <= abi.MapGroupSlots {
        return m
    }

    targetCapacity := (hint * abi.MapGroupSlots) / maxAvgGroupLoad
    ...
}

如果 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 第一次写入时：

1
2
3
4
5
6
7
func (m *Map) growToSmall(typ *abi.MapType) {
    grp := newGroups(typ, 1)
    m.dirPtr = grp.data

    g := groupReference{data: m.dirPtr}
    g.ctrls().setEmpty()
}

也就是说，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 写进去是外层做的：

1
2
3
4
func (m *Map) Put(typ *abi.MapType, key, elem unsafe.Pointer) {
    slotElem := m.PutSlot(typ, key)
    typedmemmove(typ.Elem, slotElem, elem)
}

这也解释了为什么 map 元素不能取地址：

1
2
// 编译错误：cannot take address of m["a"]
_ = &m["a"]

map 写入可能触发 table 重建，元素位置并不稳定。允许用户长期持有元素地址，会让 runtime 无法移动和重排 slot。

探测序列

full map 查找一个 key 时，不一定一次就落到正确 group。碰撞时需要继续探测后续 group。

Go 1.26.3 使用二次探测，源码注释给出的形式是：

1
p(i) = hash + (i^2 + i)/2  (mod mask+1)

实现很短：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
type probeSeq struct {
    mask   uint64
    offset uint64
    index  uint64
}

func makeProbeSeq(hash uintptr, mask uint64) probeSeq {
    return probeSeq{
        mask:   mask,
        offset: uint64(hash) & mask,
        index:  0,
    }
}

func (s probeSeq) next() probeSeq {
    s.index++
    s.offset = (s.offset + s.index) & s.mask
    return s
}

因为 group 数量总是 2 的幂，& mask 可以替代取模。探测过程有一个重要不变量：table 不能 100% 填满，探测序列最终必须遇到 empty slot。遇到 empty slot 就说明 key 不存在，可以停止。

删除 map 元素

删除入口是：

1
delete(m, key)

删除和查询类似，也会先 hash，再定位 table/group/slot。找到 key 后要做三件事：

used--，更新 map 和 table 的元素数量。
清理 key/elem 内存，尤其是包含指针的对象，避免 GC 继续把它们当成可达对象。
更新 control byte：设为 empty 或 deleted。

为什么有时不能直接设为 empty？因为开放寻址里查找遇到 empty 就会停止。如果一个 slot 位于某个探测链中间，直接设 empty 可能让后面的 key 永远查不到。

所以 full map 删除时有两种情况：

1
2
3
4
5
group 里还有 empty slot:
    当前 slot 可以设为 empty

group 原本是满的:
    当前 slot 必须设为 deleted，也就是 tombstone

流程图：

  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 有三个和容量相关的字段：

1
2
3
4
5
6
type table struct {
    used       uint16
    capacity   uint16
    growthLeft uint16
    ...
}

capacity 是 slot 总数，必须是 2 的幂。最大平均负载因子是 7/8：

1
const maxAvgGroupLoad = 7

正常 table 的可继续插入数量是：

1
growthLeft = (capacity * 7) / 8 - used - tombstones

当 growthLeft == 0 时，插入会触发 rehash：

1
2
3
4
5
6
7
8
9
func (t *table) rehash(typ *abi.MapType, m *Map) {
    newCapacity := 2 * t.capacity
    if newCapacity <= maxTableCapacity {
        t.grow(typ, m, newCapacity)
        return
    }

    t.split(typ, m)
}

Go 1.26.3 里单个 table 的最大容量是 1024：

1
const maxTableCapacity = 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 索引：

1
2
3
4
5
6
func (m *Map) directoryIndex(hash uintptr) uintptr {
    if m.dirLen == 1 {
        return 0
    }
    return hash >> (m.globalShift & 63)
}

示意：

1
2
3
4
5
6
7
globalDepth = 2

hash 高 2 位:
  00 -> directory[0] -> table A
  01 -> directory[1] -> table A   // 多个目录项可以指向同一个 table
  10 -> directory[2] -> table B
  11 -> directory[3] -> table C

一个 table split 后，directory 中原来指向它的一段索引会改成分别指向 left/right。如果当前 directory 深度不够，先扩一倍。

遍历 map

for k, v := range m 对 map 的要求比看上去复杂。语言规范允许遍历期间修改 map，并规定了几个语义：

不保证遍历顺序。
遍历期间新增的元素可能出现，也可能不出现。
遍历期间删除还没访问到的元素，不应该再被返回。
同一个元素不能返回两次。

runtime 用 maps.Iter 保存遍历状态：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
type Iter struct {
    key  unsafe.Pointer
    elem unsafe.Pointer
    typ  *abi.MapType
    m    *Map

    entryOffset uint64
    dirOffset   uint64
    clearSeq    uint64
    globalDepth uint8
    dirIdx      int
    tab         *table
    group       groupReference
    entryIdx    uint64
}

初始化时会随机化起点：

1
2
it.entryOffset = rand()
it.dirOffset = rand()

所以 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 会设置两个随机偏移：

1
2
it.entryOffset = rand()
it.dirOffset = rand()

后续遍历 directory 和 slot 时都会带上这两个偏移：

1
2
dirIdx := int((uint64(it.dirIdx) + it.dirOffset) & uint64(it.m.dirLen-1))
entryIdx := (it.entryIdx + it.entryOffset) & entryMask

因此，同一个 map 连续 range 两次，也可能得到不同顺序。这个设计有两个直接效果：

避免开发者误以为 map 有稳定顺序，并在业务代码里依赖这个实现细节；
让不同 hash seed、不同扩容状态下的遍历行为更接近语言规范里的「顺序未指定」。

如果业务上需要顺序，必须自己定义顺序。最常见做法是先收集 key，再排序，然后按排序后的 key 访问 map：

1
2
3
4
5
6
7
8
9
keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
slices.Sort(keys)

for _, k := range keys {
    fmt.Println(k, m[k])
}

遍历最麻烦的是扩容期间的语义。源码里的策略是：

如果遍历开始时的 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：

1
2
3
4
5
6
7
runtime/map_fast32.go
runtime/map_fast64.go
runtime/map_faststr.go

internal/runtime/maps/runtime_fast32.go
internal/runtime/maps/runtime_fast64.go
internal/runtime/maps/runtime_faststr.go

它们分别服务于常见 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 可以读，不能写

1
2
3
4
5
6
var m map[string]int

fmt.Println(m["x"]) // 0
fmt.Println(len(m)) // 0

m["x"] = 1 // panic: assignment to entry in nil map

查询 nil map 会返回元素零值；写入 nil map 会 panic。修复方式是先 make：

1
2
m = make(map[string]int)
m["x"] = 1

判断 key 是否存在必须用 ok

1
2
3
4
m := map[string]int{"a": 0}

fmt.Println(m["a"]) // 0
fmt.Println(m["b"]) // 0

只看返回值分不清 key 存在且值为零，还是 key 不存在。应该写：

1
v, ok := m["a"]

底层上，缺失 key 会返回 zeroVal，ok 才是存在性信息。

map 不是并发安全的

runtime 里有 writing 标志，会尽量发现并发问题：

1
2
3
fatal: concurrent map writes
fatal: concurrent map read and map write
fatal: concurrent map iteration and map write

这只是运行时检测，不是同步机制。并发读写 map 必须用 sync.Mutex、sync.RWMutex，或者在适合的读多写少场景使用 sync.Map。

map 元素不能取地址

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

// _ = &m["a"] // 编译错误

根本原因是 map 扩容、rehash、split 都可能移动元素位置。允许用户拿到元素地址会破坏 runtime 对内部存储的管理。

如果值是结构体，不能直接改字段：

1
2
3
4
5
6
7
type User struct {
    Name string
}

m := map[int]User{1: {Name: "old"}}

// m[1].Name = "new" // 编译错误

常见写法是取出、修改、再放回：

1
2
3
u := m[1]
u.Name = "new"
m[1] = u

或者让 map 存指针：

1
2
m := map[int]*User{1: {Name: "old"}}
m[1].Name = "new"

遍历顺序不稳定

1
2
3
4
5
6
7
8
9
m := map[string]int{
    "a": 1,
    "b": 2,
    "c": 3,
}

for k := range m {
    fmt.Println(k)
}

不要依赖输出顺序。需要稳定顺序时，先把 key 拿出来排序：

1
2
3
4
5
6
7
8
9
keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
slices.Sort(keys)

for _, k := range keys {
    fmt.Println(k, m[k])
}

delete 不会缩容

delete 会清理 slot，并可能留下 tombstone。后续插入可能复用这些位置，rehash 也会清理 tombstone，但 map 不会因为大量删除自动把 directory/table 缩小。

如果一个大 map 删到很小且长期保留，想释放内存，通常直接新建一个 map：

1
2
3
4
5
6
old := bigMap
newMap := make(map[string]int, len(old))
for k, v := range old {
    newMap[k] = v
}
bigMap = newMap

如果只是清空并复用，可以用 Go 1.21 引入的内置函数：

1
clear(m)

clear 会删除所有元素，但它的目标是清空内容，不是保证缩容。

大 key / 大 value 可能间接存储

abi.MapType 里有两个标志：

1
2
func (mt *MapType) IndirectKey() bool
func (mt *MapType) IndirectElem() bool

Go 的常量里也能看到阈值：

1
2
3
4
const (
    MapMaxKeyBytes  = 128
    MapMaxElemBytes = 128
)

超过阈值的 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 的实现去理解。

参考资料

#Go #Map #底层原理 #Runtime

Go map 底层实现原理全解析

Related posts