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

假设 users 是“用户编号到用户名”的索引，业务只写 users[42]，希望立即找到编号 42 的用户。如果底层把所有用户排成普通列表，每次查询都可能从头比较到尾；用户越多，耗时越长。

users := map[int]string{
    7:  "Ada",
    42: "Lin",
}

userID := 42          // 本次要找的用户编号
name := users[userID] // 业务只关心拿到 "Lin"

hash（哈希）是把 key 计算成整数编号的过程。旧版 map 先用这个编号选择 bucket（桶）；一个桶像有 8 个格子的收纳盒，只负责一小部分候选 key。

有了这张需求图，再认识源码名词

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 是可以保存内存地址的通用指针类型。这里理解字段职责即可，不需要死背声明。

先别背“以 2 为底的对数”：把 B 当成翻倍次数

假设仓库最开始只有 1 个主桶。每翻倍一次，主桶数量就按 1 → 2 → 4 → 8 → 16 变化。B 记录的就是走到这一步用了多少次翻倍：B=0 对应 1 个主桶，B=3 对应 8 个主桶。

“以 2 为底的对数”只是把问题反过来问

对数在这里不是新的计算魔法，只是在问“2 的多少次方等于这个数量”。已知 B=3，正着算 2³=8；已知有 8 个主桶，反过来找指数，答案是 log₂(8)=3。log₂ 读作“以 2 为底的对数”，下标 2 表示我们一直拿 2 的幂来比较。

runtime 保存 B 很顺手，因为主桶数量总是 2 的整数次幂，而且选桶正好要取 hash 的低 B 位。源码会构造一个低 B 位全为 1 的掩码，再做位运算；你现在只需记住它的结果等价于 hash % 2^B，不需要先学会位运算。

hash0 是随机种子，可以理解成每张 map 各自的一份“调味料”，让同一个 key 在不同 map 中不必得到相同的 hash。

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

先回答根问题：hash("cat", hash0) 在真实机器里到底是什么？

经典 Go Map 查询并不是先得到一串神秘的“高位/低位符号”，而是先得到一个真正的整数。Go 1.23 的 runtime 查询源码可以概括成 hash := t.Hasher(key, uintptr(h.hash0))：key 和这张 map 的随机种子 hash0 交给对应 key 类型的哈希函数，返回值是一个 uintptr 整数。

uintptr 的宽度跟机器指针宽度一致。在常见的 amd64、arm64 服务器和 Apple Silicon Mac 上，它是 64 位；在 32 位机器上则是 32 位。所以下面不再用“简化成 16 位”的玩具模型，而是直接按常见 64 位机器来观察。

// 假设某次 64 位机器上的查询得到：
hash = 0xA73C91F052D86E05

// 十六进制按 8 个字节看：
A7 3C 91 F0 52 D8 6E 05

// 展开成 64 个二进制位：
10100111 00111100 10010001 11110000 01010010 11011000 01101110 00000101
^^^^^^^^                                                             ^^^
bit 63~56                                                           bit 2~0
高 8 位                                                              低 3 位

CPU 实际怎样“取”这两部分

在 64 位机器上，要取得最高 8 位，可以把 64 位整数整体右移 64-8=56 位：uint8(hash >> 56)。经典 runtime 的 tophash 函数本质就是这样做；如果取出的原始值小于 minTopHash=5，还会再加 5，用来避开 0～4 这些内部状态值。本例最高字节是 0xA7，本身大于 5，所以无需调整。

要取得最低 B 位，runtime 构造掩码 (1<<B)-1。当 B=3 时，掩码就是二进制 111；执行 hash & 0b111 后，只保留 bit 2～0。示例 hash 最后一个字节是 05 = 0000 0101，最后 3 位恰好是 101，也就是十进制 5。

现在用一个具体例子查 m["cat"]。假设 B=3，这张 map 的 buckets 是一排 2³=8 个主桶：buckets[0]、buckets[1]，一直到 buckets[7]。方括号里的数字叫数组下标，它是这排桶的位置编号，并且从 0 开始。

继续使用上面的 64 位教学 hash 0xA73C91F052D86E05。因为当前 B=3，runtime 只保留这个整数的最低 3 个 bit，也就是 bit 2～0。最后一个字节 05 展开为 0000 0101，最低 3 位就是 101。这三个位置从右向左分别代表 1、2、4，所以 101₂ = 1×4 + 0×2 + 1×1 = 5，最终选择 buckets[5]。这个 5 是数组下标；由于下标从 0 开始，它是一排 8 个主桶中的第 6 个位置。

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

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

独立的拥挤场景：假设整张 map 原有 8 个元素，它们都在 buckets[5]，"cat" 是第 9 个

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

先分清三个数量：元素、主桶、每桶槽位

例如扩容前 B=3，有 8 个主桶，每个桶仍是 8 槽；普通翻倍后 B=4，变成 16 个主桶，但每个桶仍是 8 槽。可以把它想成“8 格货箱的数量增加了”，不是“每只货箱从 8 格改造成 16 格”。

为什么有时增加主桶，有时主桶数量不变

负载因子表示“元素数量 ÷ 主桶数量”，也就是平均每个主桶对应多少个元素。它看的是全局平均，不代表每个桶恰好都装了同样多。旧版插入数据时会观察两个信号：元素相对主桶是否太多，以及 overflow bucket 是否太多。

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

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

源码把“搬一个旧桶”叫 evacuate（直译为“疏散”）。旧槽位的 tophash 会改成搬迁状态：evacuatedX（值 2）表示该数据走 X 路，evacuatedY（值 3）表示走 Y 路；普通有效摘要从 minTopHash=5 开始，因此不会和 0～4 的空槽、搬迁状态混淆。若算出的摘要小于 5，runtime 会先加 5 再保存。

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

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

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

如果讨论的是 Go 1.23 及之前：

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

主桶数量是 2^B：例如 B=3 时 2³=8，
反过来就是 log₂(8)=3；低 B 位也刚好能表示全部主桶编号。
每个 bmap bucket 始终只有 8 个槽位，扩容不会把单桶改成 16 槽，
布局是 tophash[8]、keys[8]、values[8]，末尾可连接 overflow bucket。

查询时 hasher 会返回一个 uintptr hash。
在常见 64 位机器上，它就是一个 64 位整数：
低 B 位通过 hash & ((1<<B)-1) 选择主 bucket；
最高 8 位通过右移取得并生成 tophash（原始值小于 5 时 runtime 会调整）；
tophash 匹配后仍要比较完整 key，主桶没找到再沿 overflow 查找。

扩容有两种：
负载过高时 B 加 1、容量翻倍；
overflow 过多时 B 不变，做等量扩容整理数据。
两种情况都保留 oldbuckets，并通过后续写操作渐进迁移。

本文依据 Go 1.23.12 的历史 runtime 源码整理；源码中的 same-size grow 对应等量扩容，growWork/evacuate 对应分批执行和迁移旧桶。

• Go 1.23.12 runtime/map.go
• 阈值依据：overLoadFactor 判断负载是否超标，tooManyOverflowBuckets 判断溢出桶是否过多，hashGrow 决定翻倍还是等量扩容。
• 迁移依据：evacuatedX、evacuatedY 和 minTopHash 保存槽位状态；evacuate 搬一个旧桶，advanceEvacuationMark 推进整张表的迁移进度。
• Go 1.24+ Swiss Table 主线文章