跳到主要内容Go 1.24 Map 底层重构解析:Swiss Table 与分层结构 | 极客日志Go / Golang算法
Go 1.24 Map 底层重构解析:Swiss Table 与分层结构
Go 1.24 对 map 进行了底层重构,采用 Swiss Table 风格的分层结构(Directory + Tables),替代了旧版的 overflow bucket 链式存储。新架构通过 H1/H2 哈希拆分实现快速过滤,利用 Group 探测优化缓存局部性,并引入 extendible hashing 风格的 split 扩容方案以减少延迟。虽然性能在微基准中提升显著,但并发安全边界未变,迭代语义维护仍是难点。
漫步1 浏览
hmap、bucket、每个桶 8 个槽位、满了挂 overflow bucket、扩容时搬桶。
这套说法在很长一段时间里都没问题。可如果你现在还只会这么讲,那面对 Go 1.24 的 map,就已经不够了。
因为这次改的不是 API,而是底层组织方式。表面上你还是在写:
m := map[string]int{}
m["go"] = 124
可 runtime 里那张'哈希表'已经不是很多人熟悉的那张表了。
- Go 为什么要重写 map
- 新版 map 到底重构了什么
- 这件事对后端工程师、性能判断分别意味着什么
如果你读完之后,能把'Go 1.24 map = Swiss Table + extendible hashing 风格增长 + 语义兼容处理'这句话真正理解明白,这篇就值了。
注:Swiss Table 起源于 Google/Abseil 的高性能哈希表工程实现,因 C++ 版本出名
1. 为什么 Go 要重写 map
先说结论:旧版 map 不是不能用,而是继续往上做,越来越难。
旧版设计的核心问题,不在于它'查得不快',而在于它在冲突、高负载、扩容和遍历语义这几件事上,包袱越来越重。
最典型的一个包袱,就是 overflow bucket。
它的存在当然有价值。桶满了,总得先有地方放。但问题也正出在这里:一旦冲突集中,查找路径就会从'在一个桶里看几眼'慢慢变成'顺着链往后跳'。
经常写算法的都知道:这就相当于把 O(1) 的查找速度,硬生生地退化成了 O(n)。这时候 CPU 不喜欢,cache 也不喜欢,延迟更不会喜欢。
对后端来说,这不是教科书里的小瑕疵,而是线上会遇到的真问题:
- 热点 key 冲突时,单次查找成本会上升
- overflow 链一长,缓存局部性就差
- 扩容时既要搬数据,又要尽量别把单次请求延迟打高
- 迭代语义还不能乱,Go 对
range map 的行为是有约束的
所以 Go 1.24 的这次重构,本质上不是'换个更新潮的名词',而是一次针对旧瓶颈的结构性调整。
2. 旧版 map 到底卡在哪
每个 bucket 最多放 8 个槽位。冲突多了,就往后挂 overflow bucket。
这套设计的问题,不是功能不完整,而是几个成本会一起冒头。
主 bucket 还算连续,overflow 一挂上去,访问路径就不再那么'平'。现代 CPU 很吃缓存局部性,这种链式跳转会让命中率变差。
查找一个不存在的 key,本来应该尽快停下。可一旦 overflow 多,你得继续探、继续跳、继续比,空查也会被拖慢。
旧版要靠 oldbuckets + nevacuate 渐进迁移,把一次性重分布拆散到后续操作里。这套办法很聪明,但也说明了另一件事:增长这件事本身已经很重了。
只要结构里有冲突链、删除标记、迁移状态,时间一长,表就会越来越不像一张'干净的表'。
旧版 map 的主问题,不是不能冲突,而是冲突后的代价越来越依赖 overflow 链,结构会越跑越重。
3. 新版整体结构:map -> directory -> tables -> groups -> slots
Go 1.24 的新实现,第一眼最容易看错的地方是:它不是'把 bucket 改名成了 Swiss Table'。
Map -> Directory -> Table -> Group -> Slot
Map:顶层容器,持有元数据
Directory:一个索引层,用来把哈希空间分给多个 table
Table:独立的哈希表实例,table 内部使用 Swiss Table 风格组织
Group:最小探测单位,包含 8 个 slot
Slot:真正放 key/value 的位置
它不是'一张大表加一堆 overflow 桶',而是'顶层 directory + 底层多个 table'的分层结构。
旧版本:
主表 [桶 0] [桶 1] [桶 2] [桶 3] ... 桶 2 满了 [桶 2] -> [overflow1] -> [overflow2]
Go 1.24 之后
directory ├── 指向 table A
├── 指向 table B
├── 指向 table C
└── 指向 table D
table A: 存一部分 key
table B: 存一部分 key
table C: 存一部分 key
table D: 存一部分 key
把原来'一张总表'拆成了'directory + 多个底层 table'的两层结构。
顺带一提,小 map 还有专门优化。元素很少时,路径会更短,不需要一开始就把目录层玩得很重。这一点很工程化,因为真实业务里小 map 并不少。
这件事在官方源码里说得很直白:如果一个 map 始终不超过 8 个元素,它可以直接塞进单个 group,dirLen 会保持为 0,连真正的 directory 都不用展开。并且这种 small map 不会留下 deleted slot,因为它本身就没有需要维护的 probe 链。
换句话说就是:由于这种小 map 的查找不依赖复杂的探测链,所以删除元素时也不需要保留'已删除但不能当成空位'的墓碑标记。
4. group / control word / H1 / H2 各自负责什么
如果说旧版 map 的标志性结构是 bucket + tophash,那新版的标志性结构就是 group + control word。
一个 group 里有 8 个 slot。这个'8'很关键,因为它既是存储单位,也是探测单位。查找时不是一个槽一个槽慢慢问,而是先看这一组里谁有可能命中。
它本质上就是 8 字节,对应这 8 个 slot。你可以把它理解成一块'组内导航板':
- 哪些 slot 是空的
- 哪些 slot 被删过
- 哪些 slot 是已占用
- 已占用 slot 上还保留了一个简短的
H2
一个 key 做完哈希之后,不是整个哈希值一起乱用,而是拆成两部分:
H1:在 64 位系统上取哈希的高 57 位,负责选 table、决定 probe 路径
H2:取低 7 位,负责在 group 内做快速过滤
它只是'先帮你排除大部分不可能命中的槽位'。真正命中了候选 slot,最后仍然要做完整 key compare。
这一步非常重要。因为真正贵的,不是看一个字节状态,而是去比完整 key。尤其是字符串 key、长结构体 key、或者需要间接访问的 key。
所以新版 map 的一个核心收益,就是把'重比较'尽量往后推,只在必要的时候做。
5. 一次查找到底怎么走
hash(key) -> 拆成 H1 / H2 -> 用 H1 选 directory 和 table -> 按 probe sequence 找到目标 group -> 读取 control word,批量过滤候选 slot -> 对候选做完整 key compare -> 命中则返回;遇到 empty 可停止
这里最值得记住的,不是步骤顺序,而是新版 map 的查找哲学变了:
这跟旧版 overflow bucket 的思路很不一样。
旧版冲突多了,本质上是在'往后接更多位置';而新版更强调'在连续空间里更快地判断哪些位置值得看'。一个是链式补救,一个是探测优化。
因为 group 是连续的,control word 也是连续的,查找路径更容易保持在局部内存里完成。对 cache 更友好,对 miss 的处理也更利落。
遇到 empty 就可以停,是开放寻址类结构里很关键的终止信号。
6. 为什么扩容方案不是旧版搬桶,而是 split
新版 map 还是要增长,但增长方式变了。它不再默认把一整张大表一起重分布,而是更接近 extendible hashing 的思路。
一个 map 会先从单个 table 起步;在单 table 容量还没到上限前,增长就是把这个 table 扩成更大的 table;超过上限之后,才不再继续把同一张表做大,而是把它 split 成两张 table。当前这个单 table 上限是 1024 个条目。
注:(一个 map 对应一个 directory,一个 directory 可以对应多个目录项,也就是全局索引)
globalDepth 表示 directory 当前用多少位来做全局索引
localDepth 表示某个 table 当前真正关心多少位
意味着多个 directory index 可以共享同一个 table。只有当某个 table 压力真的上来了,才需要把这个 table 拆成两个,也就是 split。
如果局部拆分之后,directory 现有位数还够,就只更新部分映射关系。
这跟旧版'整张表一起翻倍,然后慢慢 evacuate'是两种味道。
顶层 directory 负责分流,局部 table 负责独立增长,必要时再做 split。
- 增长动作更局部
- 单次重分布范围更可控
- 更容易把延迟打散,而不是集中爆一次
这也是为什么很多材料会说:Go 1.24 的 map,不只是用了 Swiss Table,还把增长方案一起重做了。
7. 为什么 iteration 最难,以及 Go 1.24 如何维持语义
如果只做查找和插入,新版 map 其实已经很好理解了。真正麻烦的,是 iteration。
因为 Go 对 range map 的语义不是'随便遍历一下就行',而是有实际约束的。典型地说:
- 尚未遍历到的元素,如果先被删掉了,后面不该再返回
- 已有元素如果被更新了,返回时应该看到更新后的值
- 新插入元素,可能返回,也可能不返回
- table 可能 split
- 元素可能迁移
- 删除可能留下 tombstone
- 当前路径看到的是旧位置,真实数据可能已经去了新位置
所以 iteration 难,不是因为'遍历很慢',而是因为:
你要在底层结构持续变化的前提下,尽量维持 Go 语言层面对遍历结果的承诺。
原则上:Go 1.24 的处理思路可以概括成两步:
- iterator 继续沿着旧 table 的遍历顺序往前走
- 在返回元素之前,再去当前状态下确认这个元素是不是还有效、值是不是已经变化
这就是为什么很多人说:新 map 最难的不是查找,不是扩容,而是 iteration 语义。
底层重构了,不代表原生 map 就变成并发安全了。它依旧不支持并发写,读写并发依旧不安全,照样可能触发运行时问题。
8. 工程结论:哪些收益是真的,哪些点最容易讲错
如果只看 map 内核本身,这次重构带来的方向很明确:
- 冲突处理更偏向连续探测,而不是 overflow 链
- 无效 key compare 更少
- cache 局部性更好
- 增长动作更局部,延迟更容易控
所以说,Go 1.24 之后的 map,相较于老 map:
- 大 map、高负载、冲突更明显的场景,收益通常更容易体现
- 小 map 也有优化,但不一定每个业务都能感到巨大差异
map 相关微基准里,操作性能最高可以比 Go 1.23 快到 60%
- 但放到完整应用基准里,几何平均 CPU 改善大约在
1.5%
- 同时官方也明确提到,少数边缘场景会有回退
9. 自测
Go 1.24 的 map 是分层结构,顶层有 directory,下面是多个 table。
它只是组内快速过滤,最后仍然要做完整 key compare。
需要 tombstone 这一类状态来维持 probe 链的完整性。
第四,新版不是旧版 oldbuckets 搬迁模型的换皮。
它的增长思路更接近 extendible hashing 风格的 split。
不要把'底层重构'误讲成'原生 map 更适合并发写了'。
一分钟复盘:
Go 1.24 之前,经典 map 的核心是 hmap + bucket + overflow bucket。它能工作,但冲突多时会出现 overflow 链,缓存局部性和查找路径都会变差。Go 1.24 把 map 底层重构成了分层结构:顶层是 directory,下面挂多个 table,table 内部采用 Swiss Table 风格的 group + control word + open addressing。查找时先把 hash 拆成 H1 / H2,H1 负责选 table 和 probe,H2 负责组内快速过滤,最后再做完整 key compare。增长方式也不再是旧版整表搬迁那套思路,而是更接近 extendible hashing 的局部 split。最难的是 iteration,因为底层结构在变,但 Go 还得维持既有遍历语义。要注意的是,这次重构提升的是性能和组织方式,不是并发语义,原生 map 依旧不支持并发写。
深度思考:
- 为什么旧版 map 的瓶颈会出现在 overflow 上
- 为什么新版要把查找改成 group 探测
- 为什么最难的不是查,而是边增长边维持 iteration 语义
参考资料
微信扫一扫,关注极客日志
微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
相关免费在线工具
- 加密/解密文本
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
- Base64 字符串编码/解码
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online
- Base64 文件转换器
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具,Base64 文件转换器在线工具,online
- Markdown 转 HTML
将 Markdown(GFM)转为 HTML 片段,浏览器内 marked 解析;与 HTML 转 Markdown 互为补充。 在线工具,Markdown 转 HTML在线工具,online
- HTML 转 Markdown
将 HTML 片段转为 GitHub Flavored Markdown,支持标题、列表、链接、代码块与表格等;浏览器内处理,可链接预填。 在线工具,HTML 转 Markdown在线工具,online
- JSON 压缩
通过删除不必要的空白来缩小和压缩JSON。 在线工具,JSON 压缩在线工具,online