map 的底层结构是什么？扩容（rehash）是怎么进行的？

结论先行

map 是哈希表，运行时核心是 hmap：元素存放在 bmap 桶数组里，每个桶固定 8 个槽位并可通过 overflow 指针串成溢出链；当装载因子过高或溢出桶过多时触发扩容：桶数组翻倍或原地整理，并按旧桶逐个“疏散”（evacuate）元素。整个过程是渐进式的，不会一次性大卡顿。

要点

• 结构骨架：hmap 含元素计数 count、桶数对数 B（实际桶数 = 2^B）、buckets、oldbuckets、溢出桶、扩容状态等字段。
• 定位流程：对 key 取哈希，低 B 位决定落入哪个桶，再用高 8 位（tophash）与桶内 8 个槽快速比对，命中失败沿 overflow 链继续。
• 复杂度与约束：平均 O(1)，哈希退化时最坏 O(n)；key 必须支持 ==，slice、map、func 不能做 key。
• 扩容触发一：装载因子（元素数 / 桶数）超过 6.5 时“翻倍扩容”，桶数变为 2^(B+1)。
• 扩容触发二：桶数很大但溢出桶过多时做“等量扩容”（sameSizeGrow），桶数不变，目标是打散冗长的溢出链、压缩稀疏桶。
• 渐进迁移：扩容后旧桶保留在 oldbuckets，每次插入/删除顺带迁移 1~2 个旧桶（growWork），读写按需去新旧两处查，避免一次性全量搬移。
• 遍历随机：迭代起点与桶顺序随机化，绝不要依赖遍历顺序；扩容中的遍历会同时兼顾新旧桶。
• 并发安全：map 不是并发安全的，并发读写会直接 fatal error，本组后续题目再展开锁与 sync.Map。
• delete 与 len：delete 对不存在的 key 是安全空操作且平均 O(1)；len(m) 返回当前元素数。

示例

m := make(map[string]int, 8) // 预分配可减少中途扩容
m["go"] = 1
v, ok := m["rust"] // ok=false，v 为零值
delete(m, "go")    // 删除不存在的 key 安全
for k, v := range m { // 顺序随机，勿做任何顺序假设
	_, _ = k, v
}

常见追问/记忆点

• 追问：为什么 map 元素不可取地址？答：扩容会让元素“搬家”，已取出的地址会失效，所以 m[k].Field 不能直接改。
• 追问：为什么遍历要随机化？答：防止开发者依赖顺序写出脆弱代码，也避免每次遍历撞上同一个热点桶。
• 追问：为什么 8 槽一桶？答：权衡比较次数、内存占用与缓存友好性，配合 tophash 把平均比较降到 1 次以内。
• 记忆：8 槽一桶、tophash 加速、6.5 阈值翻倍、渐进疏散、天生无序、非并发安全。