go的map

map的结构

拉链法的hashMap

• 共有2^B 个桶
• 每个桶只能存放 8个 K*V，若多余8个，则放到溢出桶里面去

hash算法、B、oldBuckets

map的访问

read

write

使用拉链法实现 hashmap

每个桶中存储键hash 的前8位

桶超出 8个数据后，就会存储在溢出桶这个i部分

map的扩容

当 hash碰撞严重时，扩容桶会指向下一个扩容桶，此时变成了长链表，效率会变低；可以使用map的扩容来减缓压力。

发生扩容的场景

• 装载因子超过了6.5（平均每个槽6.5个key）
• 使用了太多的溢出桶（溢出桶的数量超过了普通的桶）

扩容的类型

• 等量扩容
  • 普通桶的数量不变，减少溢出桶的数量
• 翻倍扩容
  • 增加普通桶的数量

步骤

• 创建新的newBuckets
• oldBuckets指向之前的buckets
• 采用渐进式驱逐，每次操作一个旧桶时，将旧桶驱逐到新桶
• 读取时不进行驱逐，只判断读取新桶还是旧桶
• 旧桶数据驱逐完成后，回收oldBuckets

map的并发问题

map并发读写会 panic

A协程在桶中读数据时，B协程驱逐了这个桶；此时A协程会读取到错误的数据或者找不到数据

• 使用 mutex
• 使用 sync.Map

sync.Map

• 普通的map在扩容时不会有并发问题
• sync.Map 使用了 两个 map，分离扩容问题
• 不会引发扩容的操作（查、改）使用read map
• 可能引发扩容的操作（新增）使用dirty map

var m sync.Map

m.Store("k1", "v1")
m.Store("k1", "v2")
m.Store("k2", "v2")

/*	deleted := m.CompareAndDelete("k1", "v2")
	if deleted {
		fmt.Println("k1 is deleted")
	}*/
v, ok := m.Load("k2")
if ok {
	fmt.Println("k2->:", v)
}
m.Range(func(key, value any) bool {
	if key == "k2" {
		return false
	}
	fmt.Println(key, value)
	return true
})