哈希冲突

解决哈希冲突的方法

Go 的 map 主要采用 链地址法（Separate Chaining） 来解决哈希冲突。

与传统的单向链表（每个节点只存一个元素）不同，Go 对此进行了内存和性能上的优化：

1. 桶（Bucket）机制：哈希表的每个节点是一个桶（即底层结构 bmap）。
2. 批量存储：每个桶内部可以连续存储最多 8 个键值对（K-V）。
3. 桶内遍历：当发生哈希冲突，多个 key 被映射到同一个桶时，Go 会遍历这 8 个槽位，寻找空闲位置插入。这种设计能更好地利用 CPU 缓存（局部性原理），减少内存分配的开销。

溢出桶（Overflow Bucket）

作用： 当一个常规桶（Normal Bucket）的 8 个槽位都已经存满，此时若还有新的 key 发生哈希冲突并映射到该桶，就需要额外的空间来容纳这些“溢出”的元素。溢出桶就是用来解决单个桶容量上限问题的。

连接方式：

1. 链表结构：在编译期生成的 bmap 底层结构中，末尾会包含一个 overflow 指针。
2. 动态挂载：当常规桶满时，Go 运行时会分配一个新的溢出桶，并将当前常规桶（或上一个溢出桶）的 overflow 指针指向这个新分配的溢出桶。
3. 形成链条：如果溢出桶也满了，就会继续追加新的溢出桶，最终形成一个类似 常规桶 -> 溢出桶1 -> 溢出桶2 -> ... 的单向链表结构。

补充：如果溢出桶的数量过多，会导致链表过长，查找性能退化为 $O(N)$。为了防止性能严重下降，此时 Go 的 map 会触发等量扩容（SameSizeGrow），通过重新整理内存、紧凑数据来减少溢出桶的数量，从而恢复访问效率。