Go Map

Go Map 1.22-

参考资料

Go 1.22 及之前 map 主要由两部分实现 hashmap+bitmap

hmap 与 bmap 结构

hmap 结构

type hmap struct{
	count int //当前元素个数
	B     uint8 // 桶数 = 2^B
	hash0 uint32//哈希种子
	buckets unsafe.Pointer //指向桶数组
	oldbuckets unsafe.Pointer //扩容时指向旧桶
}

hmap 存什么

map 的元数据（count/B/hash0）和桶数组的指针（buckets/oldbuckets）

实例

m := make(map[string]int,10)
m["a"] = 1
m["b"] = 2
m["c"] = 3

此时
hmap:{
  		 count = 3 , 
       B = 2,
       hash0 = 0xXXXXXXXX,
       buckets = [bmap0][bmap1][bmap2][bmap3]
  		 oldbuckets = nil
      }

bmap 存什么

一个 bmap 就是一个桶，最多存储 8 个 kv 对；桶满后会通过溢出桶指针挂载新的溢出桶。

bmap 结构

// 旧版（1.22及之前）bmap 真实结构（运行时内部，含隐藏字段）
type bmap struct {
    tophash [8]uint8        // 哈希高8位，用于快速匹配key
    keys    [8]keytype      // 8个键的存储数组
    values  [8]valtype      // 8个值的存储数组
    overflow *bmap          // 隐藏字段：指向溢出桶的指针，桶满时链接新桶
}

实例

m := make(map[string]int,10)
m["a"] = 1
m["b"] = 2
m["c"] = 3
//假设上述三个kv都存在于bucket0

索引 0	索引 1	索引 2	索引 3	索引 4	索引 5	索引 6	索引 7
tophash	0x5a	0x3b	0x7b	0	0	0	0
keys	“a”	“b”	“c”	””	””	””	””
values	1	2	3	0	0	0	0

核心对应关系（同一列 = 同一索引）：

索引 0：tophash [0]=0x5a ←→ keys [0]=”a” ←→ values [0]=1

索引 1：tophash [1]=0x3b ←→ keys [1]=”b” ←→ values [1]=2

索引 2：tophash [2]=0x7b ←→ keys [2]=”c” ←→ values [2]=3

索引 3-7：全为空闲槽位，填充对应类型零值（空字符串 / 0）

map 存储过程

m["k"] = v

1. hash := hashFunc (“k”, hash0) // 结合哈希种子计算 key 的哈希值
2. bucket_index := hash % (2^B - 1) // 哈希值取模，定位目标桶
3. b := buckets [bucket_index] // 获取目标桶
4. 在 b 中遍历 tophash，找第一个值为 0 的空 slot（空闲槽位）
5. 写入数据：b.tophash [i] = hash 高 8 位；b.keys [i] = “k” ; b.values [i] = v
6. hmap.count ++ // 全局元素数 + 1

补充：若当前桶无空 slot，会创建溢出桶并通过 overflow 指针链接，数据写入溢出桶

map 查找数据

V,ok = map["k"]

1. hash = hashFunc (“k”, hash0) // 计算 key 的哈希值
2. bucket_index = hash % (2^B - 1) // 定位目标桶
3. b = buckets [bucket_index] // 获取目标桶（含溢出桶链）
4. tophash_target = hash » 8 // 提取哈希值高 8 位作为匹配依据
5. 遍历 b 的 tophash 数组：
   • 遍历到 tophash [i]==0，说明后续无数据，直接退出；
   • 若 tophash [i] == tophash_target 且 keys [i] == “k”，返回 values [i] 和 true；
   • 若当前桶遍历完未找到，继续遍历溢出桶链，直到找到或遍历完所有溢出桶。

map 扩容

扩容时机

装载因子：map 全局负载阈值，默认 6.5。

计算方式：总元素数 (count) / (总桶数 × 8)（总桶数 = 2^B，每个桶 8 个槽）。

触发条件：全局装载因子 ≥ 6.5 时触发扩容；1.23+ 新增「桶链过长阈值」（单桶链长度 > 16），也会触发扩容。

• 旧版（1.22 及之前）：单个桶 8 个槽写满后，不会触发全局扩容，仅为该桶挂载「溢出桶」形成桶链；
• 全局扩容仅在「装载因子≥6.5」时触发，目的是降低整体负载，避免桶链过长导致性能下降。

扩容原理

流程：

1. 分配新桶数组：容量为原桶数组的 2 倍（B 值 + 1）；
2. hmap 的 buckets 指向新桶数组，oldbuckets 指向旧桶数组；
3. 渐进式迁移：每次执行 put/delete 操作时，迁移 1~2 个旧桶的数据到新桶，避免一次性迁移导致 STW（Stop The World）；
4. 所有旧桶迁移完成后，释放 oldbuckets 指向的内存，oldbuckets 置为 nil。

一次性迁移的问题：

1. 元素过多时，单次迁移耗时久；
2. 阻塞当前 goroutine，产生明显延迟；
3. 高并发场景下，对大 map 极不友好。

渐进式迁移：

1. 扩容前 B=2，4 个桶

┌─────────────────────┐
│ hmap                │
│ count:26   B:2      │
│ oldbuckets: nil     │
│ nevacuate: 0        │
└─────────────────────┘
         ↓
┌─────────┬─────────┬─────────┬─────────┐
│ bucket0 │ bucket1 │ bucket2 │ bucket3 │
└─────────┴─────────┴─────────┴─────────┘

2. 扩容后 hashGrow B=3，8 个新桶

┌─────────────────────┐
│ hmap                │
│ count:26   B:3      │
│ buckets   → 新8桶   │
│ oldbuckets → 旧4桶  │
│ nevacuate: 0        │
└─────────────────────┘

新桶（8个）：
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │
└───┴───┴───┴───┴───┴───┴───┴───┘
↑ 新写入的数据直接存新桶

旧桶（4个）：
┌───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │
└───┴───┴───┴───┘
↑ nevacuate标记待迁移的旧桶序号

3. 迁移过程（旧桶 0 → 新桶 0/4）

第 1 次 put/delete 操作触发迁移：
→ 完整迁移 oldbuckets[0] 所有数据到新桶
→ 迁移完成后 nevacuate = 1（指向下一个待迁移桶）

旧桶0 数据分裂规则：
旧 B=2：哈希低2位=00 → 定位旧桶0
新 B=3：新增第3位（bit2）作为分裂依据
         ┌─ 第3位=0 → 哈希低3位=0xx → 新桶 0
旧桶0 ────┤
         └─ 第3位=1 → 哈希低3位=1xx → 新桶 4

总结

1. 扩容迁移的最小单位是整个 bucket（桶），而非单个 slot（槽位）；
2. nevacuate 递增规则：仅当一个旧桶的所有数据完整迁移到新桶后，nevacuate 才 + 1，始终指向 “下一个待迁移的旧桶序号”；
3. 扩容期间查询逻辑：先查新桶 → 若旧桶未迁移（nevacuate ≤ 旧桶序号），再查旧桶 → 确保能找到未迁移 / 已迁移的 key。

map 乱序遍历

迭代器初始化时的随机化

每次 range 遍历 map 时，Go 会创建迭代器（Iter），并生成两个随机偏移量：

• entryOffset：决定从桶内哪个槽位（slot）开始遍历；dirOffset：决定从哪个桶（bucket）开始遍历。

  两个偏移量每次遍历都重新生成，导致遍历起点不固定。

---

遍历时偏移量参与计算

• 小 map（仅 1 个桶）：

  k = (entryIdx + entryOffset) % 8
  

  起始槽位不再固定为 0，而是entryOffset对应的位置。

• 大 map（多个桶）：

  dirIdx = (dirIdx + dirOffset) & (dirLen-1) // 随机起始桶
  entryIdx = (entryIdx + entryOffset) & entryMask // 随机起始槽位
  

  起始桶和桶内起始槽位均为随机。

  注意：仅 for k,v := range map 遍历会随机化，直接通过 map[k] 访问无此逻辑。

---

直观例子

假设小 map 有 5 个 key（1-5），存在 slot 0~4：

• entryOffset = 0 → 遍历顺序：1, 2, 3, 4, 5
• entryOffset = 3 → 遍历顺序：4, 5, 1, 2, 3
• entryOffset = 5 → 遍历顺序：2, 3, 4, 5, 1（跳过空槽位后循环）

每次 range 生成不同的 entryOffset，遍历顺序自然混乱。

---

设计意图

Go 官方源码注释明确：

“Iteration order is unspecified. In the implementation, it is explicitly randomized.”

该设计为故意为之，目的：

• 避免开发者编写依赖 map 遍历顺序的代码（不同版本 / 环境下顺序可能变化）；
• 引导开发者通过 sort 显式排序，保证代码健壮性和可移植性。

Go Map 1.23+

背景

Go 1.23 对 map 底层做了存储结构和性能优化，核心设计思想（哈希表 + 桶、渐进式扩容、乱序遍历）完全兼容旧版；优化集中在「内存利用率」「高并发性能」「哈希冲突处理」，上层 API（make/map[]/range）无改动，开发者无感知。

核心差异

维度	Go 1.22 及之前（旧版）	Go 1.23+（新版）
bmap 存储结构	固定 8 槽位数组： tophash[8]+keys[8]+values[8]，空槽位占内存	切片：稀疏存储 + 类型特化： 1. 仅存储有数据的槽位，空槽位无内存开销 2. 不同类型 map 生成专属 bmap，砍掉无用字段
扩容触发逻辑	仅依赖「装载因子（6.5/8）」触发	双条件触发： 1. 装载因子（核心） 2. 桶链过长阈值（>16 个桶）
渐进式迁移	每次 put/delete 迁移 1-2 个桶	批量迁移：一次最多迁 4 个桶，减少锁竞争，高并发性能提升
内存利用率	低（空槽位占内存），小 map 内存浪费明显	高（稀疏存储），小 map 内存占用减少 20%-50%
乱序遍历	随机 entryOffset+dirOffset 打乱顺序	逻辑不变，优化随机数生成效率，遍历性能小幅提升

核心优化

1. bmap 结构：从「固定数组」到「稀疏存储（切片）」

旧版 bmap（固定 8 槽位，空槽位占内存）

┌─────────────────────────────────────────────────────────┐
│ tophash: [0x5a,0x3b,0x7b,0,0,0,0,0]                     │
│ keys:    ["a","b","c","","","","",""]                   │
│ values:  [1,2,3,0,0,0,0,0]                              │
└─────────────────────────────────────────────────────────┘
↑ 即使只存3个kv，仍占用8个槽位的完整内存

新版 bmap（稀疏存储，仅存有效槽位）

// 新版 bmap变成了切片 内存布局（连续一块内存，无空槽位开销）
┌─────────────────────────────────────────────────┐
│ 字段名       | 数据内容          | 内存占用       │
│--------------|-------------------|----------------|
│ sparseIndex  | [0,1,2]           | 3×4=12字节     │
│ tophash      | [0x5a,0x3b,0x7b]  | 3×1=3字节      │
│ keys         | ["a","b","c"]     | 3×字符串内存   │
│ values       | [1,2,3]           | 3×8=24字节     │
└─────────────────────────────────────────────────┘
↑ 所有字段连续排布，无链表指针，缓存命中率极高

• 核心变化：新增 sparseIndex 记录有效槽位索引，访问时快速定位，省内存且不丢性能；
• 类型特化：map[int]int 的 bmap 无字符串相关字段，map[string]interface{} 新增专属字段，内存更精准。

2. 扩容逻辑：新增「桶链过长阈值」

旧版仅靠装载因子扩容，哈希冲突严重时桶链过长（几十个桶），访问效率暴跌：

旧版桶链（哈希冲突严重）：
bucket0 → overflow_bucket0 → overflow_bucket1
├─ tophash[8] ├─ tophash[8] ├─ tophash[8]
├─ keys[8]    ├─ keys[8]    ├─ keys[8]
└─ values[8]  └─ values[8]  └─ values[8]
↑ 内存零散、缓存差，即使装载因子没到6.5，访问仍慢

新版新增「桶链过长阈值（16）」，链长超阈值时强制扩容，拆分长链：

新版扩容后拆分桶链：
bucket0 → bucket4 → ...（链长≤16）
bucket16 → bucket20 → ...（链长≤16）
↑ 保证每个桶链访问效率，避免性能暴跌

3. 渐进式迁移：批量迁移优化

旧版迁移（单次 1-2 个桶，速度慢）

第1次 put → 迁移 oldbucket[0] → nevacuate=1
第2次 put → 迁移 oldbucket[1] → nevacuate=2
↑ 大map扩容耗时久，锁竞争明显

新版迁移（单次最多 4 个桶，效率高）

第1次 put → 迁移 oldbucket[0,1,2,3] → nevacuate=4
第2次 put → 迁移 oldbucket[4,5,6,7] → nevacuate=8
↑ 批量迁移，扩容速度提升，高并发下锁竞争减少

新版 map 完整实例（对比旧版）

假设 m := map[string]int{"a":1,"b":2,"c":3}：

旧版（1.22）

hmap:{
   count = 3 , 
   B = 2,
   hash0 = 0xXXXXXXXX,
   buckets = [bmap0（8槽位）][bmap1][bmap2][bmap3]
   oldbuckets = nil
}
// bmap0：固定8槽位，空槽位占内存

新版（1.23+）

hmap:{
   count = 3 , 
   B = 2,
   hash0 = 0xXXXXXXXX,
   buckets = [bmap0（稀疏3槽位）][bmap1][bmap2][bmap3]
   oldbuckets = nil
   chainLen: [1,0,0,0] // 新增字段：记录每个桶链长度，用于触发扩容
}
// bmap0：稀疏存储，仅3个有效槽位，内存减少 ~60%

总结

1. Go 1.23+ 仅优化 map 底层存储和性能，核心逻辑（哈希定位、渐进式扩容、乱序遍历）不变；
2. 稀疏存储 + 类型特化降低内存占用，批量迁移 + 桶链阈值提升高并发性能；
3. 上层使用无感知，无需改代码，仍需注意「不能依赖 map 遍历顺序」。