哈希表
说到键值对的存储，就会想到哈希表，哈希表的实现通常会用一堆bucket桶来存储键值对。若要新增一个键值对到哈希表，就要选择一个桶，那么怎么选存到哪个桶？
选择桶算法
假设有m个桶（桶编号区间就为0到m-1），先通过哈希函数把『键』处理一下得到一个哈希值，现在要利用这个哈希值从一堆桶中选择一个，有两种方法比较常用：
1.取模法
取模法就是用哈希值与桶的个数m进行取模运算，得到桶的编号 hash(key) % m。
2.与运算法
与运算法：哈希值与m-1进行与运算 hash(key) & (m-1）,若想运算结果落在区间 [0, m-1] 而不会出现空桶，就要限制桶的个数 m 必须是 2 的整数次幂，这样可以保证m的二进制表示一定只有一位是1，那么 m-1 就一定是低于这一位的所有位均为1。 假设 m=4，二进制表示为 100；m-1 的二进制表示则为 011。 桶的索引则为 hash(key) & 011。 如果桶的数目不是 2 的整数次幂，就会出现某些桶永远不会选中的情况。
Go 语言选择桶算法是用的与运算方法。
哈希冲突
现在桶选择好了，如果后来又有新的键值对选择了这个桶，就是发生了哈希冲突，解决冲突的办法常用的也有两种：
1. 开放地址法
假如编号为 2 的桶已经被 key1 占用了，新赠的键 key2 就占用它后面没有被占用的桶。
如果三号桶还没有用，新增的 key2 就会选择3号桶。
查找 key2 这个键值对的时候，虽然会首先定位到 编号为 2 的桶，但是经过比较 key 并不相等，就会遍历它后面的桶，直到 key 相等，或者遇到空桶证明这个 key 并不存在。这就是『开放地址法』。
2. 拉链法
假如2号桶已经被 key1 占用了，没关系，在这个桶上再加一个链表，链接一个新桶存储这个键值对。
查找 key2 时候同样会先找到编号为2号桶，经过比较发现 key 不相等，所以就顺着链表往后查找，这就是『拉链法』。
扩容
不过哈希冲突的发生会影响哈希表的读写效率。选择散列均匀的哈希函数可以减少哈希冲突的发生。适时的对哈希表进行扩容也是保障读写效率的有效手段。
通常会把存储键值对的数目与桶数目的比值，作为是否需要扩容的判断依据，这个比值被称为『负载因子』: Load Factor = count / m。
需要扩容时候就要分配更多的桶，它们就是新桶。需要把旧桶里存储的键值对都迁移到新桶里。如果哈希表存储的键值对比较多，一次性迁移所有桶花费的时间就比较显著，所以通常会在哈希表扩容时先分配足够多的新桶，然后用一个字段 oldbuckets 记录旧桶的位置，再增加一个字段 nevacuate 记录旧桶的迁移进度，例如记录下一个要迁移的旧桶编号。
在哈希表每次读写操作时，如果检测到当前处于扩容阶段，就完成一部分键值对迁移的任务，直到所有的旧桶迁移完成，旧桶不再使用，才算真正完成一次哈希表的扩容。
像这样把键值对迁移的时间分摊到多次哈希表操作中的方式就是『渐进式扩容』,可以避免一次性扩容带来的性能瞬时抖动。
map结构体
Go语言中Map类型的底层实现就是哈希表，map类型的变量本质上是一个指针，*hmap 指向 hmap 结构体。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// A header for a Go map.
type hmap struct {
// count 已经存储的键值对数目
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
// B 记录桶的数目是2的多少次幂（Go语言选择桶用的是与运算方法）
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
// noverflow 记录的使用溢出桶的数量
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
// buckets 记录桶在哪里
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
// oldbuckets 用于在扩容阶段保存旧桶位置
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
// nevacuate 记录渐进式扩容阶段下一个要迁移的旧桶编号
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
// extra 指向mapextra结构体，记录溢出桶信息
extra *mapextra // optional fields
}
// mapextra holds fields that are not present on all maps.
type mapextra struct {
// overflow 是一个slice，记录目前已经被使用的溢出桶地址
overflow *[]*bmap
// oldoverflow 用于在扩容阶段存储旧桶用到的那些溢出桶地址
oldoverflow *[]*bmap
// nextOverflow 指向下一个空闲的溢出桶.
nextOverflow *bmap
}
// bmap 就是map使用的桶结构
// A bucket for a Go map.
type bmap struct {
// tophash 对应哈希值的高8位
tophash [bucketCnt]uint8
}
溢出桶
溢出桶是为了减少扩容次数而引入的，当一个桶存满了，还有可用的溢出桶时，就会在桶后面链一个溢出桶，继续往这里面存储。
实际上如果哈希表要分配的桶的数目大于2^4，就认为使用到溢出桶的几率比较大，就会分配 2^(B-4) 个溢出桶备用，这些溢出桶与常规桶在内存中是连续的，只是 2^B 个用作常规桶，后面的用作溢出桶。
hmap 结构体最后有个 extra 字段指向一个 mapextra 结构体, 里面记录的都是溢出桶相关的信息。
扩容规则
1
2
a := map[string]string
a["k1"] = "v1"
变量 a 本质上是一个 hmap的指针，目前存储了一个键值对，只拥有一个桶，也没有预分配的溢出桶。如果我们把这个桶存满，接下来再存储新的键值对时，这个哈希表是会创建溢出桶呢？还是会发生扩容呢？这就要看map的扩容规则了。
翻倍扩容
Go语言map默认负载因子是6.5，超过这个数就会触发翻倍扩容，分配新桶的数目是旧桶的两倍。
1
2
3
// count：已经存储的键值对数目
// B：桶的数目是2的多少次幂；2^B就是桶的总数
count / (2^B) > 6.5 ————> 翻倍扩容(hmap.B++)
等量扩容
如果负载因子没有超标，但是使用的溢出桶较多，也会触发扩容，不过这一次是『等量扩容』。那么用多少溢出桶就算多了呢？
如果常规桶数目不大于2^15，即 B <= 15，那么当使用溢出桶数目超过常规桶就算是多了。
如果常规桶数目大于2^15，即 B > 15，那么使用溢出桶数目一旦超过2^15就算是多了。
等量扩容的意义
所谓等量扩容，就是创建和旧桶数目一样多的新桶，然后把原来的键值对迁移到新桶中。但是既然等量，迁移来迁移去的有什么用呢？那就需要想一想在什么情况下桶的负载因子没有超出上限值，却偏偏使用了很多溢出桶呢？自然是有很多键值对被删除的情况。
如果满足了等量扩容的触发条件，就会分配等量的新桶。旧桶会迁移到同样编号的新桶。同样数目的键值对迁移到新桶中能够排列的更加紧凑，从而减少溢出桶的使用，这就是等量扩容的意义所在。