Map

参考链接：

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
type hmap struct {
    count     int            // 当前存储的键值对数量
    flags     uint8          // 标志位，用于记录 map 的状态（如是否正在扩容等）
    B         uint8          // 桶数组的大小是 2^B，决定了桶的数量
    noverflow uint16         // 记录溢出桶的数量
    hash0     uint32         // 哈希种子，防止哈希冲突攻击

    buckets    unsafe.Pointer // 指向主桶数组的指针
    oldbuckets unsafe.Pointer // 扩容时，指向旧桶数组
    nevacuate  uintptr        // 记录扩容的进度，表示已经迁移的桶的索引

    extra *mapextra // 存储溢出桶和其他额外信息
}

// 储存溢出桶以及额外信息
type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap
 
	nextOverflow *bmap
}

// 实际上储存键值对的地方
type bmap struct {
	tophash [bucketCnt]uint8
}

// 但是实际中可以通过以上值直接计算出键值对在堆中的位置，所以map实际上是一个索引结构
type bmap struct {
	tophash [bucketCnt]uint8
	keys [bucketCnt]T
    values [bucketCnt]T
    overflow unsafe.Pointer
}

桶结构

img

  • hash值计算：通过 hash 函数计算得出哈希值。
  • 确定桶的位置：通过 hash 值的后面 B 位得出桶的系数，每个桶都有 8 个 slot，每一个slot 最多放置 8 个数据。总共有 2^B 个桶。
    • 如果桶的八个 slot 未满，那么直接存入空闲 slot。
    • 如果当前桶的 8 个 slot 都满了，那么就会开辟一个新的溢出桶，放置在溢出桶里面。溢出桶是链表结构，通过指针连接。
  • 扩容：触发条件是：
    • 装载因子过高（元素数 / 桶数 > 6.5）
    • 溢出桶过多（表示分布均匀）

查询流程

img
以键 k4 为例子：

  • 首先进行 hash 计算，计算得出 k4 的 hash 值（在 64 位操作系统中一般 hash 值为 64 位）
  • 通过最后的 B 计算得出在几号桶。
  • 根据 k4 对应的 hash 值得出在桶的哪个位置需要注意的是，在实现中并没有发现 key，value 的显示定义，这是因为为了实现泛型，key，value 是直接保存在 tophash 之后的内存地址中的，需要在运行时通过 动态内存布局和运行时计算得出的
    • 如果前八位一致，那么就直接读出数据
    • 否则需要对比 key 完整的 hash 值，如果匹配，则读出数据
    • 如果都没有找到，那么直接去溢出桶中去寻找。

存放数据

  • 通过 key 的 hash 值的后面 B 位确定在哪个桶中
  • 遍历当前桶，通过 key 的 tophash 和 hash，防止 key 重复，然后找到第一个可以插入的位置
    • 如果当前桶元素已满，那么就会通过 overflow 链接创建一个新的桶来保存数据。

扩容机制

go 的扩容机制分为两种：

  • 等量扩容：如果 map 的溢出桶的数量过多，导致性能下降，说明 kv 分布不均匀，此时触发等量扩容，hash 桶的数量不变，但是会重新分配 kv 的位置，减少桶的数量，增加 kv 的密度。
  • 增量扩容：如果负载因子超标（count / 2 ** B），那么说明 kv 数量过多，桶的数量不够，那么就让 bucket 数量翻倍，让所有的 kv 对重新分配到新的桶数组中，目的是为了减少 kv 的密度，降低每个桶的 kv 数量，优化查询时间。

扩容前置

  1. 在我们的hmap结构中有一个oldbuckets吗，扩容刚发生时，会先将老数据存到这个里面。
  2. 每次对map进行删改操作时，会触发从oldbucket中迁移到bucket的操作【非一次性，分多次】
  3. 在扩容没有完全迁移完成之前，每次get或者put遍历数据时，都会先遍历oldbuckets，然后再遍历buckets。

等量扩容

img

由于map中不断的put和delete key，桶中可能会出现很多断断续续的空位，这些空位会导致连接的bmap溢出桶很长，导致扫描时间边长。这种扩容实际上是一种整理，把后置位的数据整理到前面。这种情况下，元素会发生重排，但不会换桶。

增量扩容

img

避免 hash 冲突的方法

  • 拉链法：将多个命中到同一个桶的键值对，按照插入顺序依次存放在桶中。
  • 开放寻址法：对于命中到同一个桶的多个键值对，采取向后寻找，知道找到空的桶再将值放入其中
方法 优点
拉链法 简单常用，容易实现，无需事先分配空间
开放寻址法 无需额外的内存来存放指针，存放的元素在内存上基本连续

显然，Go采取的是拉链法，桶数组中的每一个桶，严格来说应该是一个链表结构的桶数组，它通过overflow指针链接上了下一个溢出桶，使得多个键值对能存放在同一个桶中。若当前桶八个槽位都满了，就开辟一个新的溢出桶，放置在溢出桶里面。

杂谈

为什么说 map 不是并发安全的

  • 数据竞争：如一个 goroutine 扩容时，另一个 goroutine 正在读写，可能破坏内部结构。
  • 内存损坏：并发修改桶的 tophash 或键值对区域可能导致内存越界或数据错乱。

下面有一个扩容竞争过程：

  1. g1 查询一个 k1
    1. 计算出hash，确定桶的系数，但是还未查询到 buckets
  2. g2 添加一个 k2，触发扩容条件
    1. 数据迁移到 oldbuckets，buckets 为新
  3. g1 进行查询，会出现查询失败。