go 的 map 实现原理

Go 语言的map 使用 hash 表作为底层实现，一个 Hash 表可以有多个 bucket，而每个 bucket 保存了 map 中的一个或一组键值对。

map的内存模型

map.jpg

type hmap struct {
    count      i nt               // 元素个数
    flags      uint8
    B          uint8             // buckets 数组的长度就是 2^B 
    hash0      uint32 
    buckets    unsafe.Pointer    // 指向 buckets 数组，大小为 2^B，如果元素个数为0，就为 nil
    oldbuckets unsafe.Pointer    // 老旧的 buckets 数据，用来扩容 
    nevacuate  uintptr       
    extra      *mapextra 
}

buckets 是一个指针，最终它指向的是一个结构体：

type bmap struct {
    tophash [bucketCnt]uint8
}

但这只是表面(src/runtime/hashmap.go)的结构，编译期间会给它加料，动态地创建一个新的结构：

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr    // 溢出buckets
}

bmap 就是我们常说的 bucket，元素经过 hash 运算后就会落到某个 bucket 中存储。

image.png

注意到 key-value 不是 ke/value key/value 这样放在一起的，是 key/key/.../value/value/的形式，源码解释是为了可以省掉paddding，节省内存空间。

hash 冲突

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

  image.png

  在bucket 的数据结构中使用指针指向溢出的 bucket，意为当前的 bucket 盛不下而溢出的部分，这并不是一件好事，因为它降低了存取效率。

• 负载因子
  负载因子用于衡量一个 Hash 表冲突的情况，公式为：

  

  对于一个 bucket 数量为4，包含4个键值对的 Hash 表来说，这个 hash 表的负载因子为1，负载因子过小或者过大都不理想：

  • 负载因子过小，说明空间利用率低。
  • 负载因子过大，说明冲突严重，存取效率低。
    当 hash 表负载因子过大时，需要申请更多的 bucket，并对所有键值对重新组织，使其均匀分布到这些 bucket 中，这个过程称为 rehash。每个 hash 表的实现对负载因子容忍程度不同，比如 Redis 的map 实现中负载因子为1 就会触发rehash，而 go 是 6.5，因为 Redis 每个 bucket 只能存1个键值对，而 go 的bucket 可以存 8个键值对。

扩容

• 扩容条件
  降低负载因子常用的手段是扩容，为了保证访问效率，当新元素将要添加进 map 时。都会检查是否需要扩容，扩容实际上是以空间换时间的手段。
  触发扩容需要满足下列的条件：

  • 负载因子大于6.5时，即平均每个 bucket 存储的键值对达到 6.5 个以上。
  • overflow 的数量达到 2^min(15, B) 时。

• 增量扩容
  当负载因子过大时，就新建一个 bucket 数组，新的 bucket 数组的长度是原来的2倍，然后旧的 bucket 数组中的数据搬迁到新的 bucket 数组中。
  考虑到如果 map 存储了数以亿计的键值对，那么一次性搬迁会造成比较大的延时，所以 Go 采用逐渐搬迁策略，即每次访问 map 时都会触发一次搬迁，每次搬迁2个键值对。
  比如现在有一map，存储了 7个键值对，只有1个bucket，此时负载因子为7，再次添加时会触发扩容操作，扩容之后再将新的键值对写入新的 bucket 中。当添加第8个键值对时，将触发扩容：

  image.png

  扩容时，先让hmap中的oldbuckets指向原buckets数组，然后申请新的buckets数组，并将数组指针保存到 hmap数据结构的buckets成员中，这样就完成了新老buckets数组的交接，后续的迁移工作将是从oldbuckets数组逐步搬迁键值对到新的buckets数组中，待oldbuckets数组中的所有键值对搬迁完毕后，就可以安全的释放 oldbuckets数组。

• 等量扩容
  等量扩容，并不是扩大容量，而是 bucket 数量不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使 bucket 的使用率更高，进而保证更快的存取效率。

key 的查找

查找过程如下：

• 根据 key 值 计算 hash 值
• 取 hash 值低位 与 hmap.B 取模来确定 bucket 的值
• 取 hash 值高位，在 tophash 数组中查询
• 如果 tophash[i] 中存储的 hash值 与当前的 key 的 hash 值相等，则获取 tophash[i] 的 key 值进行比较
• 当前bucket 中没有找到，则从溢出的bucket继续查找

如果当前 map 处于搬迁过程中，那么查找时优先从 oldbuckets 数组中查找。然后再从新的buckets 数组中查找。

key 的添加

新元素添加过程如下：

• 根据 key 的值计算 hash 值
• 取 hash 值低位 与 hmap.B 取模来确定 bucket 的值
• 查找该 key 是否已经存在，如果存在则直接更新值
• 如果该 key 不存在，则从该 bucket 中寻找空余位置并插入

如果当前 map 处于搬迁过程中，那么新元素会直接添加到新的buckets 数组中。

key 的删除

删除元素实际上先查找元素，如果元素存在则把元素从相应的 bucket 中清除，如果不存在则什么都不做。