1、前言
本文主要讲述Golang Map的底层实现，概括起来主要有这几点：
- Map的本质是一个哈希表，哈希表内的数据被存储在一个由桶构成的数组中（an array of buckets）
- 每个桶最多存储8个键值对，桶的选择取决于键的哈希值的低阶位。比如一个Key哈希后的值是：
1417598731，选择哪个桶取决于哈希值后面的数字，也就是低阶位（具体取多少位下文会说明）
// 源码里面对桶存储的键值对数量的声明
const (
// Maximum number of key/elem pairs a bucket can hold.
bucketCntBits = 3
bucketCnt = 1 << bucketCntBits // 桶的元素数量，<< 相当于 1 * 2^3 = 8
） 桶底层源码的结构体包含
tophash、keys、values、overflow等字段，其中tophash数组存储的是键的哈希值的高8位，查找元素时，先根据哈希值匹配到tophash的索引，然后根据索引再获取对应key/value由于桶的选择取决于键的哈希值，虽然哈希算法会尽可能保证分配平均，但总会出现桶的元素溢出的情况（超过8个），这时候会新建一个溢出桶来存储(overflow字段)
当Map的元素不断增长，当达到一定条件时，会触发扩容，扩容有翻倍扩容和等量扩容，桶内的键值对会从老桶拷贝至新桶
Map遍历元素时，会按桶数组的顺序遍历，这也是为什么遍历时的元素顺序是无序的（和存入的顺序不一致）
2、Map的底层结构
源码：https://go.dev/src/runtime/map.go
Map的底层结构由两个struct组成，分别是 hmap（header map） 和 bmap（bucket map）
hmap：
// A header for a Go map.
type hmap struct {
count int // 哈希表的键值对个数(总数)
flags uint8 // 用于处理并发时，表示是否正在写入
B uint8 // 该值决定桶（bucket）创建的数量
noverflow uint16 // 溢出桶的大致数目
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) （接下来要迁移的桶的编号）（搬迁进度，小于nevacuate的已经搬迁）
extra *mapextra // optional fields
}
// mapextra holds fields that are not present on all maps.
type mapextra struct {
overflow *[]*bmap
oldoverflow *[]*bmap
// nextOverflow holds a pointer to a free overflow bucket.
nextOverflow *bmap
}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.
// 长度为8的数组（不是切片），用来存储哈希后的值的高8位，通过高8位查找同一个桶的不同元素
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.
} hmap 和 bmap之间的关系可以用下图说明：
注：hmap这个结构体并不会存储实际的数据，实际存储数据的是bmap结构体
3、Map的初始化
众所周知，我们通常使用 make 或者 new 方法来初始化Map，且make方法还可以声明Map的初始容量，如下：
m := make(map[string]string, 10)而make方法在源码中对应的方法为 makemap，具体如下：
// t 是map的类型，hint 是map的初始容量
func makemap(t *maptype, hint int, h *hmap) *hmap {
...
// 1、初始化 hmap 结构体
if h == nil {
h = new(hmap)
}
// 2、初始化哈希种子
h.hash0 = fastrand()
// 3、计算出桶的数量
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
// 4、根据B的值生成对应的桶数组（bucketArray）
if h.B != 0 {
var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}初始化Map的整体流程分为四步，在上面已经作了说明，需要特殊说明的是 hmap 结构体中B字段的计算方式：
const (
bucketCntBits = 3
bucketCnt = 1 << bucketCntBits
loadFactorNum = 13
loadFactorDen = 2
)
// 1、for循环不断累加
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
// 2、overLoadFactor 函数会先判断初始容量是否大于桶的最大容量（bucketCnt，常量，值为8），
// 最终再判断初始容量是否大于 loadFactorNum*(bucketShift(B)/loadFactorDen，
// 其中 loadFactorNum 和 loadFactorDen 都是常量，bucketShift(B) 等同于 2^B
func overLoadFactor(count int, B uint8) bool {
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
// 3、bucketShift returns 1<<b （即返回 2^b）
func bucketShift(b uint8) uintptr {
// Masking the shift amount allows overflow checks to be elided.
return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}可以得到，初始容量与B的对应关系为：
hint B
0-8 0
9-13 1
14-16 2
...4、Map的数据写入
m["name"] = "fuxiang"Map的数据写入需要解决两个问题，一是找到要存储的那个桶，二是这个key/value 在桶里如何存储。
第一个问题，桶的选择取决于key哈希后的值的低阶位，具体取多少个低阶位取决于hmap中B的值。
写入对应的源码是：
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
// 1、将key进行hash，貌似用的是murmur3算法
hash := t.hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// 2、计算tophash，即高阶位
top := tophash(hash)
bucketloop:
...
return unsafe.Pointer(&zeroVal[0])
}第二个问题，虽然在源码中，我们看到的bmap结构体只有一个tophash字段，但实际不止这一个，有些字段是动态加入的：
type bmap struct {
// tophash 是一个数组，用来存储哈希值的最高 8 位，可以加快哈希冲突的判断。
// tophash[i] 存储的是第 i 个键值对的哈希值的最高 8 位。
// 如果 tophash[i] == 0，则表示第 i 个键值对为空。
tophash [bucketCnt]uint8
// keys 和 values 数组用来存储键值对，它们的长度都是 bucketCnt。
// keys[i] 存储的是第 i 个键值对的键，values[i] 存储的是第 i 个键值对的值。
keys [bucketCnt]keytype
values [bucketCnt]valuetype
// overflow 是一个指针，指向下一个存储桶，用来处理 bmap 溢出的情况。
// 如果当前 bmap 中的 bucket 数组已经被占满了，Golang 会创建一个新的 bmap，并将 overflow 指向这个新的 bmap。
overflow *bmap
}5、Map的数据读取
if data, ok := range m["name"] {
}根据第四点Map的数据写入，当我们进入读取时，具体步骤为：
根据key的哈希值的低阶位找到对应的桶
根据哈希值的高8位在
tophash找到索引，再根据索引从keys、values中找到对应的值
6、Map的扩容
由于Map的数据是可以不断添加的，而且我们一般无法预知最终的数据大小，所以随着数据的添加，最终达到某个阈值后，就会引发Map的扩容。
Map的扩容有两种形式，一种是翻倍扩容，即申请比现在多一倍的桶，并将老数据迁移到新的桶；一种是等量扩容，即申请与现在同等数量的桶，并将老数据迁移到新的桶。
map扩容有两种情况，一种是map的负载因子超过了6.5，一种是溢出桶太多了
翻倍扩容触发条件：
- map中数据总个数 / 桶个数 > 6.5，引发翻倍扩容
等量扩容触发条件：
B <= 15，已使用的溢出桶个数 >= 2^B 时，引发等量扩容
B > 15，已使用的溢出桶个数 >= 2^15，引发等量扩容
需要注意的是，扩容只是初始化新的桶，并没有进行数据迁移。
7、Map的迁移
由于扩容有翻倍扩容和等量扩容，不同类型的扩容数据迁移也不一样。需要注意的是，两种类型的扩容都会新建新的桶，这时因为桶的哈希值可能会发生变化，如果直接在原来的哈希表中进行元素的重新分配，会非常麻烦，因为需要对哈希表中的所有元素进行操作，而且容易出现数据丢失等问题。而新建一个新的哈希表，可以将元素重新分配到新的哈希表中，同时避免对原来的哈希表造成影响。
7.1 翻倍扩容的迁移
翻倍扩容时，桶的数量会翻倍，比如原先是4个桶，这时候会重新建8个新桶，hmap中的buckets字段会指向新桶。
当数据未迁移，又有新数据写入，新数据会写入到新的桶（有标识）
翻倍扩容时，hmap的B字段会加1，因为桶的数量变了，而B字段控制的又是桶的数量，桶的数量翻倍，正好对应B+1。
翻倍扩容时，数据迁移并不是随机的，而是分流的。比如我一开始在1桶，翻倍后，1桶的键值对只会分配到1桶或者5桶，具体的比例要看哈希值，因为桶的选择是根据哈希值的低阶位，低阶位又跟hmap的B字段有关，而B字段又加1了。
7.2 等量扩容的迁移
- 等量扩容，桶的数量没变，所以键值对归属的桶不变，它的意义在于可以使数据更紧凑，比如一个桶可以存8个元素，6个被删了（标记删除），然后还有3个在溢出桶，此时等量扩容后，就可以把在溢出桶的挪到被删的位置，减少桶的数量，也能大大降低查找时间。
