Golang底层实现系列——map的底层实现
本文基于golang 1.14.13
map的底层数据结构
hmapbmaphmap结构：
bmap结构：
2021.08.17补充：这里tophash的写错了，类型应该是一个uint8的数组，数组的长度是8(一个桶的容量)，每个值保存的时
map的创建
runtime.makemap
runtime.fastrandbucketCnt
overLoadFactorBfunc overLoadFactor(count int, B uint8) bool {
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}参数含义：
count：当前map容量
B：当前B的值
bucketCnt：单个桶数量（默认为8）
loadFactorNum：13
bucketShift : 1<<B
loadFactorDen：2
overLoadFactortrueB++overLoadFactorefalsemakeBucketArry
<center>桶及溢出桶的分布</center>
makeBucketArrybucket.size * buckets总数（基础桶和溢出桶）map的赋值
map的赋值会附带着map的扩容和迁移，这两部分是map底层实现的关键，会在后面来单独说，除去这两部分的话，map赋值相对简单，主要是一个hash分为两部分（低位bash和高位hash）低位用于查找bucket，然后tophash快速判断bucket中各个位置是为空。找到key对应的位置，然后设置key及elem（如果key已经存在则会直接返回elem的位置，汇编底层会将值赋值到elem对应位置）。
有一点需要特别注意，bmap中的key/value是如下图这样分布的：
bmap漏了一个问题：当查找到所有桶发现没有可插入位置时，说明所有的桶都满了，需要申请一个溢出桶（可能是预先申请好的，也可能需要重新申请），并且将溢出桶接到当前bucket的后面（如果已有溢出桶则为最后一个溢出桶的后面）
2021.08.17补充：
在根据tophash向一个桶内插入数据时，是从头开始遍历桶的八个位置，找到桶中空的位置。
map的删除
mapdelete
删除的逻辑相对比较简单，大多函数在赋值操作中已经用到过，所以这里只列除了一些特有的代码（删除数据）。
map的查询
mapaccess
bmap.tophashmap的扩容
map的扩容有量中情况：
overLoadFactr第二种：溢出桶过多。溢出桶数量 ≥ （B&15）。
注：这里的扩容因子的规定值是一个定值，是通过经验得出的结论，我们不做讨论。
当是第一种扩容时，会将map容量扩大一倍。如果是第二种情况则代表可能是空的kv占用的空间过多，这次的扩容不会拓展空间，buckets的数量和原来是一样的但是会对map中的kv进行整理，去除空的kv。
map的扩容只是将底层数组扩大了一倍，并没有进行数据的转移，数据的转移是在扩容后逐步进行的，在迁移的过程中每进行一次赋值（access或者delete）会至少做一次迁移工作。
map的迁移
evacDst
整个迁移的流程如下：
注： 这里只是简单的举例子，实际中hash值不可以小于5，因为小于5的hash都被用于tophash的标识。
总结
- map的赋值难点在于数据的扩容和数据的迁移操作
- bucket迁移是逐步进行的，在迁移的过程中每进行一次赋值，会做至少一次迁移工作。
- 扩容不一定会增加空间，也可能只是做了内存整理
- tophash的标志即可以判断是否为空也可以判断是否搬迁（用户key的tophash最小值为5,5以下为标识，用于标识此tophash对应的值的搬迁进度及状态），以及搬迁的位置。
- 从map中删除key，有可能导致出现很多空的kv，这会导致迁移操作，如果可以避免，尽量避免。