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，则数据迁移到新桶。