go 中的 map 也是 hashmap，由哈和(bucket)数组组成，每个 bucket 可以存放若干元素(默认8个)，当超过 8 个元素后，hmap会使用extra中的overflow指向新的 bucket 来拓展该bucket；
bucket 数组 tophash 数组 data字节数组 overflow 链表
1. hashmap 的数据结构：
type hmap struct {
count int // 当前保存的元素个数
...
B uint8 // 指示bucket数组的大小
...
buckets unsafe.Pointer // bucket数组指针，数组的大小为2^B
...
}
image.png
2. bucket 的数据结构：
type bmap struct {
tophash [8]uint8 //存储哈希值的高8位
data byte[1] //key value数据:key/key/key/.../value/value/value...
overflow *bmap //溢出bucket的地址
}
- tophash 数组长度为 8，哈希值相同的 key 存入 bucket 时，将哈希值高位存储在该数组中；
查找时，tophash 用来快速查找key值是否在该bucket中，而不用每次都通过真值全量进行比较； - data 区存放实际 key/value，存储方式是 k1k2k3k4...v1v2v3v4...，节省字节对齐带来的空间浪费；
比如：map[int64]int8，key 是 int64（8个字节），value是int8（一个字节），kv的长度不同，如果按照kv格式存放，则考虑内存对齐v也会占用int64，而按照后者存储时，8个v刚好占用一个int64。 - overflow 指向的是下一个 bucket；
如果 bucket 已经存储了 8 个值，bucket 会使用 overflow 指向新的 bucket 来存储新的碰撞值；
image.png
哈希冲突后的数据结构：
overflow 表示溢出的意思
image.png
3. 负载因子
负载因子用于表示哈希冲突的情况 = 键数量 / bucket 的数量
哈希因子需要控制在合适的大小，超过阙值后需要 rehash
* 哈希因子过小，说明空间利用率低
* 哈希因子过大，说明冲突严重，存取效率低
每个 hash 表的实现对负载因子的容忍程度不同，redis 中负载因子为 1 时就会触发 rehash，因为 redis 的每个 bucket 只能存储一个键值对。而 go 的能存储 8 个，负载因子为 6.5；
4. rehash
4.1 扩容的前提条件
为保证访问效率，当新元素要添加时，都会检查是否需要扩容，扩容实际是空间换时间；
- 触发扩容的条件
负载因子达到了 6.5
overflow 数量 > 2^15
4.2 增量扩容
负载因子超过阙值后，新建一个 buckets，长度为原来的2倍，旧 buckets 的数量逐渐搬迁至新的 buckets 中。
如果数据量较大，采取渐进式hash，每次访问 map 都会触发一次搬迁，每次搬迁2个键值对，搬迁完成后将会删除 oldbuckets；
即将搬迁.png
搬迁中.png
搬迁完成.png
4.3 缩容
image.png
通过不断地删除，键值对集中在一小部分地 bucket 中，overflow 中大部分是空的，经过重新组织后 bucket 的数量会减少，提高访问效率；
5 查找过程
- 根据 key 算出哈希值
- 取 hash 值的低位和 hmap.B 取模确定 bucket 的位置
- 取 hash 值高位在 tophash 数组中查询
- 如果有，则去 bucket 中找该 key
- 如果当前 bucket 中没有，则从 overflow 指向的 bucket 中找
- 如果当前处于搬迁过程中，则优先从 oldbucket 中查找
6 更新过程
- 根据 key 算出 hash 值
- hash 值对 hmap.B 取模确定 bucket 的位置
- 如果 key 存在，则更新值，如果不存在则插入
