map#

map又称字典，是golang中常用的数据结构，主要功能就是用来存储kv对这样的数据，其会基于key维度实现存储数据的去重，读，写，删的时间复杂度都是O(1)

一、初始化#

golang中的map的初始化有以下几种形式：

1.使用make进行初始化：

1// 通过make关键词进行初始化，但是这个mp1的预分配的容量为0
2mp1 := make(map[int]int)
3// 当然make也可以指定map预分配的容量
4mp2 := make(map[int]int,2)

2.初始化+赋值：

1mp3 := map[int]int{
2    1:1,
3    2:2,
4}

二、map的基本操作和常识#

2.1 map的读#

map的读分为两种形式

1、直接读，如果key不存在，就会返回对应value类型的零值

1mp := map[int]int{
2    1:1,
3    2:2,
4}
5
6v1 := mp[1]
7// v1 = 1
8
9v2 := mp[2]
10// v2 = 2
11
12v3 := mp[3]
13// v3 = 0

2、读的同时多返回一个bool类型的值，来表示这个key是否存在

1mp := map[int]int{
2    1:1,
3    2:2,
4}
5
6v1,ok := mp[1]
7// v1 = 1, ok = true
8
9v2,ok := mp[2]
10// v2 = 2, ok = true
11
12v3,ok := mp[3]
13// v3 = 0, ok = false

2.2 map的写#

map的写非常简单

1mp := make(map[int]int)
2
3mp[1] = 1
4// 添加<1,1>的kv对
5
6mp[1] = 2
7// 由于key=1存在，所以value会被2覆盖,最后<1,1> -> <1,2>

需要注意的是，如果map没有进行初始化，直接写是发生panic的

2.3 map的删除#

1delete(mp,1)

执行delete方法时，如果key存在，就会从map中对应的key-value删除；反之如果不存在或map未初始化，则方法直接结束，不会产生显式提示

2.4 map的遍历#

遍历有两种形式：

1for k,v := range mp{
2  // ...
3}

k,v 依次承接 map 中的 key-value 对

1for k := range mp{
2  // ...
3}

k 依次承接 map 中的 key，不关注 val 的取值

需要注意的是，像c++的map，遍历时是按照key的大小依次遍历，但是golang的map遍历是乱序的，所以前后两次的遍历的顺序可能存在差异

2.5 map不是并发安全的#

golang的map 不是并发安全的数据结构，倘若存在并发读写行为，会抛出 fatal error

具体规则是：

• 并发读没有问题

• 并发读写中的写，包含写入、更新、删除等操作

• 读的时候发现其他 goroutine 在并发写，抛出 fatal error

• 写的时候发现其他 goroutine 在并发写，抛出 fatal error

此处并发读写会引发 fatal error，是一种比 panic 更严重的错误，无法使用 recover 操作捕获.

三、核心原理#

map 又称为 hash map，在算法上基于 hash 实现 key 的映射和寻址；在数据结构上基于桶数组实现 key-value 对的存储.

以一组 key-value 对写入 map 的流程为例进行简述：

1、通过哈希函数得到对应的key的hash值

2、hash值对桶数组的长度进行取模，确定其所属的桶

3、在桶中插入key-value对

基于hash 的性质，保证了相同的 key 必然产生相同的 hash 值，因此能映射到相同的桶中，通过桶内遍历的方式锁定对应的 key-value 对

因此，只要在宏观流程上，控制每个桶中 key-value 对的数量，就能保证 map 的几项操作都限制为常数级别的时间复杂度

3.1 hash冲突#

由于输入域（key）无穷大，输出域（hash值）有限，所以必然存在不同的key映射到相同的hash值的情况，这就叫hash冲突

如何解决hash冲突？

最经典的解决手段分为两种：拉链法和开放寻址法

拉链法：

将命中同一个桶的元素通过链表的形式进行链接，因此很便于动态扩展

开放寻址法：

开放寻址法中，在插入新条目时，会基于一定的探测策略持续寻找，直到找到一个可用于存放数据的空位为止

3.2 桶数组#

map 中，会通过长度为 2 的整数次幂的桶数组进行 key-value 对的存储

• 每个桶固定可以存放8个key-value对

• 如果超过8个key-value对打到桶数组的同一个索引当中，此时会通过创建桶链表的方式来化解这个问题

在 map 解决 hash /分桶 冲突问题时，实际上结合了拉链法和开放寻址法两种思路. 以 map 的插入写流程为例，进行思路阐述：

1、桶数组中的每个桶，严格意义上是一个单向桶链表，以桶为节点进行串联；

2、每个桶固定可以存放 8 个 key-value 对；

3、当 key 命中一个桶时，首先根据开放寻址法，在桶的 8 个位置中寻找空位进行插入；

4、倘若桶的 8 个位置都已被占满，则基于桶的溢出桶指针，找到下一个桶，重复第3步；

5、倘若遍历到链表尾部，仍未找到空位，则基于拉链法，在桶链表尾部续接新桶，并插入 key-value 对.

3.3 扩容#

如果 map 的桶数组长度固定不变，那么随着 key-value 对数量的增长，当一个桶下挂载的 key-value 达到一定的量级，此时操作的时间复杂度会趋于线性

因此在实现上，map 桶数组的长度会随着 key-value 对数量的变化而实时调整，以保证每个桶内的 key-value 对数量始终控制在常量级别，满足各项操作为 O(1) 时间复杂度的要求

扩容分为增量扩容和等量扩容：

增量扩容：

表现：扩容后，桶数组的长度为原长度的2倍

目的：降低每个桶中kv对的数量，优化map操作的时间复杂度

等量扩容：

表现：扩容后，桶数组的长度和之前保持一致；但是溢出桶的数量会下降

目的：提高桶主体结构的数据填充率，减少溢出桶数量，避免发生内存泄露

何时扩容？#

1、只有 map 的写流程可能开启扩容模式

2、写 map 新插入 key-value 对之前，会发起是否需要扩容的逻辑判断

• 当桶内的kv总数/桶数组长度 > 6.5时发生增量扩容，桶数组长度增长为原值的两倍

• 当同辈的溢出桶数量 >= 2^B(桶数组长度)，发生等量扩容，桶数组长度保持为原值

• 采用渐进扩容的方式，当桶被实际操作到时，由使用者负责完成数据迁移，避免因为一次性的全量数据迁移引发性能抖动

核心数据结构的变化#

在扩容开始的一瞬间，hmap 结构体发生了“新老更替”：

• oldbuckets： 存放扩容前的老桶数组。

• buckets： 存放新申请的、容量翻倍（或相等）的新桶数组。

• nevacuate： 搬迁进度计数器，记录当前搬迁到了第几个桶。

扩容的核心过程#

无论是哪种扩容，其初始化阶段是相似的：

1. 创建新桶（New Buckets）：

   1. 增量扩容： 创建两倍于原长度的新桶数组（B -> B+1）。
   2. 等量扩容： 创建与原长度相同的新桶数组。

2. 标记状态： 将原有的 buckets 挂载到 oldbuckets 指针下，并重置搬迁进度 nevacuate（表示下一个待搬迁的桶索引）。

3. 分配标志位： 标记 map 处于扩容状态

增量扩容的具体搬迁逻辑#

对于旧桶中的每一个 Key，需要重新确定它在新数组中的位置：

• 计算掩码变化： 假设原桶数组长度为 2^B。扩容后变为 2^(B+1)。此时，决定 Key 在哪个桶的“掩码位”向左多出了一位（bit）。
• 分流（Splitting）：
  • 如果该位（bit）是 0：Key 留在 X 区域（索引号不变）。
  • 如果该位（bit）是 1：Key 移动到 Y 区域（新索引 = 原索引 + 旧数组长度）。
• 物理搬迁： 将 Key-Value 对从 oldbuckets 拷贝到 buckets 的指定位置，并更新 tophash（高位哈希值）。

等量扩容的具体搬迁逻辑#

• 索引不变： 所有的 Key 在新桶中的索引号与旧桶完全一致。

• 紧凑排列： 搬迁时会跳过那些被标记为 emptyRest 或 emptyOne 的已删除项。

• 效果： 就像电脑磁盘碎片整理一样，把原本稀疏分布在多个溢出桶里的数据重新紧凑地排列在主桶中，减少由于溢出桶过多导致的查找性能下降。

渐进式搬迁#

为了避免扩容时的 STW（Stop The World） 风险，Go 采用了渐进式设计：

• 触发点： 每次 mapassign（写）或 mapdelete（删）。
• 搬迁量：
  • 1. 当前操作桶： 搬迁当前操作所落入的那个旧桶。
  • 2. 顺序搬迁： 顺带搬迁 nevacuate 指向的那个桶，并递增计数器。
• 状态维护： 每一组搬迁完后，旧桶的 tophash 会被标记为 evacuatedX 或 evacuatedY

什么是 tophash？

在 Go map 的底层结构中，每个桶（bmap）可以存储 8 个 key-value 对。为了避免每次都进行昂贵的整个 Key 的相等性比较（尤其是大对象 Key），Go 为每个 Key 额外存储了一个 8 位（1 字节）的哈希高位值，这就是 tophash。

它的作用：

• 快速预检： 当你查找一个 Key 时，Go 先计算该 Key 的哈希值，取其高 8 位。

• 性能加速： 先在桶里对比这 1 字节的 tophash。如果 tophash 都不匹配，说明这个槽位（slot）肯定不是我们要找的 Key，直接跳过。只有当 tophash 相等时，才会去比较真正的 Key 内容。

• 状态记录： 这是重点——当 tophash 的值小于某些预定义的常量（例如 1-5）时，它不再代表哈希高位，而是代表该槽位的状态（如空闲、已删除、已搬迁）。

  Go 源码中定义了一个界限：凡是小于 5 的值，都预留给“状态标记”；凡是大于等于 5 的值，才是真正的“哈希高位”。

  在计算 tophash 时，Go 会强制执行一个逻辑：如果计算出来的哈希高 8 位恰好小于 5，它会手动给它加一个偏移量，使其变成大于等于 5 的值。

evacuatedX (值为 2)： 表示该槽位的数据已经搬迁到了新桶数组的 X 区域（即新数组的前半部分，索引号与旧桶一致）。

evacuatedY (值为 3)： 表示该槽位的数据已经搬迁到了新桶数组的 Y 区域（即新数组的后半部分，索引号 = 原索引 + 旧数组长度）。

evacuatedEmpty (值为 4)： 表示该槽位原本就是空的，搬迁时也作为空处理