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`](https://go.googlesource.com/go/+/refs/tags/go1.26.3/src/runtime/map.go) 和 [`src/internal/runtime/maps`](https://go.googlesource.com/go/+/refs/tags/go1.26.3/src/internal/runtime/maps/)，按数据结构、创建、查询、写入、删除、扩容和遍历几个路径梳理 map 的真实执行过程。核心结论先放前面： - Go 1.26.3 的 map 核心实现位于 `internal/runtime/maps`，`runtime/map.go` 主要是编译器、reflect 和 runtime 之间的转发层。 - 新实现基于 [Abseil Swiss Table](https://abseil.io/about/design/swisstables) 思路，每 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` 定义，它引入的是： ```go import "internal/runtime/maps" ``` `makemap`、`mapaccess1`、`mapassign`、`mapdelete` 等入口最终都落到 `maps.Map` 上： ```go 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 的顶层结构： ```go 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 看成下面这个层次： ```text 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。 ```mermaid flowchart TD A["用户代码里的 map 变量"] --> B["*maps.Map"] B --> C["used
元素数量，len(m) 读取它"] B --> D["seed
每个 map 独立的 hash 种子"] B --> E["dirPtr / dirLen"] B --> F["globalDepth / globalShift
directory 选 table"] B --> G["writing
并发写检测"] E --> H{"dirLen == 0?"} H -->|是，小 map| I["dirPtr -> group"] I --> J["ctrlGroup
8 个 control byte"] I --> K["8 个 slot
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]` 查询，可以简化成下面这条路径： ```mermaid flowchart TD A["m[key]"] --> B{"m == nil 或 used == 0?"} B -->|是| Z["返回元素零值 / ok=false"] B -->|否| C["hash = Hasher(key, seed)"] C --> D["拆分 hash
H1 = 高位
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()
继续下一个 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](https://abseil.io/about/design/swisstables)。它的核心不是发明一种新的哈希函数，而是把「怎么在哈希冲突下更快找到候选位置」这件事做得更紧凑。传统开放寻址哈希表通常是这样查找： ```text 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 位。于是一次查询变成两阶段： ```text 第一阶段：只看 metadata，快速筛出 H2 相同的候选 slot 第二阶段：只对候选 slot 做完整 key 比较 ``` 用图表示： ```text 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。源码里也保留了同样的抽象： ```go 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： ```go const MapGroupSlotsBits = 3 const MapGroupSlots = 1 << MapGroupSlotsBits // 8 ``` 一个 group 的逻辑布局是： ```go type group struct { ctrls ctrlGroup slots [8]slot } type slot struct { key typ.Key elem typ.Elem } ``` 源码里没有直接写出这个 Go 结构体，而是由编译器根据 key/elem 类型生成对应布局。`groupReference` 通过偏移拿到 key 和 elem： ```go 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 有三种状态： ```text empty: 1000 0000 deleted: 1111 1110 full: 0hhh hhhh // h 是 hash 的低 7 位，也就是 H2 ``` 查找时不会直接逐个比较 8 个 key，而是先用 control word 一次筛出 H2 相同的候选 slot： ```go func (g ctrlGroup) matchH2(h uintptr) bitset { return ctrlGroupMatchH2(g, h) } ``` 这一步可能有假阳性，因为 H2 只有 7 bit，平均每 128 个 slot 会有一个控制字节碰上。但这没关系，runtime 会继续调用 key 的 Equal 函数做完整比较。control word 的价值是先把绝大多数不可能匹配的 slot 排除掉。内存布局可以这样理解： ```text 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： ```go hash := typ.Hasher(key, m.seed) ``` Go 把 hash 拆成 H1 和 H2： ```go func h1(h uintptr) uintptr { return h >> 7 } func h2(h uintptr) uintptr { return h & 0x7f } ``` 两者分工不同： - H1：高位，用来选择 table 和 group，决定从哪里开始探测。 - H2：低 7 位，写进 control byte，用来快速筛候选 slot。完整查询路径大致是： ```mermaid 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 常见创建方式： ```go m := make(map[string]int) m2 := make(map[string]int, 100) ``` 入口是 `makemap`，它会调用 `maps.NewMap`。关键逻辑是： ```go 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。执行路径： ```mermaid 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 第一次写入时： ```go 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。简化后的写入路径： ```mermaid 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 写进去是外层做的： ```go func (m *Map) Put(typ *abi.MapType, key, elem unsafe.Pointer) { slotElem := m.PutSlot(typ, key) typedmemmove(typ.Elem, slotElem, elem) } ``` 这也解释了为什么 map 元素不能取地址： ```go // 编译错误：cannot take address of m["a"] _ = &m["a"] ``` map 写入可能触发 table 重建，元素位置并不稳定。允许用户长期持有元素地址，会让 runtime 无法移动和重排 slot。 --- ## 探测序列 full map 查找一个 key 时，不一定一次就落到正确 group。碰撞时需要继续探测后续 group。 Go 1.26.3 使用二次探测，源码注释给出的形式是： ```text p(i) = hash + (i^2 + i)/2 (mod mask+1) ``` 实现很短： ```go 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 元素删除入口是： ```go delete(m, key) ``` 删除和查询类似，也会先 hash，再定位 table/group/slot。找到 key 后要做三件事： 1. `used--`，更新 map 和 table 的元素数量。 2. 清理 key/elem 内存，尤其是包含指针的对象，避免 GC 继续把它们当成可达对象。 3. 更新 control byte：设为 empty 或 deleted。为什么有时不能直接设为 empty？因为开放寻址里查找遇到 empty 就会停止。如果一个 slot 位于某个探测链中间，直接设 empty 可能让后面的 key 永远查不到。所以 full map 删除时有两种情况： ```text group 里还有 empty slot: 当前 slot 可以设为 empty group 原本是满的: 当前 slot 必须设为 deleted，也就是 tombstone ``` 流程图： ```mermaid 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 有三个和容量相关的字段： ```go type table struct { used uint16 capacity uint16 growthLeft uint16 ... } ``` `capacity` 是 slot 总数，必须是 2 的幂。最大平均负载因子是 7/8： ```go const maxAvgGroupLoad = 7 ``` 正常 table 的可继续插入数量是： ```go growthLeft = (capacity * 7) / 8 - used - tombstones ``` 当 `growthLeft == 0` 时，插入会触发 `rehash`： ```go 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： ```go const maxTableCapacity = 1024 ``` 因此扩容有两种： ```mermaid 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 索引： ```go func (m *Map) directoryIndex(hash uintptr) uintptr { if m.dirLen == 1 { return 0 } return hash >> (m.globalShift & 63) } ``` 示意： ```text 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` 保存遍历状态： ```go 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 } ``` 初始化时会随机化起点： ```go it.entryOffset = rand() it.dirOffset = rand() ``` 所以 map 遍历顺序不是插入顺序，也不是 hash 顺序。它是有意随机化的。 ### 为什么遍历不按顺序返回 map 没有「顺序」这个语义。它不是数组、slice 或链表，内部也不会记录 key 的插入先后。元素放在哪个 slot，主要取决于： 1. key 的 hash 值； 2. 每个 map 独立的随机 hash seed； 3. 当前 table/directory 的大小； 4. 碰撞后探测序列找到的空 slot； 5. 后续 grow、split、delete 留下的 tombstone。同一批 key，只要 map 的 seed 不同，hash 结果就可能不同；同一个 map，只要扩容或 split 发生，元素也可能被重新分布到新的 table/group 中。所以 runtime 没有稳定的「从第一个插入的元素开始遍历」这种信息可用。即使暂时不考虑扩容，遍历也不是从第 0 个 directory、第 0 个 group、第 0 个 slot 固定开始。`Iter.Init` 会设置两个随机偏移： ```go it.entryOffset = rand() it.dirOffset = rand() ``` 后续遍历 directory 和 slot 时都会带上这两个偏移： ```go 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： ```go 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]) } ``` 遍历最麻烦的是扩容期间的语义。源码里的策略是： 1. 如果遍历开始时的 table 后续被 grow/split，iterator 仍然保留旧 table，用旧 table 决定哪些 key 已经走过。 2. 返回元素前，再去当前 map 里按 key 查一次。 3. 如果 key 已删除，就跳过。 4. 如果 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： ```text 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 可以读，不能写 ```go 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`： ```go m = make(map[string]int) m["x"] = 1 ``` ### 判断 key 是否存在必须用 ok ```go m := map[string]int{"a": 0} fmt.Println(m["a"]) // 0 fmt.Println(m["b"]) // 0 ``` 只看返回值分不清 key 存在且值为零，还是 key 不存在。应该写： ```go v, ok := m["a"] ``` 底层上，缺失 key 会返回 `zeroVal`，`ok` 才是存在性信息。 ### map 不是并发安全的 runtime 里有 `writing` 标志，会尽量发现并发问题： ```text 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 元素不能取地址 ```go m := map[string]int{"a": 1} // _ = &m["a"] // 编译错误 ``` 根本原因是 map 扩容、rehash、split 都可能移动元素位置。允许用户拿到元素地址会破坏 runtime 对内部存储的管理。如果值是结构体，不能直接改字段： ```go type User struct { Name string } m := map[int]User{1: {Name: "old"}} // m[1].Name = "new" // 编译错误 ``` 常见写法是取出、修改、再放回： ```go u := m[1] u.Name = "new" m[1] = u ``` 或者让 map 存指针： ```go m := map[int]*User{1: {Name: "old"}} m[1].Name = "new" ``` ### 遍历顺序不稳定 ```go m := map[string]int{ "a": 1, "b": 2, "c": 3, } for k := range m { fmt.Println(k) } ``` 不要依赖输出顺序。需要稳定顺序时，先把 key 拿出来排序： ```go 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： ```go old := bigMap newMap := make(map[string]int, len(old)) for k, v := range old { newMap[k] = v } bigMap = newMap ``` 如果只是清空并复用，可以用 Go 1.21 引入的内置函数： ```go clear(m) ``` `clear` 会删除所有元素，但它的目标是清空内容，不是保证缩容。 ### 大 key / 大 value 可能间接存储 `abi.MapType` 里有两个标志： ```go func (mt *MapType) IndirectKey() bool func (mt *MapType) IndirectElem() bool ``` Go 的常量里也能看到阈值： ```go 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 1.26.3 runtime/map.go](https://go.googlesource.com/go/+/refs/tags/go1.26.3/src/runtime/map.go) - [Go 1.26.3 internal/runtime/maps](https://go.googlesource.com/go/+/refs/tags/go1.26.3/src/internal/runtime/maps/) - [Abseil Swiss Tables Design Notes](https://abseil.io/about/design/swisstables) - [Go spec: Map types](https://go.dev/ref/spec#Map_types) - [Go 1.26 Release Notes](https://go.dev/doc/go1.26)