返回归档
🎗️Golang

Go map:hmap、bmap 和为什么不能并发写

Go 1.23 及以前的 map 是 hmap 加一组 bmap。每个 bucket 放 8 个 key,装载因子 6.5 指的是每个 bucket 平均 6.5 个元素。内置 map 没有锁;读多写少用 sync.Map,写多且 key 分散用分片锁。

文章目录

Go 的内置 map 是哈希表。1.24 起默认换成了 Swiss Table,下面按 1.20–1.23 的 hmap / bmap 讲——装载因子、渐进搬迁、「运行时不给你加锁」这三件事,换实现之后仍然成立。

不是 slot 里再塞 bucket

顶层结构是 hmap:元素个数、B(bucket 数组长度是 2^B)、buckets、扩容时的 oldbucketsbuckets 是一组 bmap。每个 bmap 固定 8 个槽:8 个 tophash(哈希的高 8 位)、8 个 key、8 个 value,满了再挂 overflow bucket。

所以:

  • 先按哈希的低 B 位落到某个 bucket
  • 再在这个 bucket 的 8 个槽里用 tophash 过滤
  • 不是「一个 slot 里有多个 bucket」

hmap 指向一组 bmap,每个 bmap 含 tophash / keys / elems

冲突用的是同一 bucket 内的开址 + overflow 链,不是另做一条独立的「拉链 hashmap」叙事。

什么时候扩容

触发条件有两个:

  1. 装载因子 > 6.5:平均每个 bucket 超过 6.5 个 key(8 个槽用到约八成),不是「每个 slot 6.5 个 bucket」
  2. overflow bucket 太多(大致超过普通 bucket 数):数据量没涨,只是散列得难看

对应两种搬迁:

  • 装载高了:翻倍B+1,新数组是旧的两倍
  • 只是 overflow 多了:等量扩容,还是 2^B 个 bucket,把元素摊开

搬迁是渐进的。hmap.oldbuckets 指着旧数组;写和删会顺手把碰到的旧 bucket evacuate 到新数组。纯读一般不搬,只判断去新桶还是旧桶。旧桶搬完再丢掉 oldbuckets

为什么不能并发读写

不是「读的时候可能读到搬迁前的桶」。运行时的选择更干脆:内置 map 没有锁,并发写、或一边写一边读,直接 fatalconcurrent map writes / concurrent map read and map write)。

原因是代价。给每个 map 加锁会惩罚所有只用在单 goroutine 里的代码;渐进搬迁再叠加无锁并发,正确性会非常贵。需要并发时,在外面自己选同步原语。

sync.Map 和分片锁

sync.Map 适合官方写明的两类场景:一个 key 基本只写一次、之后狂读(只增不改的缓存),或者 不同 goroutine 碰的 key 几乎不重叠。它不是「写多读少」的默认答案。两个 goroutine 同时 Store 同一批 key,演示不出它的长处。

写多、key 又散落在整个空间里,更常见的是 分片锁:按 key 的哈希选中其中一个子 map,每个子 map 一把 RWMutex。压力摊到 16 / 32 把锁上,而不是一把锁护住整张表。这和 MongoDB 把数据切到不同机器不是一回事——那是分布式分片,这里只是进程内降低锁竞争。

func (m ConcurrentMap[K, V]) GetShard(key K) *ConcurrentMapShared[K, V] {
	return m.shards[uint(m.sharding(key))%uint(SHARD_COUNT)]
}

选用顺序可以记成:单 goroutine 用内置 map;读多写少或 key 不打架用 sync.Map;写多且 key 分散再上分片锁。