Interview Lab / Go / Map / Classic

Go 经典 Map：hmap、bmap、bucket 与渐进扩容

“经典实现”指 Go 1.23 及之前内置 map 的底层方案。hmap 是管理整张 map 的头部结构，bmap 是一个 bucket（桶）的底层结构；桶可以理解成一次容纳 8 组 key/value 的小盒子。标题里的渐进扩容表示容量增长时不一次搬完全部数据，而是让后续操作每次帮忙搬一小部分。

这篇文章只服务旧版源码和旧面试题，按“整体结构 → 桶内布局 → 查询 → 冲突 → 两种扩容 → 版本对照”展开。

Go 1.23 及之前hmap / bmap桶内 hash 摘要满桶后继续连接分批搬迁
不要当成当前实现：Go 1.24+ 默认已经改用 Swiss Table。学习当前 map 请回到Swiss Table 主线文章。旧题中的 tophash 是桶内 hash 摘要，overflow bucket 是溢出桶，oldbuckets 是旧桶数组，nevacuate 是迁移进度；出现这些词时，才使用本文这套回答。
一、先认识整套旧版术语
名词小白解释
hmap整张 map 的管理中心，记录元素数量、桶数组地址和扩容状态
bmap一个 bucket 的底层结构；每个主桶最多有 8 个槽位
tophash从 hash 高位提取的小摘要，用来快速排除不可能匹配的槽位
overflow bucket主桶装满后额外连接的溢出桶
oldbuckets扩容期间暂时保留的旧桶数组
nevacuate迁移进度，表示编号小于它的旧桶已经搬完
hmap管理整体
buckets主桶数组
bmap每桶 8 槽
tophash桶内初筛
overflow满后追加
先形成画面：hmap 像仓库管理员，buckets 是一排货架，每个 bmap 是有 8 个格子的货箱；货箱满了，再接 overflow 货箱。
二、hmap：整张旧 map 的管理中心

hmap 是整张经典 map 的“管理表”。它不直接把所有 key/value 塞进自己，而是记录元素数量、随机种子、当前桶数组，以及扩容搬到哪了。

type hmap struct {
    count      int            // 当前元素数量，len(m) 读取它
    B          uint8          // 主 bucket 数量 = 2^B
    noverflow  uint16         // overflow bucket 的近似数量
    hash0      uint32         // 每张 map 自己的随机 hash 种子
    buckets    unsafe.Pointer // 当前主桶数组
    oldbuckets unsafe.Pointer // 扩容期间的旧桶数组
    nevacuate  uintptr        // 旧桶迁移进度
}

uint8/uint16/uint32 是不同位数的无符号整数类型；unsafe.Pointer 是可以保存内存地址的通用指针类型。这里理解字段职责即可，不需要死背声明。

hmap 管理 bucket 数组的整体结构 左侧 hmap 保存 count、B、hash0、buckets、oldbuckets 和 nevacuate，右侧展示当前桶数组以及扩容时暂存的旧桶数组。 hmap 自己不装货，它负责管理“货架” hmap 管理表 count23 个元素 B3 → 2³=8 桶 hash0随机种子 buckets当前桶数组 oldbuckets扩容时才有 nevacuate搬迁进度 buckets → 当前 8 个主桶 bucket 08 个槽 bucket 18 个槽 bucket 2正在访问 … bucket 7共 2ᴮ 个 每个 bucket 本质上是一个 bmap 最多 8 组 key/value；装满后可连接 overflow bucket 真正的数据主要放在这里，不在 hmap 字段里 扩容期间才同时存在 oldbuckets 旧桶 0 ✓已迁移 旧桶 1 ✓已迁移 旧桶 2下一个 旧桶 3…待迁移 迁移完成后，oldbuckets 会被清空
先记住层级：hmap → buckets 数组 → bmap 桶 → 8 个槽位 → overflow 桶。后面所有查询与扩容都在这张图上发生。

B 是指数：当 B=3 时，主桶数量是 2³=8；当 B 增加 1，主桶数量就翻倍。hash0 是随机种子，可以理解成每张 map 各自的一份“调味料”，让同一个 key 在不同 map 中不必得到相同的 hash。

不要死背所有字段。面试重点是：count 管长度、B 管桶数量、buckets/oldbuckets 管新旧桶、nevacuate 管迁移进度。
三、bmap：一个 bucket 里面怎样放 8 组数据

bmap 是一个具体的桶。可以把它想成一个有 8 列的收纳盒：同一列的 tophash[i]、key[i] 和 value[i] 共同描述一条数据。

bmap 的八个槽位和连续内存布局 一个 bmap 先连续保存 8 个 tophash，再连续保存 8 个 key 和 8 个 value，最后保存 overflow 指针；第 3 列被高亮，表示同一下标组成一条记录。 一个 bmap：8 列槽位，同列才是一组 key/value 槽位编号 01234567 tophash[8] keys[8] values[8] 0x310x8A0x420xA70x190xE20x76空 "ant""dog""fox""cat""bee""owl""yak"— 128599367— overflow 指针满了再指向下一个 bmap 第 3 列摘要 + key + value共同组成一条记录 先放 8 个 key，再放 8 个 value，可减少某些类型组合产生的内存对齐空隙。
查询时先横向扫第一行的 tophash；只有摘要相同，才向下比较同一列的完整 key，最后取同列 value。
不要误解：tophash 只是快速初筛，不是 key 的唯一身份。两个不同 key 可能拥有相同摘要，最终必须比较完整 key。
四、查询：低 B 位选桶，高位摘要筛槽

现在用一个具体例子查 m["cat"]。假设 B=3，主桶数量是 2³=8。hash 的低 3 位是 101，换成十进制就是 5，所以先去 buckets[5]。

一个 hash 同时提供 bucket 下标和 tophash hash 高 8 位 A7 生成 tophash，低 B 位 101 生成第 5 号 bucket 下标，中间位保留给完整 hash。 同一个 hash，被切成两种“路标” hash("cat", hash0) 高 8 位：A7生成 tophash 中间很多位……仍属于完整 hash 低 B 位：101选择 bucket 5 桶内先看摘要 先跳到第 5 桶 低位回答“去哪个桶”，高位摘要回答“桶里哪些槽值得比较”

完整查询过程：让 "cat" 从入口走到结果

经典 Go map 的七步完整查询流程 key cat 和随机种子计算 hash，低 B 位选择 bucket 5，高位生成 tophash A7；扫描主桶八个摘要，候选槽比较完整 key，未找到则继续 overflow，最终命中返回 value，否则返回零值且 ok 为 false。 查询 m["cat"]：先缩小范围，再确认完整 key 1 key "cat" + hash0交给该 key 类型的 hash 函数 2 得到完整 hash：A7…0101它是整数，页面用十六进制/二进制方便看位 3 高 8 位 A7 → tophash 同一个 hash 拆成两条线索 低 3 位 101 → bucket 5 4 跳到主 bucket 5，先扫 8 个 tophash 31A742A719E276空 只留下 A7两个候选 5 摘要相同，再比较完整 key 候选槽 1：key = "dog""dog" ≠ "cat" → 不是它 候选槽 3：key = "cat"完整 key 相等 → 命中 value=99 返回 99ok=true 6 主桶候选都不相等？沿 overflow 指针继续在每个 overflow bucket 中重复“扫摘要 → 比完整 key” 7 主桶和所有 overflow 都找完仍未命中返回 value 类型零值；value, ok := m[key] 时，ok=false
这 7 步的核心是不断缩小范围：完整 hash → 一个主桶 → 少数摘要候选 → 完整 key。overflow 只是主桶没找到时的续查路径。
常见错误：低 B 位只负责选择 bucket；tophash 只负责桶内初筛。真正命中必须比较完整 key。直接写 v := m[key] 时，未命中得到零值；需要区分“零值”和“不存在”时要用 v, ok := m[key]。
五、冲突：bucket 满了为什么需要 overflow

哈希冲突是不同 key 最终需要在同一个主 bucket 中查找。一个 bmap 只有 8 个槽；8 个都占用后，新元素不会覆盖旧元素，而是挂接一个 overflow bucket（溢出桶）继续存放。

主 bucket 装满后连接 overflow bucket 主 bucket 5 的八个槽都占满，overflow 指针连接 overflow bucket 1；查询时先扫主桶，再沿指针继续扫溢出桶。 overflow 不是“另一个主桶”，而是 bucket 5 的加长车厢 主 bucket 5先查这里 01234567 8 个槽全部占用 overflow 指针 overflow bucket 1主桶没找到再查 8910cat空空空空 链越长，查询需要跳到越多块内存；这是经典实现性能变差的重要来源。

overflow 越多，查询越可能跟着指针跳到更多内存位置。CPU cache 是处理器内部速度很快的一小块临时存储，它更喜欢相邻数据；长链会破坏这种内存局部性。

冲突不等于 hash 完全相同：只要低 B 位相同，就会先落到同一个主 bucket。即使 tophash 也相同，仍然要比较完整 key。
六、扩容：容量翻倍与等量扩容是两回事

负载因子表示平均每个主 bucket 放了多少元素。旧版插入数据时会观察两个信号：元素相对主桶是否太多，以及 overflow bucket 是否太多。

容量翻倍扩容

元素确实太多时，B 加 1，主桶数量从 2^B 变成 2^(B+1)。旧桶数据根据新增的那一位 hash 分到两个新位置。

等量扩容

元素未必很多，但 overflow 太多时，B 不变、主桶数量不变。runtime 建立同样大小的新桶数组，把有效数据重新摆紧凑。

翻倍扩容时旧桶的数据分流到两个新桶 旧 B 等于 2 时，旧桶 2 中的元素在新 B 等于 3 后查看新增的第 2 位；该位为 0 留在新桶 2，为 1 去新桶 6，也就是 2 加 2 的 oldB 次方。 翻倍扩容只多看 1 个 hash 位 例：oldB=2，旧桶 i=2；newbit = 1 << oldB = 4 旧 bucket 2旧定位只看低 2 位：10 key A新位=0 key B新位=1 新 bucket 2新增位为 0：原地编号不变key A 新 bucket 6新增位为 1：2 + 2² = 6key B X 路：留在 iY 路：去 i + 2^oldB 不是重新随机决定位置；只是原有低位前面再多看一位。
旧桶 i 翻倍后只可能去两个地方：i 或 i + 2^oldB。这就是经典面试题里的 X/Y 分流。

为什么不一次搬完：把一次大停顿拆成很多小搬运

如果 map 很大，一次搬完所有 bucket 会让某一次写操作突然停顿很久。因此旧版采用渐进迁移：新写操作发生时，顺手搬与本次访问相关的旧桶，并继续推进迁移进度。

oldbuckets 和 nevacuate 表示渐进迁移进度 新 buckets 已投入使用，旧桶 0 和 1 已迁移，nevacuate 等于 2 指向下一个待搬旧桶；本次写入先搬目标旧桶，再额外推进一个桶，最终 oldbuckets 清空。 扩容开始后：新旧两排桶暂时同时存在 buckets：新桶数组（正在使用） 新 0新 1新 2新 3新 4新 5新 6新 7 oldbuckets：旧桶数组（还没全部搬完） 旧 0 ✓ 已迁移槽位标记 evacuated旧 1 ✓ 已迁移数据已到新桶旧 2 ← 下一个nevacuate = 2旧 3仍待迁移 写growWork：先迁移本次将访问的旧桶，再推进 nevacuate 指向的旧桶每次只做一小部分，把总搬运成本分摊到后续写操作；全部完成后 oldbuckets=nil。 扩容期间查询会判断对应旧桶是否已经迁移，必要时仍从 oldbuckets 查。
面试一句话：负载过高时容量翻倍；overflow 过多但负载不高时等量扩容；两种扩容都保留 oldbuckets，并通过后续写操作渐进迁移。
七、删除：槽位清空不等于立刻缩容

delete(m, key) 找到目标槽位后，会清理 key/value，并更新 tophash 中的空槽状态。删除不存在的 key 仍然安全。

删除大量元素不代表主桶数组立刻缩小。旧版可能通过等量扩容整理过多的 overflow，但如果业务明确需要释放大块 map 内存，常见做法仍是新建 map，把保留数据复制过去，再丢弃旧 map。

八、经典 bucket 和当前 Group 怎样区分
对比Go 1.23 及之前Go 1.24+
顶层hmapMap + Directory
基本分组bmap bucket，8 槽Group，8 槽
初筛信息tophash[8]8 字节 control word，保存 H2
冲突处理overflow bucket开放寻址 + group 级二次探测
增长方式整组桶渐进迁移Table 独立 grow 或 split
不要把相似点当成同一个结构：两者都把数据按 8 个槽分组，也都用 hash 摘要初筛，但 Group 不是把 bmap 改了个名字。它们的内存组织、冲突路径和扩容方式都不同。

返回 Go 1.24+ Swiss Table 主线文章 →

九、经典实现常见面试追问
1. hmap 和 bmap 分别是什么？
hmap 管整张 map 的元数据和桶数组；bmap 表示一个最多容纳 8 组 key/value 的 bucket。
2. 为什么一个 bucket 是 8 个槽？
这是旧版 runtime 的固定布局选择。面试时记住 bmap 有 8 个 tophash、8 个 key 和 8 个 value 即可。
3. hash 的低位和高位分别做什么？
低 B 位选择主 bucket；高位摘要形成 tophash，在桶内先筛选候选槽位。
4. tophash 相同就命中吗？
不是。它只是摘要，最后必须比较完整 key。
5. 为什么有等量扩容？
元素可能经过反复增删后并不多，但留下很多稀疏 overflow。等量扩容不增加主桶数量，只重新紧凑排列数据。
6. 为什么渐进迁移？
把大 map 一次搬完会造成明显停顿。渐进迁移把工作分摊到后续写操作中。
十、经典实现 90 秒总结话术
如果讨论的是 Go 1.23 及之前：

map 顶层由 hmap 管理。
hmap 记录元素数量 count、桶指数 B、当前 buckets、
扩容期间的 oldbuckets 和迁移进度 nevacuate。

主桶数量是 2^B，每个 bmap bucket 有 8 个槽位，
布局是 tophash[8]、keys[8]、values[8]，末尾可连接 overflow bucket。

查询时先计算 hash：
低 B 位选择主 bucket，高位摘要形成 tophash；
tophash 匹配后仍要比较完整 key，主桶没找到再沿 overflow 查找。

扩容有两种：
负载过高时 B 加 1、容量翻倍；
overflow 过多时 B 不变，做等量扩容整理数据。
两种情况都保留 oldbuckets，并通过后续写操作渐进迁移。
顶层hmap
分组bmap 8 槽
冲突overflow
扩容渐进迁移
回答结束要补版本：“以上是 Go 1.23 及之前经典实现；Go 1.24+ 默认已经改用 Swiss Table。”
附录、官方源码依据

本文依据 Go 1.23.12 的历史 runtime 源码整理。runtime 是 Go 程序运行时负责底层管理的部分；源码中的 same-size grow 对应等量扩容，growWork/evacuate 对应分批执行和迁移旧桶。

Interview Lab · Go 经典 Map · hmap / bmap / bucket