Go Map

数据结构

hmap 是 Go 中 map 的底层数据结构，定义在 runtime/map.go 中：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


type hmap struct {
    count     int // 键值对的数量
    flags     uint8 // 标志位
    B         uint8 // bucket 数组的大小指数
    noverflow uint16 // 溢出桶的数量
    hash0     uint32 // hash seed, 为哈希函数的结果引入随机性
    
    buckets    unsafe.Pointer  // 指向 bucket 数组的指针
    oldbuckets unsafe.Pointer // 指向旧的 bucket 数组的指针
    nevacuate  uintptr // 旧的 bucket 数组中已经处理的元素数量
    
    extra *mapextra // 指向额外信息的指针
}

type mapextra struct {
    overflow    *[]*bmap // 指向溢出桶的指针
    oldoverflow *[]*bmap // 指向旧的溢出桶的指针
    nextOverflow *bmap // 指向下一个溢出桶的指针
}

其中维护了一个 bucket 数组。每个 bucket 可以放 8 个键值对。当一个 bucket 装满后，会创建溢出桶链接到当前的 bucket 中

扩容

map 会在以下两种情况发生时触发扩容：

装载因子超过 6.5时（装载因子既键值对数量 / bucket 数量）

在插入元素时，需要判断装载因子，当装载因子超过 6.5 的时候，就会触发扩容。此时会将桶的数量翻倍

使用了太多溢出桶

当我们持续向哈希表插入数据，并将他们全部删除时，如果哈希表中的数据没有超过阈值，就会不断累积溢出桶，造成缓慢的内存泄漏。

因此引入了等量扩容来复用已有的哈希扩容机制来解决该问题。

此时会创建与原来的桶数量相同的新桶，并逐步将原来的桶中的数据迁移到新的桶中，直到所有的桶都被迁移到新的桶中为止。之后老的 bucket 和溢出桶会由 GC 清理掉

面试题

使用 map 有哪些需要注意的问题？

并发安全问题。map 本身并不是并发安全的，如果多个 goroutine 同时读写一个 map，和容易触发 panic。
- 可以通过 sync.Mutex 或者 sync.RWMutex 来加锁，来保证并发安全
- 可以使用 sync.Map 来替代 map，sync.Map 是一个并发安全的 map 实现
map 的 key 必须是可比较的类型，例如 int、string、float、bool、指针、结构体等。不能使用 slice、map 和 function 作为 key
map 会自动扩容，但是不会缩容。map 的扩容是通过重新分配内存来实现的，因此在使用 map 时，应该尽量避免频繁的扩容操作
map 的遍历顺序是随机的，因此在遍历 map 时，不能依赖于遍历的顺序

Map 怎么知道自己处于竞争状态？

map 的并发读写检测是由 hmap 中的 flags 字段来实现的
- 在写入操作时设置 flags 的 0 位为 1，表示处于竞争状态
- 写入操作结束后，清除该位
- 若其他协程在写入操作未完成时尝试写入或者读取，会检测到该位为 1，触发 panic

并发使用 Map 除了加锁还有什么其他方案吗？

使用 sync.Map 替代
分片加锁。将 map 分为多个小 map，每个小 map 有自己的锁，以减少锁竞争。以 hash 取模来决定 key 落在哪个 map
使用 channel 将并行操作串行化。将所有对 map 的操作都放入一个 channel 中，由一个 goroutine 来处理这些操作

有对比过 sync.Map 和加锁的区别吗？

读多写少的场景 sync.Map 性能较好，因为读操作不加锁
写多读少的场景，sync.Map 性能一般，因为写操作时需要维护内部两个 map
sync.Map 维护了两个 map，内存开销会略大