Golang Map 基本原理

Go 语言中的 map 即哈希表。哈希表把元素分到多个桶里，每个桶里最多放8个元素。在访问元素时，首先用哈希算法根据 key 和哈希表种子获得哈希值(暂将其命名为 h)，然后利用 h 的低 $b$ 位得到桶的序号。其中桶的个数为 $2^b$ 个，是 2 的幂。桶中存储了所有元素的 key、value 和 key 哈希值的高 8 位。所以在找到桶之后会遍历元素的高 8 位哈希值，判断与 h 的高 8 位哈希值是否相等，若相等则再对比 key。如果在当前桶中没有找到 key，还会与溢出桶的元素进行比较。

在哈希表的数据结构中，结构体 hmap 是哈希表的核心，里面记录了一些元数据，例如元素数据、桶的数量、哈希表种子，还有用于储存数据的 buckets 数据。

type hmap struct {
/**元数据**/
  count int // 哈希表元素数量
  B int // 2^B=桶的个数 
  hash0 uint32 // 哈希表种子，在创建哈希表时确定
/**存储**/
  buckets []bmap // 桶，一个桶中最多有8个元素
  mapextra struct { // 溢出桶
    overflow *[]*bmap // 非预分配的溢出桶
    nextOverflow *bmap // 指向预创建的溢出桶 
  }
}
1
2
3
4
5
6
7
8
9
10
11
12

bmap 是桶的结构，里面存储了每个元素的 key、value 和哈希值的高 8 位。

type bmap struct {
    topbits [8]uint8 // 哈希值高 8 位
    keys [8]keytype // 存储key
    values [8]valuetype // 存储value
    overflow *bmap
}
1
2
3
4
5
6

哈希表的逻辑结构是正常桶和溢出桶组成链表，但其内存结构是正常桶与预创建的溢出桶在连续的内存空间中，其它溢出桶在需要时才会创建，内存不连续。

map 的创建过程：首先根据 make(map[keytype]valuetype, cap) 中传入的容量计算出桶的个数，计算规则是找出最大的 $B$ 使得 $\text{cap}>6.5\ast 2^B$，其中 6.5 是装载因子，表示平均一个桶里面放多少个元素。其中的 $B$ 代表正常桶的个数，在创建 $2^B$ 个正常桶时，还要创建 $2^{B-4}$ 个溢出桶，因为可能会出现哈希函数产生了不均匀的哈希值，导致一个桶序号中包含的元素不止 8 个。

新增元素过程：如果新增的元素不存在于当前哈希表中，则把元素添加到正常桶中，如果正常桶满了，就尝试添加到溢出桶中，如果溢出桶也满了，则创建新的溢出桶。

扩容过程包含两步，首先创建一组新桶，然后迁移数据。新桶的大小由两个因素决定，如果装载因子超过 6.5，则容量翻倍，如果只是溢出桶太多，则容量不变。溢出桶多通常发生在向 map 中添加了很多元素后来又删掉的情况，容量不变的意义是将溢出桶中的数据“放回”正常桶中，不过不是放回原来的正常桶，而是放到新建的桶中。

在为新桶分配好内存后且在迁移数据之前会用 hmap.oldbuckets 指向旧桶。当有新的访问请求时优先访问旧桶，如果旧桶已迁移才会访问新桶。迁移数据的过程是惰性的，只有在 map 赋值或者删除时才会触发数据迁移，并且值迁移当前桶即对应的溢出桶，比如在 delete(map, key) 时计算出桶序号是 2，在旧桶大小为 4 的情况下，会把 2 号桶即其溢出桶根据哈希值复制到新 2 号和新 6 号桶中。