总体来说golang的map是hashmap，是使用数组+链表的形式实现的，使用拉链法消除hash冲突。
map的内存模型
我的go源码版本是：go1.17.2
map的源码在Go_SDK\go1.17.2\src\runtime\map.go中。
首先我们来看一下map最重要的两个结构：
hmap:
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}
bmap:（bucket桶）
// A bucket for a Go map.
type bmap struct {
// tophash generally contains the top byte of the hash value
// for each key in this bucket. If tophash[0] < minTopHash,
// tophash[0] is a bucket evacuation state instead.
tophash [bucketCnt]uint8
// Followed by bucketCnt keys and then bucketCnt elems.
// NOTE: packing all the keys together and then all the elems together makes the
// code a bit more complicated than alternating key/elem/key/elem/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}
实际上在golang runtime时，编译器会动态为bmap创建一个新结构：
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}
Golang中map的底层实现是一个哈希表，因此实现map的过程实际上就是实现哈希表的过程。在这个哈希表中，主要出现的结构体有两个，一个叫hmap(a header for a go map)，一个叫bmap(a bucket for a Go map，通常叫其bucket)。这两种结构的样子分别如下所示：
hmap:
图中有很多字段，但是便于理解map的架构，你只需要关心的只有一个，就是标红的字段：buckets数组。Golang的map中用于存储的结构是bucket数组。
bucket:
标红的字段依然是“核心”，map中的key和value就存储在这里。“高位哈希值”数组记录的是当前bucket中key相关的“索引”，稍后会详细叙述。还有一个字段是一个指向扩容后的bucket的指针，使得bucket会形成一个链表结构。例如下图：
由此看出hmap和bucket的关系是这样的：
而bucket又是一个链表，所以整体的结构应该是这样的：
哈希表的特点是会有一个哈希函数，对传进来的key进行哈希运算，得到唯一的值，一般情况下都是一个数值。Golang的map中也有这么一个哈希函数，也会算出唯一的值，对于这个值的使用：
Golang把求得的值按照用途一分为二：高位和低位。
如图所示，蓝色为高位，红色为低位。 然后低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的哪个key。上文中提到：bucket中有个属性字段是“高位哈希值”数组，这里存的就是蓝色的高位值，用来声明当前bucket中有哪些“key”，便于搜索查找。 需要特别指出的一点是：我们map中的key/value值都是存到同一个数组中的。数组中的顺序是这样的:
并不是key0/value0/key1/value1的形式，这样做的好处是：在key和value的长度不同的时候，可以消除padding(内存对齐)带来的空间浪费。
现在，我们可以得到Go语言map的整个的结构图了：(hash结果的低位用于选择把KV放在bmap数组中的哪一个bucket中，高位用于key的快速预览，用于快速试错)
map的扩容
负载因子
判断扩充的条件，就是哈希表中的负载因子(即loadFactor)。
每个哈希表的都会有一个负载因子，数值超过负载因子就会为哈希表扩容。
Golang的map的加载因子的公式是：map长度 / 2^B(这是代表bmap数组的长度，B是取的低位的位数)阈值是6.5。其中B可以理解为已扩容的次数。
渐进式扩容
需要扩容时就要分配更多的桶（Bucket），它们就是新桶。需要把旧桶里储存的键值对都迁移到新桶里。如果哈希表存储的键值对较多，一次性迁移所有桶所花费的时间就比较显著。
所以通常会在哈希表扩容时，先分配足够多的新桶，然后用一个字段（oldbuckets）记录旧桶的位置。
再增加一个字段（nevacuate），记录旧桶迁移的进度。例如记录下一个要迁移的旧桶编号。
在哈希表每次进行读写操作时，如果检测到当前处于扩容阶段，就完成一部分键值对迁移任务，直到所有的旧桶迁移完成，旧桶不再使用，才算真正完成一次哈希表的扩容。
像这样把键值对迁移的时间分摊到多次哈希表操作中的方式，就是渐进式扩容，可以避免一次性扩容带来的性能瞬时抖动。
扩容规则
bmap结构体的最后一个字段是一个bmap型指针，指向一个溢出桶。溢出桶的内存布局与常规桶相同，是为了减少扩容次数而引入的。
当一个桶存满了，还有可用的溢出桶时，就会在后面链一个溢出桶，继续往这里面存。
实际上如果哈希表要分配的桶数目大于2 ^ 4，就认为要使用到溢出桶的几率较大，就会预分配2 ^ (B - 4)个溢出桶备用。
这些溢出桶与常规桶在内存中是连续的，只是前2 ^ B个用做常规桶，后面的用作溢出桶。
hmap结构体最后有一个extra字段，指向一个mapextra结构体。里面记录的都是溢出桶相关的信息。nextoverflow指向下一个空闲溢出桶。
overflow是一个slice，记录目前已经被使用的溢出桶的地址。noverflower记录使用的溢出桶数量。oldoverflower用于在扩容阶段储存旧桶用到的那些溢出桶的地址。
翻倍扩容
当负载因子 count / (2 ^ B) > 6.5 ,就会发生翻倍扩容（hmap.B++），分配新桶的数量是旧桶的两倍。
buckets指向新分配的两个桶，oldbuckets指向旧桶。nevacuate为0，表示接下来要迁移编号为0的旧桶。
每个旧桶的键值对都会分流到两个新桶中。
等量扩容
如果负载因子没有超标，但是使用的溢出桶较多，也会出发扩容，不过这一次是等量扩容。
那么用多少溢出桶算多了呢？
- 如果常规桶的数目不大于
2 ^ 15,那么使用溢出桶的数目超过常规桶就算是多了。 - 如果常规桶的数目大于
2 ^ 15，那么使用溢出桶的数目一旦超过2 ^ 15，就算是多了。
所谓等量扩容，就是创建和旧桶数目一样多的新桶。然后把原来的键值对迁移到新桶中，但是既然是等量，那来回迁移的又有什么用呢？
什么情况下，桶的负载因子没有超过上限值，却偏偏使用了很多溢出桶呢？自然是有很多键值对被删除的情况。同样数目的键值对，迁移到新桶中，能够排列的更加紧凑，从而减少溢出桶的使用。这就是等量扩容的意义所在。
参考博客：
https://www.cnblogs.com/maji233/p/11070853.html
https://www.bilibili.com/video/BV1Sp4y1U7dJ?spm_id_from=333.999.0.0