天机阁

Golang的map数据结构

2022-07-08 · 7 min read
Go

map 数据结构

Golang 的 map 使用哈希表作为底层实现，一个哈希表里可以有多个哈希表节点，也即 bucket，而每个 bucket 就保存了 map 中的一个或一组键值对。

map 数据结构由 runtime/map.go:hmap 定义：

type hmap struct {
    count     int // 当前保存的元素个数
    ...
    B         uint8  // 指示bucket数组的大小
    ...
    buckets   unsafe.Pointer // bucket数组指针，数组的大小为2^B
    ...
}

下图展示一个拥有4个 bucket 的 map：

上图例子中，hmap.B=2，因此 hmap.buckets 长度是 2B 等于4。元素经过哈希运算后会落到某个 bucket 中进行存储。

bucket 数据结构

bucket 数据结构由 runtime/map.go:bmap 定义：

type bmap struct {
    tophash [8]uint8 //存储哈希值的高8位
    data    byte[1]  //key value数据:key/key/key/.../value/value/value...
    overflow *bmap   //溢出bucket的地址
}

每个 bucket 可以存储8个键值对。

  • tophash 是个长度为8的数组，哈希值相同的键（准确的说是哈希值低位相同的键）存入当前 bucket 时会将哈希值的高位存储在该数组中，以方便后续匹配；
  • data 存储的是 key-value 数据，存放顺序是 key/key/key/...value/value/value，如此存放是为了节省字节对齐带来的空间浪费；
  • overflow 指针指向的是下一个 bucket，据此将所有冲突的连接起来。

下图展示 bucket 存放8个 key-value 对：

哈希冲突

当有两个或两个以上数量的键被哈希到了同一个 bucket 时，我们称这些键发生了冲突。
Go 使用 链地址法 来解决键冲突。
由于每个 bucket 可以存放8个键值对，所以同一个 bucket 存放超过9个键值对时就会再创建一个键值对，用类似链表的方式将 bucket 连接起来。

下图展示产生冲突后的 map：

bucket 数据结构指示下一个 bucket 的指针称为 overflow bucket，意为当前 bucket 盛不下而溢出的部分。事实上哈希冲突并不是好事情，它降低了存储效率，好的哈希算法可以保证哈希值的随机性，但冲突过多也是要控制的。

负载因子

负载因子是用来衡量哈希冲突严重程度的指标，公式为：

负载因子负载因子 = 键数量bucket数量\frac{键数量}{bucket 数量}

例如对于一个 bucket 数量为4，包含4个键值对的哈希表来说，这个哈希表的负载因子为1。
哈希表需要将负载因子控制在合适的大小，超过其阈值需要进行 rehash，即重新组织键值对：

  • 负载因子过小，说明空间利用率低
  • 负载因子过大，说明冲突严重，存储效率低

每个哈希表的实现对负载因子容忍程度不同，比如 Redis 实现中负载因子大于1时就会触发 rehash，而 Go 则在负载因子达到6.5时才会触发 rehash，因为 Redis 的每个 bucket 只能存一个键值对，而 Go 的 bucket 可能存8个键值对，所以 Go 可以容忍更高的负载因子。

扩容

扩容的前提条件

为了保证访问效率，当新元素将要添加进 map 时，都会检查是否需要扩容，扩容实际上是以空间换时间的手段。触发扩容的条件有两个（满足其一）：

  1. 负载因子 > 6.5 时，即平均每个 bucket 存储的键值对达到6.5个；
  2. overflow 数量 > 215时，即 overflow 数量超过32768时；

增量扩容

当负载因子过大时，就新建一个 bucket，新的 bucket 长度是原来的2倍，然后旧 bucket 搬迁到新的 bucket。考虑到如果 map 存储了数以亿计的 key-value，一次性搬迁会造成比较大的延时，Go 采用逐步搬迁策略，即每次访问 map 时都会触发一次搬迁，每次搬迁2个键值对。

下次展示了包含一个 bucket 满载的 map（省略了value区域）:

当前 map 存储了7个键值对，只有一个 bucket。
此时负载因子为7。
再次插入数据时会触发扩容操作，扩容之后再将新插入键写入新的 bucket。

当第8个键值对插入时，将会触发扩容，扩容后示意图如下：

hmap 数据结构中 oldbuckets 指针指向原 bucket，而 buckets 指向了新申请的 bucket。
新的键值对被插入新的 bucket 中。
后续对 map 的访问操作会触发迁移，将 oldbuckets 中的键值对逐步的搬迁出来，当 oldbuckets 中的键值对全部搬迁完毕后，删除 oldbuckets。

搬迁完成后的示意图如下：

数据搬迁过程中原 bucket 中的键值对将存在于新 bucket 的前面，新插入的键值对将存在于新 bucket 的后面。

等量扩容

所谓等量扩容，实际上并不是扩大容量，而是 buckets 数量不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使 bucket 的使用率更高，进而保证更快的存取。
在极端场景下，比如不断的增删键值对，而键值对正好集中在一小部分的 bucket，这样就会造成 overflow 的 bucket 数量过多，但负载因子又不高，从而无法执行增量搬迁的过程。

如下图所示：

由上图可知，overflow 的 bucket 中大部分是空的，访问效率会很差，此时进行一次等量扩容，即 buckets 数量不变，经过重新组织后 overflow 的 bucket 数量会减少，既节省了空间又会提高了访问效率。

map 的查找过程

查找过程如下：

  1. 根据 key 值计算出哈希值；
  2. 取哈希值低位与 hmap.B 取模确定 bucket 位置；
  3. 取哈希值高位在 tophash 数组中查询；
    1. 如果 tophash[i] 中存储值和哈希值高位相等，则去找该 bucket 中的 key 值进行比较；
    2. 如果 bucket 中没有找到，则继续从下个 overflow 的 bucket 中查找；
    3. 如果当前出于搬迁过程，则优先从 oldbuckets 查找。

map 的插入过程

新元素插入过程如下：

  1. 根据 key 值计算出哈希值；
  2. 取哈希值低位与 hmap.B 取模确定 bucket 位置；
  3. 查找该 key 是否已经存在，如果存在则直接更新值；
  4. 如果没找到该 key，就将 key 插入。

本文参考 https://www.bookstack.cn/read/GoExpertProgramming/chapter01-1.3-map.md