go中的map实现思路
核心结构体
hmap的结构其实刚开始看起来其实还是比较复杂的，有不少的字段，具体字段如下图所示：
| 字段 | 解释 |
|---|---|
| count | 键值对的数量 |
| B | 2^B=len(buckets) |
| hash0 | hash因子 |
| buckets | 指向一个数组(连续内存空间)，数组的类型为[]bmap，bmap类型就是存键值对的结构 |
| oldbuckets | 扩容时，存放之前的buckets(Map扩容相关字段) |
| extra | 溢出桶结构，正常桶里面某个bmap存满了，会使用这里面的内存空间存放键值对 |
| noverflow | 溢出桶里bmap大致的数量 |
| nevacuate | 分流次数，成倍扩容分流操作计数的字段(Map扩容相关字段) |
| flags | 状态标识，比如正在被写、buckets和oldbuckets在被遍历、等量扩容(Map扩容相关字段) |
下面详细介绍一些字段
- buckets
buckets指向了一个数组(连续的内存空间)，数组的元素是bmap类型，这个字段我们称之为正常桶。
hmap的源码和地址如下：
// https://github.com/golang/go/blob/go1.13.8/src/runtime/map.go
type hmap struct {
count int
flags uint8
B uint8
noverflow uint16
hash0 uint32
buckets unsafe.Pointer
oldbuckets unsafe.Pointer
nevacuate uintptr
extra *mapextra
}
-
bmap
正常桶
hmap.buckets的元素是一个bmap结构。bmap的具体字段如下图所示：
字段释义如下：
| 字段 | 解释 |
|---|---|
| topbits | 长度为8的数组，[]uint8，元素为：key获取的hash的高8位，遍历时对比使用，提高性能。 |
| keys | 长度为8的数组，[]keytype，元素为：具体的key值。 |
| elems | 长度为8的数组，[]elemtype，元素为：键值对的key对应的值。 |
| overflow | 指向的hmap.extra.overflow溢出桶里的bmap，上面的字段topbits、keys、elems长度为8，最多存8组键值对，存满了就往指向的这个bmap里存 |
| pad | 对齐内存使用的，不是每个bmap都有会这个字段，需要满足一定条件 |
扩容规则
Go语言中Map的默认负载因子是6.5 当当前Map的负载大于该值时，就会发生翻倍扩容，分配的新桶的数目是旧桶的两倍。buckets会指向新分配的两个桶，oldbuckets会指向旧桶，会将nevacuate字段置为0，表示接下来要迁移编号为0的旧桶，每个旧桶中的键值对会分流到两个新桶中，例如如果旧桶的数量为4，新桶的数量就是8。 桶的数量一定是2的整数次幂
如果负载因子没有超标，但是使用的溢出桶较多，也会触发扩容，这种情况出现的是等量扩容。关于用多少溢出桶算多？ 如果常规桶的数目<= 2^15（也就是结构体中的那个B字段等于15） 并且如果使用溢出桶的数量超过常规桶就算是多了。如果 常规桶的数量>2^15 那么使用溢出桶数目一旦超过2^15就算多了。这时发生的等量扩容就会创建和旧桶一样多的新桶，然后把原来的kv对迁移到新桶中。 既然是等量大小，那迁移来迁移去有什么用呢？ 存在这这么一种场景，试想在什么情况下桶的负载因子没有超过上限，但却使用了很多溢出桶呢？
自然是有很多kv对被删除的情况，溢出桶内有很多空洞。在扩容后将kv对重新排列变得更加紧凑了，从而减少溢出桶的使用，这就是等量扩容的意义。
