1. 引言
map 是 Go 语言中使用频率极高的数据结构，它提供了快速的键值对存取能力。虽然 map 的使用非常简单，但其底层的实现却是一个精心设计的哈希表，它需要高效地处理哈希计算、数据存储、扩容以及最关键的——哈希冲突。
本文将解剖 map 的底层数据结构，详细阐述其查找、赋值和扩容过程，特别是它是如何解决哈希冲突的。
2. map 的核心数据结构
Go map 的运行时表示是 runtime.hmap 结构体，其关键字段如下：
// src/runtime/map.go
type hmap struct {count int // map 中元素的个数，即 len(m)flags uint8B uint8 // buckets 的对数，buckets 数量 = 2^Bnoverflow uint16 // 溢出桶的大致数量hash0 uint32 // 哈希种子buckets unsafe.Pointer // 指向 bucket 数组的指针，大小为 2^Boldbuckets unsafe.Pointer // 在扩容时，指向旧的 bucket 数组nevacuate uintptr // 扩容进度计数器// ...
}
map 的核心是一个 bucket 数组。每个 bucket 是一个 runtime.bmap 结构：
// 一个 bucket 最多可以存放 8 个键值对
const bucketCnt = 8type bmap struct {tophash [bucketCnt]uint8 // 存储每个 key 哈希值的高 8 位// keys and values follow
}
B: 决定了map有多少个 bucket，总数是 2B。buckets: 是一个指针，指向一个连续的 bucket 数组。bmap(bucket):tophash: 这是一个巧妙的优化。它存储了每个 key 的哈希值的高 8 位 (top hash)。在查找 key 时，可以先快速比较这 8 位，如果tophash都不匹配，就无需再比较完整的 key，从而加速查找。键和值:
bmap结构体之后，紧跟着存储了 8 个 key 和 8 个 value。它们在内存上是连续的。
溢出桶 (Overflow Bucket): 如果一个 bucket 的 8 个槽位都满了，
map会通过一个指针将这个 bucket 与一个溢出桶链接起来，形成一个链表。
3. map 的工作流程
a) 写入/赋值 (map[key] = value)
哈希计算: 使用哈希函数计算
key的哈希值hash。定位 Bucket: 使用
hash的低 B 位来决定这个key应该落在哪个 bucket 中。例如，bucketIndex = hash & (2^B - 1)。定位槽位:
计算
hash的高 8 位tophash。遍历目标 bucket 的
tophash数组，看是否存在相同的tophash。如果
tophash相同，再完整地比较key是否相同。如果
key已存在，则更新对应的value。如果
key不存在，就在 bucket 中找一个空槽位，存入tophash,key和value。
处理冲突与溢出: 如果当前 bucket 的 8 个槽位都满了，
map会创建一个新的溢出桶，并让当前 bucket 指向它。新的键值对将被存入这个溢出桶。
b) 查找 (value, ok := map[key])
查找过程与写入类似。通过哈希值定位到 bucket，然后先比较 tophash，再比较完整的 key。会依次遍历 bucket 和其所有链接的溢出桶，直到找到 key 或者遍历完所有溢出桶。
c) 扩容 (Grow)
当以下任一条件满足时，map 会触发扩容：
负载因子超限:
map中元素的数量count/ bucket 数量2^B> 6.5。溢出桶过多:
map的溢出桶数量过多时（当 B < 15 时，noverflow >= 2^B），也会触发扩容，这主要是为了解决因大量删除操作导致的内存空洞问题。
扩容方式:
等量扩容: 如果是因溢出桶过多触发，
map会创建一个与原 bucket 数组大小相同的新数组，然后将数据重新排列（rehash），目的是消除内存碎片。翻倍扩容: 如果是因负载因子超限触发，
map会创建一个两倍大的 bucket 数组（B会加 1）。
渐进式扩容 (Incremental Evacuation): 为了避免因扩容导致长时间的 STW，Go map 的扩容是渐进式的。
扩容时,
map不会一次性将所有数据从oldbuckets搬到buckets。而是每当对
map进行一次写入或删除操作时，会顺便“搬运”一到两个 bucket 的数据。查询操作可能会同时在
oldbuckets和buckets中进行。整个搬运过程会分散到多次操作中，直到
oldbuckets中的数据全部迁移完毕。
