哈希碰撞的解决方式
hash 获取桶索引的方式：
取模: hash % m;
与运算: hash & (m-1)
m 代表桶的数量
我们知道当 hash key 都相同，即产生 hash 碰撞，有两种方式解决。
拉链法
先看图理解
我们看到 "John Smith" 与 "Sandra Dee" 的 hash(key) 对应的桶号都相同是 152
152 这个桶会变成一个链表，即大家的key相同，值不同。
如果我们要找 key "Sandra Dee" 的时候，就先通过 hash 函数找到152号桶, 然后遍历链表，找到 “Sandra Dee”。
开放寻址法
从图中看出， "John Smith" 与 "Sandra Dee" 的 hash(key) 对应的桶号都相同是 152，产生 hash 碰撞，
那么后加入的元素 "Sandra Dee" 自动放在 152 相邻的后一个位置 153 号桶，
如果 "Ted Baker" 的 hash 值是153，发现153已经被占用了后，就放在相邻的后一个位置 154 上。
说的题外话，我们仔细思考一下就会发现，所谓 hash map 的时间复杂读是 O(1)，那是理论上。
但如果我们的 hash 函数选的不好，散列不均匀，老是发生 hash 碰撞，即 hash map 的时间复杂度就会变成 O(n)。
所以要想 hash map 的性能好，hash 函数的选择是关键。
好了开始进入正题。
底层数据结构
hmap
即 map 的数据结构
type hmap struct {
count int // 元素数量
flags uint8 // 当前map的状态(具体有哪些状态，在map.go文件开头就能看到)
B uint8 // 2^B = bucket size (桶数)
noverflow uint16 // 已经使用了的溢出桶的数量
hash0 uint32 // hash seed
buckets unsafe.Pointer // 桶的地址指针
oldbuckets unsafe.Pointer // 旧桶的地址指针
nevacuate uintptr // 下一个要迁移的旧桶编号
extra *mapextra // 溢出桶
}
这里的 buckets 是 bmap 结构体的数组的头指针。
这里的旧桶主要是为了扩容时使用。
溢出桶则是当一个桶存满了，数据就存到溢出桶，这也就是 开放地址寻址法 的体现。
bmap
即 bucket(桶)的数据结构:
type bmap struct {
tophash [bucketCnt]uint8
}
bucketCnt = 8，即 tophash 是一个定长为 8 的数组，存储的是每个key 的 hash 值的高 8 位。 key是顺序存储的，所以 tophash也是以key的顺序存储的高8位 hash 值。
这里为什么没有看到 key, value呢？
编译期间会给它加料，动态地创建一个新的结构:
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
}
bmap 还有 3 个方法，他的溢出桶 bmap.overflow 是一个方法：
func (b *bmap) overflow(t *maptype) *bmap {
return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize))
}
咱们再来一张图就比较容易形象地理解了:
mapextra
type mapextra struct {
overflow *[]*bmap // 已经使用了的溢出桶
oldoverflow *[]*bmap // 旧桶使用了的溢出桶
nextOverflow *bmap // 下一个溢出桶的地址
}
overflow 存储当前已经使用了的溢出桶
oldoverflow 则是在扩容阶段存储旧桶的溢出桶地址
hmap，bmap，mapextra 的关系如下图:
接下来从源码可以看到：
// src/runtime/map.go
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
...
}
如果桶的数量 >= 2^4时，有大概率会提前创建好 2^(B-4) 个溢出桶。
再从上图中我们也可以看出，桶和 mapextra 中溢出桶的地址是连续的。nextOverflow 是第一个要被使用的溢出桶地址（头节点）。
从上一小节(bmap)得知每个桶都会有一个溢出桶，当桶的溢出桶也存满了后，就会用到 mapextra 中的溢出桶。这是从图中看出 nextOverflow 指向了第二个溢出桶地址
当 mapextra 中一个溢出桶用完后，hmap 中 noverflow 字段值就+1。mapextra 中的 overflow slice 就追加一个已经使用了的溢出桶地址。
扩容
hash map 有个负载因子的概念： 负载因子 = count(元素个数) / 2^B(桶的个数)
当负载因子 > 6.5 的 时候，就进行翻倍扩容；
如果 溢出桶数量(noverflow)较多：
B <= 15 && noverflow >= 2^B 或者 B > 15 noverflow >= 2^15， （uint16(1)<<(B&15) 为 2^B 的意思）
这两种情况下, 就表示溢出桶数量较多了，源码如下:
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
if B > 15 {
B = 15
}
return noverflow >= uint16(1)<<(B&15)
}
第二种情况就是等量扩容
扩容过程不是立即执行的，而是渐进式的
扩容的时候， hmap 结构体中 oldbuckets字段 的值 = bucket（当前的bucket），bucket字段 就指向新的桶数组头指针。
nevacuate 字段存储要迁移的旧桶编号，比如下图中的 编号就是 0:
翻倍扩容
当装载因子大于6.5时，即元素过多桶太少的情况，就会发生翻倍扩容
扩容时，让B += 1，这时桶的数量扩大一倍， 假设扩容之前B=2
索引的计算 h & ( 2^B - 1 )，之前索引看tophash的低2位，新的索引需要重新计算，需要看tophash的低3位，按照新索引从旧桶分流到新桶
流程大概如下：
假设扩容前，旧桶数量是4个（B=2）
假设装载因子此时很高了，每个桶都装满了8个
我们拿第0个旧桶中个元素的tophash举例
可能为xxxxx000, xxxxxx100这两种（因为这两种二进制的tophash & 3 = 0, 2^B-1 = 3）
现在，发生扩容
原先第0号旧桶中的xxxxx000 & 7 = 0 , 放入新的0号桶
原先第0号旧桶中的xxxxx100 & 7 = 0 , 放入新的4号桶
（这里比如xxxxx00, 因为当前桶数量是4个，用两位即可表示，所以我们只关注hash值的最低两位，其实就是B的值）
之前获取桶索引的方式如下（以0号为例）:
hash值: xxxx00
4(桶的数量)-1: & 11
----------------------
00
这样一个 hash值的 key 就会存储到 0 号桶。
扩容后新桶树变成8，获取桶索引的方式如下:
hash值: xxxx00
8(桶的数量)-1: & 111
----------------------
x00
比如得到的值，如果是100，那么就是到 4 号桶
如果是 000 到 0 号桶。
所以旧桶的 tophash/key/value 会自动分流到等距的新桶中。如下图：
所以，旧桶中的元素，一部分运往新桶的前一半，一部分运往新桶的后一半。
源码里提到 X, Y part，其实就是我们说的如果是扩容到原来的 2 倍，桶的数量是原来的 2 倍，前一半桶被称为 X part，后一半桶被称为 Y part。
一个 bucket 中的 key 可能会分裂落到 2 个桶，一个位于 X part，一个位于 Y part。所以在搬迁一个 cell 之前，需要知道这个 cell 中的 key 是落到哪个 Part。
很简单，重新计算 cell 中 key 的 hash，并向前“多看”一位，决定落入哪个 Part。
以上计算过程就是一个取模运算过程（转换为移位运算）
等量扩容
我们发现map在不断地插入元素、删除元素的过程中，可能会出现很多溢出桶，导致元素在桶内的分布很松散，（房子多、人少），查找时，会不断的在bucket之间链式搜索，性能会趋近于一个链表，时间复杂度为O(n)，这时为了优化这个问题，就会等量扩容。
等量扩容就是，生成数量一样的桶数组，然后搬迁到新桶。既然一样，迁移来迁移去有啥意思？
这里就要说一下，map 的 delete 了。
map 的 delete 并不会物理删除桶中的 tophash，而是将值改为 emptyOne。这样逻辑上咱们的桶 就有空间被浪费了。
等量扩容就可以节约空间，使空间更加紧凑。如下图:
由于是等量扩容，桶的索引无需重新计算，直接搬迁到同样索引的新桶即可。
“渐进式"扩容
在扩容时，如果有大量的 key/value 需要搬迁，会非常影响性能。
因此 Go map 的扩容采取了一种称为“渐进式”地方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2个桶 (var xy [2]evacDst)。
真正搬迁 buckets 的动作在 growWork() 函数中，而调用 growWork() 函数的动作是在 mapassign 和 mapdelete 函数中。
也就是插入或修改、删除 key 的时候，都会尝试进行搬迁 buckets 的工作。
oldbuckets nil 则说明搬迁做完了。
特殊情况
有一个特殊情况是：有一种 key，每次对它计算 hash，得到的结果都不一样。这个 key 就是 math.NaN() 的结果，它的含义是 not a number，类型是 float64。
当它作为 map 的 key，在搬迁的时候，会遇到一个问题：再次计算它的哈希值和它当初插入 map 时的计算出来的哈希值不一样！
你可能想到了，这样带来的一个后果是，这个 key 是永远不会被 Get 操作获取的！当我使用 m[math.NaN()] 语句的时候，是查不出来结果的。这个 key 只有在遍历整个 map 的时候，才有机会现身。所以，可以向一个 map 插入任意数量的 math.NaN() 作为 key。
当搬迁碰到 math.NaN() 的 key 时，只通过 tophash 的最低位决定分配到 X part 还是 Y part（如果扩容后是原来 buckets 数量的 2 倍）。如果 tophash 的最低位是 0 ，分配到 X part；如果是 1 ，则分配到 Y part。
PS:
当桶的容量用完后，会通过 翻倍扩容 和等量扩容 两种方式来进行扩容。
扩容是渐进式的。
golang没有重载，map 访问为什么有下面两种写法？
v := m[key]
v, ok := m[key]
这是编译器做了工作，第一种写法 编译时 Op 值为 OINDEXMAP，第二种是 OAS2MAPR。
根据不同的 Op 值 ，在运行时调用不同的函数：
// src/runtime/map.go
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
(这1，2的函数命名方式.. google的开源项目也这样么 -_-!!!)
文章出处：
《深入golang -- map》https://zhuanlan.zhihu.com/p/495750540
下面这篇文章讲得很详细，结合上面的那篇，搞懂map真是so easy啦。
《GoLang之map的扩容过程是怎样的(7)》https://blog.csdn.net/weixin_52690231/article/details/125265834
https://geek-docs.com/go-tutorials/go-examples/t_goland-program-to-read-a-number-n-and-print-the-series-1plus2plus-plusn.html
https://www.topgoer.com/beego框架/
https://www.topgoer.cn/docs/gomianshiti/mian105