1、 map的本质
golang中的map是一个指针。当执行语句 make(map[k]v, hint) 的时候，其实是调用了 makemap 函数，返回了一个指针
// makemap implements Go map creation for make(map[k]v, hint).
func makemap(t *maptype, hint int, h *hmap) *hmap
hmap是map的底层：是 hashmap 的“缩写”，但是hmap还不是主要存储key value的结构，hmap做的是一些map结构的基本设定。
2、结构
2.1 实现原理
- Go中的map是一个指针，占用8个字节，指向hmap结构体; 源码src/runtime/map.go中可以看到map的底层结构
- 每个map的底层结构是hmap，hmap包含若干个结构为bmap的bucket数组。每个bucket底层都采用链表结构
- 每个 bucket 中存储的是 Hash 值低 bit 位数值相同的元素，默认的元素个数为 BUCKETSIZE（值为 8，Go 1.17 版本中在 $GOROOT/src/cmd/compile/internal/reflectdata/reflect.go 中定义，与runtime/map.go 中常量 bucketCnt 保持一致）
- 当某个 bucket（比如 buckets[0]) 的 8 个空槽 slot）都填满了，且 map 尚未达到扩容的条件的情况下，运行时会建立 overflow bucket，并将这个 overflow bucket 挂在上面 bucket（如 buckets[0]）末尾的 overflow 指针上，这样两个 buckets 形成了一个链表结构，直到下一次 map 扩容之前，这个结构都会一直存在
- map 结构，key和value单独排列在一起可以减少结构体对齐填充，减少内存浪费
2.2 hmap
map本质是hash表（hmap），指向一堆桶（buckets）用来承接数据，每个桶（bmap）能存8组k/v。
当有数据读写时，会用key的hash找到对应的桶，hash值低8位用来定位桶，高8位用来定位桶内位置，bmap里记录了tophash数组（hash的高8位），方便桶内定位。
hash表就会有哈希冲突的问题（不同key的hash值一样，即hash后都指向同一个桶），为此map使用桶后链一个溢出桶（overflow）链表来解决当桶8个单元都满了，但还有数据需要存入此桶的问题。
// hmap的基础数据结构
type hmap struct {
count int // 元素的个数 == len()返回的值，必须放在第一个位置因为 len函数需要使用，所以map的len()时间复杂度是O(1)
flags uint8 // map的操作状态，如当前是否有别的线程正在写map、当前是否为相同大小的增长（扩容/缩容？）
B uint8 // hash桶buckets的数量为2^B个
noverflow uint16 // 溢出的桶的数量的近似值
hash0 uint32 // hash种子
buckets unsafe.Pointer // 指向2^B个桶组成的数组的指针，数据存在这里
oldbuckets unsafe.Pointer // 指向扩容前的旧buckets数组，只在map增长时有效
nevacuate uintptr // 计数器，标示扩容后搬迁的进度
extra *mapextra // 保存溢出桶的链表和未使用的溢出桶数组的首地址
}
2.3 bmap
bmap 就是我们常说的“桶”，桶里面会最多装 8 个 key，这些 key 之所以会落入同一个桶，是因为它们经过哈希计算后，哈希结果是“一类”的。在桶内，又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置（tophash数组记录了key的高8位，方便key用来查找bmap，以及bmap中定位keyvaule）。
type bmap struct {
tophash [bucketCnt]uint8
// len为8的数组
// 用来快速定位key是否在这个bmap中
// 桶的槽位数组，一个桶最多8个槽位，如果key所在的槽位在tophash中，则代表该key在这个桶中
}
但这只是表面(src/runtime/hashmap.go)的结构，编译期间会给它加料，动态地创建一个新的结构：
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}
注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/… 这样的形式。源码里说明这样的好处是在某些情况下可以省略掉 padding字段，节省内存空间。
2.4 tophash
tophash是一个长度为8的数组，记录了key的高8位，方便桶内定位。
- 向 map 插入一条数据，或者是从 map 按 key 查询数据的时候，运行时都会使用哈希函数对 key 做哈希运算，并获得一个哈希值（hashcode）
- 运行时会把 hashcode“一分为二”来看待，其中低位区的值用于选定 bucket，高位区的值用于在某个 bucket 中确定 key 的位置
- 每个 bucket 的 tophash 区域其实是用来快速定位 key 位置的，避免了逐个 key 进行比较这种代价较大的操作
每一个tophash唯一对应一个K/V对。
tophash是一个长度为8的数组，它不仅仅用来存放key的哈希高8位，在不同场景下它还可以标记迁移状态，bucket是否为空等。
- 当tophash对应的K/V被使用时，存的是key的哈希值的高8位；
- 当tophash对应的K/V未被使用时，存的是K/V对应位置的状态。
3. go map的扩容缩容
3.1扩容过程
主要是由于哈希碰撞问题
什么情况下会map扩容呢：
- 溢出桶太多时会导致严重的性能下降
- runtime.mapassign()可能会触发扩容的情况
- 装载因子超过6.5个（平均每个槽6.5个key）
- 使用太多溢出桶（溢出桶超过了普通桶）
map的两种扩容类型:
- 等量扩容（整理）：数据不多但是溢出桶太多了，使数据更紧凑
- 翻倍扩容：数据太多了增加普通桶的数量
map的扩容过程：
步骤一
- 创建一组新桶
- oldbuckets指向原有的桶数组
- buckets指向新的桶数组
- 把map标记为扩容状态
步骤二
- 将所有的数据从旧桶驱逐到新桶
- 采用渐进式驱逐（好多技术都有这种思想，比如redis的rehash）
- 每次操作一个旧桶的时，将旧数据驱逐到新桶
- 读取时不进行驱逐，只判断读取新桶还是旧桶
步骤三
- 所有的旧桶驱逐完成后
- oldbuckets回收
总结：
- 装载系数或者溢出桶的增加，会触发map扩容
- “扩容”可能并不是增加桶的数量，而是整理数据，使数据更加紧凑
- map扩容采用渐进式，桶被操作时才会重新分配
3.2 扩容缩容的基本原理
go map的扩容缩容都是grow相关的函数，这里扩容是真的，缩容是伪缩容，后面我会解释。我们先看下触发条件：
触发 map 扩容的时机：在向 map 插入新 key 的时候，会进行条件检测，符合下面这 2 个条件，就会触发扩容：
- 装载因子超过阈值，源码里定义的阈值是 6.5。
- overflow 的 bucket 数量过多：当 B 小于 15，也就是 bucket 总数 2^B 小于 2^15 时，如果 overflow 的 bucket 数量超过 2^B；当 B >= 15，也就是 bucket 总数 2^B 大于等于 2^15，如果 overflow 的 bucket 数量超过 2^15。
map只在插入元素即mapassign()函数中对是否扩容缩容进行触发，条件即是上面这段代码：
- 条件1：当前不处在growing状态
- 条件2-1：触发扩容：map的数据量count大于hash桶数量(2B)*6.5。注意这里的(2B)只是hash数组大小，不包括溢出的桶
- 条件2-2：触发缩容：溢出的桶数量noverflow>=32768(1«15)或者>=hash数组大小。
仔细观察触发的代码，扩容和缩容是同一个函数，这是怎么做到的呢？在hashGrow()开始，会先判断是否满足扩容条件，如果满足就表明这次是扩容，不满足就一定是缩容条件触发了。扩容和缩容剩下的逻辑，主要区别就在于容量变化，就是hmap.B参数，扩容时B+1则hash表容量扩大1倍，缩容时hash表容量不变。
- h.oldbuckets：指向旧的hash数组，即当前的h.buckets
- h.buckets：指向新创建的hash数组
到这里触发的主要工作已经完成，接下来就是怎么把元素搬迁到新hash表里了。如果现在就一次全量搬迁过去，显然接下来会有比较长的一段时间map被占用（不支持并发）。所以搬迁的工作是异步增量搬迁的。
在插入和删除的函数内都有下面一段代码用于在每次插入和删除操作时，执行一次搬迁工作：
if h.growing() { // 当前处于搬迁状态
growWork(t, h, bucket) // 调用搬迁函数
}
func growWork(t *maptype, h *hmap, bucket uintptr) {
// 将当前需要处理的桶搬迁
evacuate(t, h, bucket&h.oldbucketmask())
if h.growing() { // 再多搬迁一个桶
evacuate(t, h, h.nevacuate)
}
}
- 每执行一次插入或删除，都会调用growWork搬迁0~2个hash桶（有可能这次需要搬迁的2个桶在此之前都被搬过了）
- 搬迁是以hash桶为单位的，包含对应的hash桶和这个桶的溢出链表
- 被delete掉的元素(emptyone标志)会被舍弃（这是缩容的关键）
3.3 为什么叫“伪缩容”？如何实现“真缩容”？
现在可以解释为什么我把map的缩容叫做伪缩容了：因为缩容仅仅针对溢出桶太多的情况，触发缩容时hash数组的大小不变，即hash数组所占用的空间只增不减。也就是说，如果我们把一个已经增长到很大的map的元素挨个全部删除掉，hash表所占用的内存空间也不会被释放。
所以如果要实现“真缩容”，需自己实现缩容搬迁，即创建一个较小的map，将需要缩容的map的元素挨个搬迁过来：
// go map缩容代码示例
myMap := make(map[int]int, 1000000)
// 假设这里我们对bigMap做了很多次插入，之后又做了很多次删除，此时bigMap的元素数量远小于hash表大小
// 接下来我们开始缩容
smallMap := make(map[int]int, len(myMap))
for k, v := range myMap {
smallMap[k] = v
}
myMap = smallMap // 缩容完成，原来的map被我们丢弃，交给gc去清理