Golang map 底层原理

Golang
,

map 数据结构

在平常使用的 map 其实是一个语法糖，在底层实现中是一个 hmap 结构体：

1
2
3
4
5
6
7
8
9
10
11
12
type hmap struct {
    count     int
    flags     uint8
    B         uint8
    noverflow uint16
    hash0     uint32
    buckets    unsafe.Pointer
    oldbuckets unsafe.Pointer
    nevacuate  uintptr

    extra *mapextra
}
  • count：已经存储的键值对个数；
  • B：常规桶的个数为 2^B 个；
  • noverflow：溢出桶的个数；
  • hash0：hash seed，用于计算 key 的哈希值；
  • buckets：常规桶 bmap 的起始地址；
  • oldbuckets：在扩容时，保存原来常规桶的地址；
  • nevacuate：在渐进式扩容时，指明下一个要迁移的旧桶编号。

map 中一个 bucket 由结构体 bmap 表示：

1
2
3
4
5
6
7
type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

一个 bucket 内最多装 8 个键值对，并且为了使得内存使用更加紧凑，以减少内存使用，将 8 个 key 放一起，8个 value 放一起，对每个 key 只保存其哈希值的高 8 位。

还有一个字段没有介绍，那就是 extra：

1
2
3
4
5
type mapextra struct {
    overflow     *[]*bmap //把已经用到的溢出桶链起来
    oldoverflow  *[]*bmap //渐进式扩容时，保存旧桶用到的溢出桶
    nextOverflow *bmap   //下一个尚未使用的溢出桶
}

这里面存储了溢出桶相关的信息。由于一个桶中只能存储 8 个键值对，当有新的键值对来了时，不可能马上发起扩容，因为扩容操作的代价是比较大的。所以这里引入了溢出桶。

当当前桶满了之后，检查 nextOverflow 看是否还有可用的溢出桶，如果有则将新的键值对放入溢出桶中，并将 bmap 的 overflow 设置为溢出桶的地址。

map 使用的哈希函数

在程序启动的时候，会检测 CPU 是否支持 AES，如果支持则会使用 AES Hash，否则将使用 memhash。

map key

在 Golang 中，所有能够用 == 比较的类型都可以作为 map 的key。这是因为可以用 == 比较的类型，它的类型元数据中都提供了 hash 和 equal 用来比较。

所以比如 slice，它的类型元数据中是没有提供可用的 equal 方法的，所以不能当做 map 的 key。

map 可以用 float64 作为 key 吗？理论上来说是可以的，因为 float64 是可以通过 == 来比较的。但是用 float64 作为 key 会由于精度的问题出现一些诡异的现象，对 map 来说，可能几个不一样的 float64 值会是同样的 key。

这是因为 float64 作为 key 时，先要通过 math.Float64frombits 将 float64 转成 uint64，再插入 key 中。所以在将 float64 转换的过程中可能就会丢失精度了。

所以尽量不要使用 float64 作为 map 的 key。

key 的定位过程

在 64 位机器上，key 通过哈希函数计算后，会得到 64 位的哈希值。如何计算这个 key 应该落在哪个桶中呢？要根据桶的数量来计算，如果 B 等于 5，则表明现在有 2^5 个桶。所以这时候会取哈希值的最低 5 位值来得到桶的编号。接着再用哈希值的最高 8 位（tophash），来判断应该放在哪个位置。

如果在常规桶中没有找到并且溢出桶不为空，则还要去溢出桶中寻找，直到找对应的 key，或者找遍所有的位置。

所以可以看出来，在哈希桶与哈希桶之间使用的是链地址法，而在哈希桶内部则使用的是开放定址法。

map 扩容

翻倍扩容

判断哈希表是否需要扩容的指标称作负载因子，即键值对的数量和桶数量的比值，Golang 中默认为 6.5。当超过负载因子的时候就出发翻倍扩容，分配新桶数目是旧桶的两倍，将 hmap.oldbuckets 指向旧桶，hmap.buckets 再指向新桶，并把 hmap.nevacuate 置为 0，表示接下来要迁移的桶为 0 号旧桶。

并且为了防止扩容占用的时间太长而导致性能抖动，所以选择了渐进式扩容，即把旧桶中的值分多次挪到新桶里。在触发扩容后，先分配新桶，并且标记该 map 正在扩容。在后续的读写操作中，如果发现 map 在扩容中，则迁移一部分键值到新桶里，这样可以把扩容消耗的时间分散到多次操作中。

直到所有旧桶迁移完毕后，hmap.oldbuckets 将会被设置为 nil 等待被 GC，一次翻倍扩容就结束了。

等量扩容

与翻倍扩容不同的是，等量扩容的触发是由于使用的溢出桶过多了。

那用多少溢出桶算多呢？

  1. 如果常规桶数量不大于 2^15，那么溢出桶比常规桶数量还多，就算多了；
  2. 如果常规桶数量大于 2^15，那么溢出桶的数量也大于 2^15 次方，就算多了。

那等量扩容的作用是什么呢？反正桶的数量也没有变化。当 map 的负载因子没有超过上限，就表明其中其实没有那么多键值对，却还是用到了这么多溢出桶，说明该 map 中有很多键值对已经被删除了。

所以使用等量扩容可以将这些稀疏存储的键值对变得更加紧凑，可以减少对溢出桶的使用。

map 的元素是可寻址的吗？

由于扩容过程中，会发生键值对迁移，所以键值对的地址也会发生变化，从而导致 map 的元素是不可寻址的。如果要取一个 value 的地址则不能通过编译。