Map 那些事儿

1. map 的基本结构

Go 的 map 是一种哈希表，其核心思想是通过哈希函数将键映射到某个位置（桶）以存储对应的值。它主要包含以下关键部分：

•桶（bucket）：存储键值对的容器，map 中的元素被分散到多个桶中。

•哈希函数：用于计算键的哈希值，从而确定键应存放在哪个桶中。

•键值对存储：每个桶可以存储多个键值对，并通过链表或其他结构处理哈希冲突。

2. map 的实现细节

(1) hmap 结构

在 Go 源码中，map 是通过一个名为 hmap 的结构体实现的（定义在 runtime/map.go 中）。主要字段包括：

• count: map 中存储的键值对总数。

• buckets: 指向桶的指针，每个桶存储多个键值对。

• hash0: 用于防止哈希冲突的种子（随机数），在程序启动时初始化。

• B: 桶的数量为 2^B，B 是桶数的对数。

(2) 桶的结构

每个桶是一个固定大小的数组，存储若干个键值对。此外，每个桶还有一个位图，用于快速定位某个槽位是否已被占用。

• 键值对数组：存储键和值。

• 溢出桶：当一个桶满时，会使用额外的溢出桶存储新插入的键值对。

(3) 哈希冲突处理

当两个键通过哈希函数映射到同一个桶时，就会发生哈希冲突。Go 使用以下方法处理冲突：

• 链式处理：如果一个桶已满，则创建溢出桶。

• 线性探测：在桶中通过位图快速找到空闲槽位。

3. 操作原理

(1) 插入操作

1. 计算键的哈希值。

2. 根据哈希值定位到一个桶。

3. 在桶中查找空闲槽位，存储键值对。

4. 如果桶满，则分配溢出桶并存储新数据。

(2) 查找操作

1. 计算键的哈希值。

2. 定位到桶后，在桶内逐一检查键是否存在。

3. 如果未找到，继续在溢出桶中查找。

(3) 删除操作

1. 定位到桶。

2. 在桶中找到对应的键值对，将其标记为空。

4. 动态扩容

当 map 的负载因子（存储的键值对数与桶数的比值）超过某个阈值时，map 会进行扩容（rehash）：

1. 增加桶的数量（桶数翻倍）。

2. 将现有键值对重新分配到新的桶中。

3. 新的桶结构更加稀疏，减少冲突。

扩容是一项耗时操作，因此频繁的插入操作可能会导致性能抖动。

Map迁移执行过程

(1) 扩容时分配新桶

• 新的桶数量为旧桶数量的两倍。

• 新桶的内存被初始化，但数据尚未迁移。

(2) 增量迁移

迁移操作是增量完成的，而非一次性迁移：

• 当 map 被访问（插入、查找或删除）时，Go 运行时会在后台逐步迁移旧桶中的数据到新桶。

• 每次访问会触发部分桶的迁移。

(3) 数据重新分布

迁移过程中：

1. 计算新哈希值：对每个键重新计算哈希值。

2. 分配到新桶：新哈希值根据新的桶数决定键值对的位置。

哈希值的高位用来区分数据是留在旧桶还是移动到新桶：

• 如果 (hash >> B) & 1 == 0，则数据保留在旧桶。

• 如果 (hash >> B) & 1 == 1，则数据迁移到新桶。