每日八股——Go(5)

map的扩容机制

先导1：什么是bucket？

很多人讲map的时候会说桶（bucket），但是对一些刚学完go的人来说，我只知道map用的是键值对，我以为它存的就是键值对{“打招呼”:“你好”}，我从来没听过桶这玩意，它是干啥的？
实际上，bucket是哈希表里装键值对的一小块固定容量的“格子”，是 Go map 底层组织数据的基本单元。 在 Go 的 map 里，底层不是“一个超级大数组”，而是有一个 bucket 数组，长度是 2^B，每个 bucket（桶）里可以存多个 （一般是8个）key/value 对，可以想象成：

先导2：如何确定属于哪个桶？

Go 语言选择Bucket的核心逻辑可以概括为一句话：利用哈希值的“低位”（Low-Order Bits）来进行定位。 当你执行 map[key] 时，Go 首先会根据 key 的类型调用对应的哈希函数，算出一个 64 位的整数 (Hash Value)。
我们先导1写了bucket数组有2^B个bucket，假设B=3，那就有8个bucket， 如果要在这 8个bucket里均匀分配数据，我们只需要看哈希值的最后 3 位。
Go 使用位运算 & 来截取哈希值的最后 B 位，算出来的结果就是桶的索引。
BucketIndex=HashValue & (2B−1)BucketIndex = Hash Value \ \& \ (2^B - 1)BucketIndex=HashValue&(2B−1)
比如我们算出来的64位Hash Value为110…10110 110，掩码2^B - 1=7，进行运算后得到低3位110，则这个Key被放入6号桶。

先导3：如何查找到桶里的哪个位置？

我们确定桶号用了低B位，那确定桶内位置呢？答案就是先看有没有同 key 的槽（更新），没有就找第一个空槽（插入），找不到空槽就新建 overflow bucket。那问题就来了：如何看有没有同key？
这里就涉及到了Tophash，实际上，每个 bucket（bmap）里有：

• tophash[8]：每个槽位保存 key 的 hash 的“高 8 位”（做快速过滤）
• keys[8]：8 个 key
• values[8]：8 个 value
  查找 / 插入时，在这个 bucket 及其 overflow 链里做线性遍历，算出tophash （并做一些编码处理，保证不为 0） ，与每个槽位的tophash进行对比，如果有相同的，就说明找到了/更新value[i]，如果没有，就找第一个空槽进行插入，找不到空槽就新建overflow bucket。

正题

以上先导并不要求会背，只是我们需要知道原理，要不然背起这个八股会云里雾里。

Go 的 map 扩容不是“一次性把所有元素搬家”，而是：当装得太满或溢出桶太多时，申请新桶数组 → 标记为增长中 → 之后每次对 map 的操作顺带搬一小部分旧桶数据，渐进迁移，直到扩容完成。
扩容分为等量扩容与翻倍扩容：

1、 负载因子过大（装太满）

• 大致规则：count / 2^B 超过一个阈值（约 6.5）。
• 触发 “翻倍扩容”：桶数从 2^B 增加到 2^(B+1)。

2、 overflow bucket 太多

• 即使负载因子没超，但很多 bucket 被溢出桶挂了一长串。

• 触发 “等量扩容”：桶数不变（仍然 2^B），只是重新整理，尽量消灭
  overflow，提升局部性和查询性能。（因为go的删除操作时懒惰的，它只是标记了empty，并不会真的删除，这就导致出现了很多碎片，其他key无法使用，而等量扩容为了在迁移的时候清除这些碎片）。

  Go map 扩容采用“渐进式迁移”机制：当触发扩容时不会一次性搬全部数据，而是先分配一个新的 buckets 数组（容量翻倍或等量），把旧的 buckets 挂到 oldbuckets，并将 B 更新为新值，使 map 逻辑上已扩容。随后 map 进入“增长中”状态；从这一刻起，每次对 map 的访问（Load/Store/Delete）都会顺带迁移一个尚未搬迁的 old bucket（含其 overflow 链），将其中的元素按新的哈希空间重新分配到新 buckets。每搬完一个 bucket，就标记为 evacuated，并推进迁移指针。等所有 old bucket 都迁移完成后，oldbuckets 被清空，map 回到正常运行状态。这种增量搬迁将扩容成本分摊到后续多次操作中，避免一次性 O(n) 搬整个 map 带来的卡顿。

面试官如果追问：“在搬迁过程中，我读 map 会发生什么？”

• 读 (Get/Range)：
  • 先根据 hash 值找到对应的 bucket。
  • 如果 map 正在扩容，会先检查该 bucket 是否还在 oldbuckets 中（即还没搬走）。
  • 如果还在老桶里，就去老桶读；如果已经搬走了，就去新桶读。
  • 扩容期间的遍历（Range）是无序的，可能一会儿从老桶拿，一会儿从新桶拿。（因为有的桶迁移了，有的没有迁移）
• 写 (Put/Delete)：
  • 写操作会触发搬迁动作。
  • 新写入的数据只会直接写入新桶 (buckets)，不会写回老桶。

map 哪些不能作为键？

map 的 key 有严格限制：必须是可比较的类型（comparable） ，即 支持 == 比较 。

• 基础类型 (int, string, bool) 可以作为键。
• 指针 (*int, *Struct) 可以作为键，比较的是内存地址。
• Channel可以作为键，比较的是指针地址（是不是同一个通道）。
• Array可以作为键，仅当数组元素也是可比较时。
• Struct 可以作为键，仅当所有字段都是可比较时。
• Interface 可以作为键，仅当动态值必须可比较，否则
  Panic。比如map[interface{}]int，当interface{}为包含不可比较的类型时，会panic。
• 自定义类型可以作为键，仅当自定义类型是基于可比较的底层类型。
• Slice、Map、Function不能作为键，本质原因是它们的“内容相等”既昂贵又模糊：
  • slice/map 的内容比较需要 O(n) 遍历，而且底层结构复杂、容易隐藏性能坑；
  • function 的相等语义在闭包和不同实现下根本不好定义。

因此 Go 干脆在语言层面禁止这三类类型的相等比较，只保留与 nil 的可比性。