Skip to content

map 实现原理

go 的 map 采用的是 拉链法，负载因子 6.5

单位是桶 bucket，一个桶里可以放 8 对。为了内存对齐，8 个 key 会存放在一起，8 个 value 存放在一起。

在桶的顶部，存放着 8 个 key 的哈希值的高 8 位；而桶的底部，存放下一个桶的地址（因为用的是拉链法）

放入

一个 map 被初始化后会给定一定数量的桶，但一对 kv 被加入到哈希表中时，需要选择放在哪个桶里。

对于桶的选择，有两种方式：

  1. 将 key 进行哈希，然后将哈希值与桶的数量 m 取模：hash(key) % m
  2. 将 key 进行哈希，然后将哈希值与桶的数量 m 减一进行 与运算：hash(key) & (m-1)

Go 的 map 采用的就是与运算。

Tip

进行与运算的方式，要求桶的数量 m 必须是 2 的整数次幂。例如 2, 4, 8, 16, 32

因为 2 的整数次幂都是只有最高位一位为 1，其余位为0，而减一的数字一定是除了最高位，其余位都为 1。

例如：4 的二进制为 100，只有第3位为1；4-1=3 的二进制为 011，除了第三位，第二位个第一位都是 1。

这样进行与运算以后，能确保得出的数字不会落在编号不存在的桶里。

例如：桶的数量为 8(1000)，减1为 7(0111)，hash(key) 的值假设为 9(1001)，计算 9 & 7

1
2
3
4
1001
0111
---------
0001
可以得到被选择的桶编号 1。

扩容

kv 对的数量 count 与桶的数量 m 比值称为「负载因子」，Go 中设置为 6.5。

当超过负载因子的时候，也就是所有的桶里已经装了 6成半的 kv 对的时候，就需要进行扩容。

当哈希表要分配的桶的数目大于 \(2^4\)，也就是 hmap.B > 4 的时候，即认为使用溢出桶的几率比较大，所以会先预分配 \(2^{B-4}\) 个溢出桶备用。

溢出桶与常规桶在内存中是连续的，预分配后一共会有 \(2^B + 2^{B-4}\) 个桶，前 \(2^B\) 个用作常规桶，后面 \(2^{B-4}\) 个用作溢出桶。

扩容规则

  1. \(\frac {count} {2^B} \gt 6.5\) ==> 翻倍扩容（hmap/B++）
  2. 负载因子没超过 6.5，但已使用的溢出桶 noverflow 较多，则是太过稀疏了，此时扩容规则为：
    • \(B \le 15\)， \(noverflow \ge 2^B\)，进行等量扩容
    • \(B \gt 15\)， \(noverflow \ge 2^{15}\)，进行等量扩容

翻倍扩容，就是创建比现有常规桶更多的桶

等量扩容，就是创建和现有常规桶数量一样的桶。

通常在删除了较多的 kv 对以后会导致哈希标过于稀疏，此时会进行等量扩容，对现有的 kv 对重排，整理磁盘碎片。

扩容步骤(渐进式扩容)

在扩容的时候，不会一次性把旧桶中的 kv 对搬运到新桶中，而是：

  • 旧桶字段 oldbuckets = buckets
  • 在扩容时，先分配足够多的新桶 buckets = newBucketAddr
  • 在哈希表读写时，检测到当前为扩容阶段，就将要读写的 kv 对迁移到新桶
  • 然后在进度字段 nevacuate 记录下一个要迁移的桶编号
  • 直到所有的桶都迁移完成，扩容阶段才算结束。

这种将 kv 对的迁移时间分摊到多次哈希标操作的方式，就叫渐进式扩容，可以避免一次性扩容带来的瞬时性能抖动。

hmap 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
type hmap struct {
    count      int              // kv 对数量 
    flags      uint8            // 是否处于扩容阶段
    B          uint8            // 2的次幂，2^B，这里记录的是次幂，不是 m
    buckets    unsafe.Pointer   // 桶的位置
    oldbuckets unsafe.Pointer   // 旧桶的位置
    nevacuate  uintptr          // 即将迁移的旧桶的编号
    noverflow  uint16           // 溢出桶的数量
    hash0      uint32
    extra      *mapextra
}