Go map 的总体结构

  1. type hmap struct {
  2.     count     int        // 元素个数
  3.     flags     uint8        // 写标志，是否有 goroutine 在写该 map
  4.     B         uint8        // buckets 的长度，len(buckets) = 2 ^ B
  5.     noverflow uint16
  6.     hash0     uint32    // 随机遍历时的哈希种子？
  8.     buckets    unsafe.Pointer    // 正常桶
  9.     oldbuckets unsafe.Pointer
  10.     nevacuate  uintptr
  12.     extra *mapextra        // 溢出桶
  13. }
  15. type mapextra struct {
  16.     overflow    *[]*bmap
  17.     oldoverflow *[]*bmap
  18.     nextOverflow *bmap
  19. }
  1. type bmap struct {
  2.     topbits  [8]uint8
  3.     keys     [8]keytype
  4.     values   [8]valuetype
  5.     pad      uintptr        // 用于内存对齐
  6.     overflow uintptr
  7. }

map - 图1
map - 图2

  1. // tophash 的六个状态
  2. emptyRest      = 0 // 不仅当前的 K-V 位置可用，其后的 K-V 位置均可用
  3. emptyOne       = 1 // 
  4. evacuatedX     = 2 
  5. evacuatedY     = 3
  6. evacuatedEmpty = 4
  7. minTopHash     = 5
  1. 在存储上，使用正常桶 buckets 与溢出桶 extra 结合，每个正常桶有一个溢出桶。
  2. 这里值得注意的是，buckets 的长度被设为 2 的幂，即 len(buckets) = 2^B，原因是后面哈希函数需要根据 B 来定位 buckets。
  3. 正常桶最多存储 8 个键值对，多余的存储在溢出桶，溢出桶也是 8 个满一桶。
  4. 从结构上看，tophash -> keys[x] -> values[x]
  5. 8 位的 tophash 字段的作用：
    1. 当 K-V 对存在时，tophash 存储 hash(key) 的高 8 位。
    2. 当 K-V 对不存在时，tophash 存储 K-V 的位置状态。

问题：如何保证 hash(key) 的高 8 位一定不小于 5 呢？
解决：当 hash(key) 的高 8 位小于 5 时，会加上 minTopHash 作为最终的 tophash

哈希函数

在程序启动时，会检测 cpu 是否支持 aes，如果支持，则使用 aes hash，否则使用 memhash。

哈希冲突

想要了解哈希冲突是怎么发生的，首先要知道 key 是怎么定位的。

key 的定位过程（查找）

微信图片_20210809164104.jpg

  1. 首先通过哈希函数计算出 64 位二进制值；
  2. 然后根据 B 的大小，取后 B 位为 buckets 数组的索引，访问桶；
  3. 在桶内根据高 8 位 tophash 匹配 key。

冲突发生与解决

从 key 的定位过程可以看出，当 key 经过哈希函数被分配到同一个桶里，就发生了哈希冲突，这时会遍历桶找到空位，若无空位则放到溢出桶。
微信图片_20210809164731.jpg

增删查改

大致说明一下插入，删除，查找，修改四个操作的大致过程，这四个过程都基于查找，详见哈希冲突部分中 key 的定位过程。

插入

  1. 在定位正常桶之后，会遍历比较已有的 key 查看 key 是否已存在；
  2. 当正常桶未满，若不存在，则将其放到遍历过程中遇到的第一个空位上；若已存在，则修改对应的 value；
  3. 若桶已满，在溢出桶重复以上操作。
  4. 若恰好正常桶和溢出桶都满了，就多开一个溢出桶。

以上只是大致过程，
实际上在插入过程中，还会根据 flags 字段判断是否有其他 goroutine 也在对 map 进行写操作，是的话会直接 panic，所以 map 是线程不安全的。
此外，还涉及扩容。

删除

  1. 定位正常桶；
  2. 遍历寻找 key；
  3. 将对应的 value 置为 nil，修改 tophash 的状态。

实际上删除前，也会根据 flags 字段判断是否有其他 goroutine 也在对 map 进行写操作，是的话会直接 panic。

tophash 六种状态的含义与作用

minTopHash

含义：当 K-V 对存在时，hash(key) 高 8 位的最小值是 5，因此当 tophash < 5 时表示 K-V 不存在，当 tophash >= 5 时表示 K-V 不存在。
如何保证 hash(key) 高 8 位不小于 5 呢？

  1. // 源码解决
  2. func tophash(hash uintptr) uint8 {
  3.     top := uint8(hash >> (sys.PtrSize*8 - 8))
  4.     if top < minTopHash {
  5.         top += minTopHash
  6.     }
  7.     return top
  8. }

emptyRest

含义：不仅当前的 K-V 位置可用，其后的 K-V 位置均可用
赋值：

  1. 初始化每个 tophash 都为 emptyRest
  2. 删除 K-V 对时会判断 tophash 是否应该置为 emptyRest

作用：

  1. 判断 bmap 是否为空，当 tophash[0] = emptyRest 时，说明 bmap 是空的。
  2. 提前结束 bmap 遍历，当遍历到某位置时发现 tophash[i] = emptyRest 则可结束遍历。

emptyOne

含义：当前的 K-V 位置可用，不知其后的 K-V 位置是否可用
赋值：

  1. 删除 K-V 对时会先令 tophash = emptyOne

作用：

  1. 判断 bmap 是否为空，当 tophash[0] = emptyRest 时，说明 bmap 是空的。
  2. 提前结束 bmap 遍历，当遍历到某位置时发现 tophash[i] = emptyRest 则可结束遍历。

evacuatedX & evacuatedY

含义：扩容后，元素被分配到了 X 部分还是 Y 部分，下图是翻倍扩容，新桶容量是酒桶容量的两倍，因此可以划分为 X, Y 两个部分。
image.png

evacuatedEmpty

含义：扩容完成后，旧桶上所有的 tophash 都被置为 evacuatedEmpty

修改

先查找，找到 key 了就修改对应的 value

扩容策略

扩容过程不是原子的。

装载因子与扩容时机

在 go 的 map 中，装载因子定义为 loadFactor := count /(2^B)，即元素个数除以桶的个数。
扩容的两个条件如下：

  1. loadFactor >= 6.5 触发翻倍扩容。
  2. 溢出桶太多触发等量扩容

等量扩容

为什么会出现大量溢出桶？原因很简单，先大量插入，然后删除，再插入，产生大量溢出桶，但没有满足条件一触发翻倍扩容。溢出桶太多，使得 key 很分散，查找效率低。（一个大城市，住户却很少）
解决：新开一个桶（可能也需要溢出桶），把原来正常桶和溢出桶的有效 K-V 对搬进来，使得排列紧密。

翻倍扩容

loadFactor >= 6.5 说明一个桶里平均有 6-7 个元素，桶太少了。
此时 B = 1，使得桶的数量翻倍。
一个桶内的元素会被分配到两个桶中。