Go 的 map 在 Go 1.24 换了一次底层实现：从「桶 + 溢出链」的链式哈希，换成 Google 的 Swiss Table（开放寻址哈希表）。官方基准：插入、查找、删除快约 20%–50%，迭代快约 10%，内存最多省 25%。这篇先讲老实现，再讲新实现，最后给对比。
老实现（Go 1.23 及更早）：桶 + 溢出链
结构
map 的主体是 hmap，核心字段：
type hmap struct {
count int // 元素个数
B uint8 // 桶数量 = 2^B
hash0 uint32 // 哈希种子，创建 map 时随机生成
buckets unsafe.Pointer // 桶数组
oldbuckets unsafe.Pointer // 扩容前的旧桶数组，迁移完为 nil
nevacuate uintptr // 增量迁移进度：下一个要迁移的旧桶下标
noverflow uint16 // 溢出桶数量
extra *mapextra
}
每个桶是 bmap，固定装 8 个键值对，布局是编译期拼出来的：
type bmap struct {
tophash [8]uint8 // 每个 key 哈希值的高 8 位
// 接下来是 8 个 key 连续存放
// 再是 8 个 value 连续存放
// 最后是一个 overflow 指针，指向溢出桶
}
key 和 value 分开连续存放（不是 key1,val1 交替），各自按类型对齐，省内存。key 或 value 体积大、或含指针时，存的是指针。
查找流程
一次查找走四步：
- 用 hash0 种子和哈希函数算出 64 位哈希；
- 取哈希的低 B 位当桶下标，定位到桶；
- 用高 8 位（tophash）预筛：先比 1 字节的 tophash，命中再比完整 key；
- 8 个槽位都不中，顺着 overflow 指针去溢出桶继续找。
tophash 预筛是核心优化：大多数 key 不匹配，比 1 字节就淘汰，不用碰完整 key。
扩容
装载因子超过 6.5（count / 2^B > 6.5）触发扩容，分两种：
- 翻倍扩容：桶数翻倍，多取一位哈希分散数据；
- 等量扩容：桶数不变，把散在溢出桶的数据搬回前面排布，顺带清理溢出桶。
扩容是增量的：每次读写顺带迁移 nevacuate 指向的旧桶，全部搬完 oldbuckets 置空。扩容期间查找要先查新桶、不中再查旧桶。这样避免扩容瞬间卡顿。
删除只是把槽位标记为空，不立即释放内存，等扩容或 GC 回收。反复增删的大 map 可能内存居高不下。
新实现（Go 1.24+）：Swiss Table
提案是 golang/go #54766，字节跳动工程师 2022 年提出——当时实测 map 操作占服务 CPU 约 4%。实现基于 Peter Mattis 的 cockroachdb/swiss，即 Google Abseil 的 Swiss Table 同款设计，代码在 internal/runtime/maps 包。
结构
没有溢出桶。数据是一块连续的 group 数组，每个 group = 8 个槽位 + 8 字节控制字（control word）：
group:
┌──────────────────────────────┐
│ 控制字 8 字节：每字节管一个槽位 │
│ 状态：空 / 已删除 / 已占用 │
│ 占用时低 7 位存哈希的 H2 │
├──────────────────────────────┤
│ 槽位 0 ~ 7：8 个 key/value │
└──────────────────────────────┘
哈希分成两段：H1 是高 57 位，用于定位 group；H2 是低 7 位，存进控制字节。
查找
- 按 H1 定位到 group；
- 在 group 内开放寻址探测，用 SWAR/SIMD 一次并行比较 8 个控制字节里的 H2；
- 命中 H2 的槽位再比完整 key。
大多数查找只碰控制字节，完全不读 key。这是性能提升的主要来源。
删除：tombstone
删除不直接清空，而是标记成 tombstone（墓碑）。开放寻址的探测序列依赖「连续的已占用槽位」，直接清空会截断别人的探测路径。墓碑攒到超过容量约 10% 时统一清理（pruneTombstones）。
装载因子与扩容
最大装载因子 7/8：每 group 最多 7 个元素，必须留 1 个空位保证探测能终止。比老版「每桶 6.5 个 + 溢出桶」更紧凑，这是内存减少的原因。
增量扩容的思路和老版完全不同。开放寻址的探测序列依赖 group 总数，一张表要重排就得整体重建，没法像老版那样按桶搬。Swiss Table 用可扩展哈希（extendible hashing）解决：
- 一个 map 是多张表，目录（directory）按哈希的高位索引指向各表；
- 每张表独立管理自己的装载因子；
- 表容量到 1024 个 group 后不翻倍，而是拆成两张表，目录加一个索引位。
扩容变成局部操作：只有被拆的那张表要重排，其余表不动。
对比
| 维度 | 老实现（≤1.23） | Swiss Table（≥1.24） |
|---|---|---|
| 冲突处理 | 链式：溢出桶链表 | 开放寻址 + 探测序列 |
| 单元容量 | 8 槽 + 溢出链 | group 8 槽，无溢出 |
| 预筛方式 | tophash 高 8 位 | 控制字节 H2，SWAR 并行比 8 个 |
| 装载因子 | 6.5 / 桶 | 7 / 8 |
| 删除 | 标记空位 | tombstone + 定期清理 |
| 扩容 | 翻倍/等量 + 双数组迁移 | 目录 + 表拆分（extendible hashing） |
| 内存 | 溢出桶碎片 | 连续紧凑，省 0–25% |
| 性能 | 基线 | 增删查快约 20–50% |
行为特性一条没变：遍历依然无序且随机、并发写依然 panic、map 依然不能取地址、键依然要求可比较。sync.Map 用自己的独立实现，不受这次替换影响。
参考资料
- golang/go #54766：Swiss Table 提案，https://github.com/golang/go/issues/54766
- golang/go #70849：小 map 性能回退修复
- golang/go #80428：ixmap 实验，评估可扩展哈希是否再换实现
- 源码：go.dev/src/internal/runtime/maps/
