主题
第五章 哈希表、集合与并查集
1. 从“比较”到“映射”：哈希表的核心跳跃
前面几章的高效结构，大多依赖次序或层次。例如数组用下标定位，BST 用大小关系缩小搜索范围，堆用父子大小规律维护最值。哈希表走的是另一条路：不通过比较逐步逼近目标，而是先把关键字映射到某个桶位置，再在局部处理冲突。
这是一种非常重要的思想跃迁。它意味着：
- 结构不再强调整体有序。
- 查找速度不再主要来自“比较次数减少”，而来自“映射直接命中”。
- 性能瓶颈从比较路径转向哈希函数和冲突分布。
2. 哈希表的组成
一个典型哈希表通常包含三部分：
- 桶数组。
- 哈希函数。
- 冲突解决策略。
若不同关键字被映射到同一个桶，就发生冲突。冲突不是异常，而是哈希表设计中必须接受并处理的常态。
3. 哈希函数应该追求什么
理想哈希函数不是“永不冲突”，那在大多数真实场景里做不到。更现实的目标是：
- 计算成本低。
- 对输入分布足够均匀。
- 不容易被常见模式击穿。
如果哈希函数把大量键集中到少数桶里，即使表面上用了哈希表，实际性能也会退化成链表或线性探测的糟糕状态。
4. 冲突解决：拉链法与开放定址法
4.1 拉链法
每个桶挂一条链表或切片，冲突元素放进同一个桶的局部容器中。
优点：
- 实现直观。
- 删除方便。
- 装载因子高时表现较稳。
4.2 开放定址法
元素直接放在桶数组中，发生冲突时按某种探测规则寻找下一个空位。常见方式有线性探测、二次探测、双重哈希。
优点是局部性更好，缺点是删除和高负载场景更麻烦。
5. Go 里为什么还要手写哈希表
Go 自带 map，工程里当然优先用标准实现。但教学上仍然建议手写一次，因为你需要真正理解：
- 为什么查询平均是
O(1)，却不是绝对O(1)。 - 为什么扩容要重哈希。
- 为什么装载因子影响性能。
- 为什么哈希表不天然保序。
6. 用 Go 实现一个简单的链式哈希集合
下面写一个整数集合，只关心元素是否存在。
go
package hashset
type node struct {
key int
next *node
}
type HashSet struct {
buckets []*node
size int
}
func NewHashSet(capacity int) *HashSet {
if capacity < 8 {
capacity = 8
}
return &HashSet{
buckets: make([]*node, capacity),
}
}
func (s *HashSet) hash(key int) int {
if key < 0 {
key = -key
}
return key % len(s.buckets)
}
func (s *HashSet) Contains(key int) bool {
idx := s.hash(key)
for cur := s.buckets[idx]; cur != nil; cur = cur.next {
if cur.key == key {
return true
}
}
return false
}
func (s *HashSet) Add(key int) {
if float64(s.size+1)/float64(len(s.buckets)) > 0.75 {
s.resize()
}
idx := s.hash(key)
for cur := s.buckets[idx]; cur != nil; cur = cur.next {
if cur.key == key {
return
}
}
s.buckets[idx] = &node{
key: key,
next: s.buckets[idx],
}
s.size++
}
func (s *HashSet) Remove(key int) bool {
idx := s.hash(key)
var prev *node
for cur := s.buckets[idx]; cur != nil; cur = cur.next {
if cur.key == key {
if prev == nil {
s.buckets[idx] = cur.next
} else {
prev.next = cur.next
}
s.size--
return true
}
prev = cur
}
return false
}
func (s *HashSet) resize() {
old := s.buckets
s.buckets = make([]*node, len(old)*2)
s.size = 0
for _, head := range old {
for cur := head; cur != nil; cur = cur.next {
s.Add(cur.key)
}
}
}这个实现足够说明哈希表的几个关键机制：
- 桶数组并不是元素本身，而是入口。
- 冲突元素被局部串起来。
- 扩容不是简单复制，而是要重新按新桶数计算位置。
7. 集合抽象：不关心顺序，只关心成员关系
集合结构的核心不是遍历顺序，而是：
- 元素是否存在。
- 元素是否去重。
- 两个集合是否并、交、差。
这就是为什么哈希表很适合做集合：它不必维护整体顺序，只需让“存在性判断”尽量快。
8. 并查集：维护连通分量的专用结构
并查集（Union-Find / DSU, Disjoint Set Union）解决的是另一类问题：一批元素被划分到若干不相交集合中，我们需要高效支持：
- 查询两个元素是否属于同一集合。
- 把两个集合合并。
典型场景：
- 无向图连通性。
- Kruskal 最小生成树。
- 动态社交群组归并。
- 岛屿问题、等价关系归类。
9. 并查集的核心思想
并查集通常用一棵“父指针树”表示每个集合，每个元素指向父节点，根节点代表该集合。
其中 Find(x) 用于找到元素所属集合的代表元，Union(x, y) 用于把两个代表元所在集合合并。
10. 路径压缩与按秩合并
若不加优化，父指针树也可能退化。并查集高效的关键在于两条优化：
- 路径压缩：查找根时，让沿途节点直接挂到根上。
- 按秩合并：尽量把矮树挂到高树下面。
这会把均摊复杂度压得非常低，低到在工程中几乎可视作常数级。
11. Go 实现并查集
go
package dsu
type DSU struct {
parent []int
rank []int
}
func NewDSU(n int) *DSU {
parent := make([]int, n)
rank := make([]int, n)
for i := range parent {
parent[i] = i
}
return &DSU{
parent: parent,
rank: rank,
}
}
func (d *DSU) Find(x int) int {
if d.parent[x] != x {
d.parent[x] = d.Find(d.parent[x])
}
return d.parent[x]
}
func (d *DSU) Union(a, b int) bool {
ra := d.Find(a)
rb := d.Find(b)
if ra == rb {
return false
}
if d.rank[ra] < d.rank[rb] {
ra, rb = rb, ra
}
d.parent[rb] = ra
if d.rank[ra] == d.rank[rb] {
d.rank[ra]++
}
return true
}
func (d *DSU) Connected(a, b int) bool {
return d.Find(a) == d.Find(b)
}这段代码体现了并查集的本质：它不是通用容器，而是为“集合合并 + 连通性查询”定制的结构。
12. 哈希表与并查集的关系与区别
它们都经常被归到“集合”相关结构里，但关注点完全不同：
| 结构 | 关心什么 | 核心操作 |
|---|---|---|
| 哈希表 / 哈希集合 | 某个元素是否存在 | 插入、删除、查找 |
| 并查集 | 两个元素是否属于同一组 | Find、Union |
哈希表不擅长做动态连通性，并查集也不适合做任意键值映射。不要因为它们都叫“集合”就混为一谈。
13. 本章小结
这一章真正要掌握的是两条不同路线：
- 哈希表通过映射直接定位，把查找问题从“比较路径”改成“桶内冲突”问题。
- 并查集通过父指针树维护等价类与连通分量，把集合归并问题做到了极高效率。
下一章进入图结构后，并查集会和 BFS、DFS 一起成为处理图问题的核心工具箱。
14. 继续深入
基础章里的哈希表主要解决“它为什么平均很快”这个问题。进阶时还需要继续理解：
- 开放定址为什么会带来聚集问题。
- 扩容为什么不能只是简单复制。
- 工业级哈希表如何在局部性、删除、并发和扩容停顿之间做权衡。
- 一致性哈希为什么属于“分布式场景中的哈希结构延伸”。
进阶内容见：哈希进阶：开放定址、扩容策略与工程实现