Golang底层实现系列——map的底层实现
本文基于golang 1.14.13
map的底层数据结构
map的底层实现是一个散列表，map的实现过程实际上就是实现散列表的过程。map次要蕴含两个构造：hmap和bmap。
hmap构造：
bmap构造：
map的创立
map的创立通过生成汇编码能够晓得，调用的时runtime.makemap创立的。
ps:如果你的map初始容量小于等于8会发现走的是runtime.fastrand是因为容量小于8时不须要生成多个桶，一个桶的容量就能够满足（单桶容量通过bucketCnt常量定义）。
这里次要阐明overLoadFactor这个计算B的函数。
func 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
当overLoadFactor返回true时则代表须要扩容,B++。初始时在晓得容量的状况下会间断减少B直到overLoadFactore返回false。
在申请桶空间时用到的函数是makeBucketArry，这个函数会返回指向多个桶空间数组的第一个元素的指针（buckets）和第一个移除桶的指针（nextOverflow）。
<center>桶及溢出桶的散布</center>
如上图（桶及溢出桶的分布图），makeBucketArry实际上就是从内存中申请了一个间断的空间内存，内存大小为bucket.size * buckets总数（根底桶和溢出桶），其中前局部是根底桶（baseBucket）而后是溢出桶。
map的赋值
map的赋值会附带着map的扩容和迁徙，这两局部是map底层实现的要害，会在前面来独自说，除去这两局部的话，map赋值绝对简略，次要是一个hash分为两局部（低位bash和高位hash）低位用于查找bucket，而后tophash疾速判断bucket中各个地位是为空。找到key对应的地位，而后设置key及elem（如果key曾经存在则会间接返回elem的地位，汇编底层会将值赋值到elem对应地位）。
有一点须要特地留神，bmap中的key/value是如下图这样散布的：
其中dataOffset为bmap构造的大小。
漏了一个问题：当查找到所有桶发现没有可插入地位时，阐明所有的桶都满了，须要申请一个溢出桶（可能是事后申请好的，也可能须要从新申请），并且将溢出桶接到以后bucket的前面（如果已有溢出桶则为最初一个溢出桶的前面）
map的删除
map的删除调用的时mapdelete函数。
删除的逻辑绝对比较简单，大多函数在赋值操作中曾经用到过，所以这里只列除了一些特有的代码（删除数据）。
map的查问
map的查问调用的是mapaccess函数。
查问这里次要有一个在扩容过程中查问时须要确认以后key是否曾经迁徙到新的bucket中。次要是通过bmap.tophash来确认。
map的扩容
map的扩容有量中状况：
第一种：容量有余，“以后容量+1”之后计算出来扩容因子超出了规定值，即overLoadFactr函数返回true；
第二种：溢出桶过多。溢出桶数量 ≥ （B&15）。
注：这里的扩容因子的规定值是一个定值，是通过教训得出的论断，咱们不做探讨。
当是第一种扩容时，会将map容量扩充一倍。如果是第二种状况则代表可能是空的kv占用的空间过多，这次的扩容不会拓展空间，buckets的数量和原来是一样的然而会对map中的kv进行整顿，去除空的kv。
map的扩容只是将底层数组扩充了一倍，并没有进行数据的转移，数据的转移是在扩容后逐渐进行的，在迁徙的过程中每进行一次赋值（access或者delete）会至多做一次迁徙工作。
map的迁徙
在map的赋值与删除中咱们都有说道迁徙，这是扩容后的一部分，迁徙的根底构造是evacDst数据结构如下：
整个迁徙的流程如下：
注： 这里只是简略的举例子，理论中hash值不能够小于5，因为小于5的hash都被用于tophash的标识。
总结
- map的赋值难点在于数据的扩容和数据的迁徙操作
- bucket迁徙是逐渐进行的，在迁徙的过程中每进行一次赋值，会做至多一次迁徙工作。
- 扩容不肯定会减少空间，也可能只是做了内存整理
- tophash的标记即能够判断是否为空也能够半段是否搬迁，以及搬迁的地位。
- 从map中删除key，有可能导致呈现很多空的kv，这会导致迁徙操作，如果能够防止，尽量避免。
参考文章
深刻了解 Go map：赋值和扩容迁徙
Golang map底层实现原理解析
Golang Map 实现
golang map的底层实现
Go语言map底层实现