go语言基础学习十

map的底层实现#

map结构#

type hmap struct {
	count     int         // map元素个数，len()取值
	B         uint8       // 桶数量=2^B
	noverflow uint16      // 溢出桶大致数量
	hash0     uint32      // 随机哈希种子
	buckets   []*bmap     // 桶数组
	oldbuckets []*bmap    // 扩容时旧桶
	nevacuate uintptr     // 扩容迁移进度
}

type bmap struct {
	tophash [8]uint8     // 8个key的哈希高8位
	data    [8]byte      // 连续内存：key1|val1|key2|val2...
	overflow *bmap       // 溢出桶链表
}
//单个桶最多存 8 组 k/v。
//超 8 个挂 overflow 溢出桶（单向链表）

寻址流程（key→桶）#

1,key 通过 hash(key)^hash0 得到哈希值 2,低 B 位：定位桶下标 hash & (1«B -1) → 找到 buckets[i] 3,高 8 位：tophash，在桶内快速对比，匹配则取对应位置 key、value 4,本桶找不到，顺着 overflow 遍历溢出桶

插入流程#

1. 找到目标桶，遍历 8 个槽位
   1. 如果槽位为空，直接插入
   2. 如果槽位不为空，根据 hash(key) 再次对比，匹配则更新 value，不匹配则插入到溢出桶
2. 桶满 8 个：新建 overflow 溢出桶，数据挂链表尾部
3. 负载因子 > 6.5 触发扩容（负载因子 = count / (1«B)）
   1. 新建容量翻倍的桶数组（B+1）
   2. 渐进式扩容：每次增删查迁移少量 oldbuckets 数据，避免 STW 卡顿

扩容两种模式#

1. 等量扩容,B不变,同下标新桶，全量 rehash 紧凑排布、甩掉冗余溢出桶
   1. 触发条件:负载≤6.5，但溢出桶太多
   2. 扩容后：所有元素重新 hash 到新桶，避免冲突
2. 翻倍扩容,1 个旧桶数据按 hash 新增 bit，拆分到新原下标、原下标 + 2ᴮ两个新桶
   1. 触发条件:负载因子＞6.5
   2. 寻址变化:原来定位旧桶只用：hash & (S-1)（低B位）,现在多最高新增 1bit（第B位）