袋鼠知识

主题

第六章 散列表、集合与并查集 ​

📖 ⏱️ 预计阅读时长

1. 散列表的基本思想 ​

前面几章中的许多结构都强调有序关系或层次关系，而散列表提供了另一种思路：不通过比较来逐步缩小范围，而是通过映射直接定位。散列表（哈希表）通过哈希函数把关键字映射到某个地址，从而希望在平均意义上快速完成查找、插入和删除。

例如，把学生学号通过某种规则映射到数组下标，就可以较快定位对应记录。散列表的核心不是“排序”，而是“映射”。

2. 哈希函数的基本要求 ​

一个好的哈希函数通常应尽量满足以下要求：

  1. 计算过程简单，不能让映射本身成本过高。
  2. 映射结果分布尽量均匀，避免大量关键字集中到少数桶中。
  3. 对于输入中常见模式不应过分敏感，否则容易形成系统性冲突。

需要强调的是，哈希函数的目标不是让不同关键字绝对不冲突，因为这在多数场景中做不到，而是尽量降低冲突概率。

这也说明了一个根本事实：哈希表之所以快，不是因为它“没有冲突”，而是因为它把冲突控制在较低水平，并让大多数操作只需很短路径即可完成。理解这一点，有助于正确看待哈希表的平均复杂度。

3. 哈希冲突与解决方法 ​

不同关键字可能映射到同一地址，这种现象称为哈希冲突。冲突无法完全避免，只能尽量减少并妥善处理。

3.1 拉链法 ​

把映射到同一位置的元素挂到同一个链表或桶中。其优点是实现直观，扩容与删除较方便。

3.2 开放定址法 ​

若某个位置已被占用，就按某种规则继续探查下一个位置，如线性探测、二次探测、双重散列等。

这两种方法没有绝对优劣，选择时需要综合考虑空间布局、删除策略、缓存命中和实现复杂度。

从工程角度看，拉链法更容易处理删除和扩容，开放定址法则在连续存储场景中常具有较好的缓存局部性。不同语言运行库和数据库系统会根据使用场景作出不同选择。

3.3 为什么哈希表常用于“查存在” ​

很多程序并不需要哈希表维持有序性，只需要快速回答“这个元素是否已经出现过”或“这个键对应什么值”。在这种场景下，哈希表往往比树结构更直接。这也是集合、词频统计、缓存表和去重逻辑大量使用哈希表的原因。

4. 负载因子 ​

负载因子通常表示为：

负载因子 = 已存元素数 / 散列表容量

负载因子过高会显著增加冲突概率，进而降低查找效率。因此，工程系统通常会在负载因子达到阈值时进行扩容和再散列。

理解负载因子的意义非常重要。哈希表之所以平均快，并不是因为它“天然无冲突”，而是因为系统通过容量管理把冲突控制在可接受范围内。

5. 散列表复杂度 ​

操作平均复杂度最坏复杂度
查找O(1)O(n)
插入O(1)O(n)
删除O(1)O(n)

这里必须特别注意：哈希表的“快”主要是平均意义上的快，并不是任何情况下都严格常数时间。

6. 集合结构与映射思维 ​

在很多编程场景中，人们使用哈希表的目的并不是“保存复杂记录”，而只是为了快速判断某元素是否存在，或快速建立“键 -> 值”的关联。例如：

  1. 判断某个单词是否出现过。
  2. 统计字符出现次数。
  3. 根据用户编号快速定位用户信息。
  4. 用键值对管理缓存对象。

因此，从应用角度看，哈希表最典型的抽象用途就是集合与映射。

7. 并查集 ​

并查集（Disjoint Set Union, DSU）用于维护若干互不相交集合，支持两个核心操作：

  1. Find：查找某元素所属集合代表。
  2. Union：合并两个集合。

并查集特别适合处理：

  1. 连通分量判定。
  2. 网络连通问题。
  3. 最小生成树算法中的集合合并。

采用路径压缩和按秩合并优化后，并查集的均摊效率非常高，在实际应用中几乎可以视为接近常数时间。

路径压缩之所以有效，是因为它会在查找代表节点的过程中，顺手把沿途节点直接挂到更高层的代表节点之下，从而使后续查找路径显著变短。按秩合并则尽量避免把高树挂到低树下面，以免树高持续增长。两者结合，才能让并查集长期保持高效。

上图表示两个集合的父子归属关系。并查集的本质不是保存一般树结构，而是用树来表达“属于同一个集合”的代表关系。

8. 散列表与并查集的区别 ​

这两种结构虽然都常用于“快速处理关系”，但解决的问题并不相同：

  1. 散列表解决的是“如何快速定位某个键”。
  2. 并查集解决的是“两个元素是否属于同一集合，以及如何高效合并集合”。

一个强调映射定位，一个强调集合归属，这一点必须区分清楚。

9. 工程实践中的典型场景 ​

9.1 哈希表场景 ​

  1. 登录态缓存。
  2. 用户 ID 到用户对象的映射。
  3. 去重和词频统计。
  4. 内存键值缓存系统。

9.2 并查集场景 ​

  1. 社交网络中的群组归并。
  2. 网络节点连通判定。
  3. 图算法中的边合并处理。

这些应用说明，数据结构并不是教材中的抽象产物，而是系统工程中的高频工具。

10. 本章小结 ​

散列表代表了一种与比较型结构完全不同的思路，即通过函数映射来获得平均意义上的快速访问；并查集则针对集合合并与连通判定提供了极高效率的专门方案。学习本章时，应特别重视“平均复杂度”“冲突处理”“负载因子”“路径压缩”等关键词，因为它们直接决定了这些结构能否真正发挥性能优势。