基本数据结构
// A header for a Go map.
type hmap struct {
// 元素个数，调用 len(map) 时，直接返回此值
count int
flags uint8
// buckets 的对数 log_2
B uint8
// overflow 的 bucket 近似数
noverflow uint16
// 计算 key 的哈希的时候会传入哈希函数
hash0 uint32
// 指向 buckets 数组，大小为 2^B
// 如果元素个数为0，就为 nil
buckets unsafe.Pointer
// 等量扩容的时候，buckets 长度和 oldbuckets 相等
// 双倍扩容的时候，buckets 长度会是 oldbuckets 的两倍
oldbuckets unsafe.Pointer
// 指示扩容进度，小于此地址的 buckets 迁移完成
nevacuate uintptr
extra *mapextra // optional fields
}
简单图示
bucket数据结构
由runtime/map.go:bmap定义
type bmap struct {
tophash [8]uint8 //存储哈希值的高8位
data byte[1] //key value数据:key/key/key/.../value/value/value...
overflow *bmap //溢出bucket的地址
}
注意点:
- 每个bucket存储8个键值对
- tophash是长度为8的数组，存储hash值的高8位(桶中所有元素hash地位都是相同的)
- data区存放的是key-value数据，采用存放顺序是key/key/key/…value/value/value而不是key/value/key/value…，是为了节省字节对齐带来的空间浪费。
- overflow指针主要用来解决hash冲突，如果冲突多的话，会由此形成链表结构
图示:
负载因子
负载因子用于表示map冲突的情况,计算公式为
负载因子 = 键数量/bucket数量
- 对负载因子，越小，空间利用率越低；越大，冲突越严重，存取效率越低
- 一般go对触发扩容的负载因子阈值是6.5
扩容机制
- 负载因子 > 6.5时，也即平均每个bucket存储的键值对达到6.5个。
- overflow数量 > 2^15时，也即overflow数量超过32768时。
2种扩容方式
- 增量扩容:负载因子较大时，考虑新建一组bmap，长度是之前bucket的2倍，但有map比较大的情况，这个时候oldbuckets指针就有用了，即此时存在2个可访问的bucket,此时采取逐步搬迁策略，即每次访问map时都会触发一次搬迁，每次搬迁2个键值对。
- 等量扩容:主要针对一些极端场景，比如不断地增删，而键值对正好集中在一小部分的bucket，这样会造成overflow的bucket数量增多，但负载因子又不高，从而无法执行增量搬迁的情况。执行等量扩容时候，相当与把所有overflow指针的buckets搬到正常的buckets指针下，然后remap
map查找过程分析
查找过程:
- 根据key值算出哈希值
- 取哈希值低位与hmap.B取模确定bucket位置
- 取哈希值高位在tophash数组中查询
- 如果tophash[i]中存储值也哈希值相等，则去找到该bucket中的key值进行比较
- 当前bucket没有找到，则继续从下个overflow的bucket中查找。
注意点
- 如果当前处于搬迁过程，则优先从oldbuckets查找
- 查找不到，也不会返回空值，而是返回相应类型的0值。