主题
第五章 哈希表、集合与并查集
1. 从“比较”到“映射”：哈希表的核心跳跃
前面几章的高效结构，大多依赖次序或层次。例如数组用下标定位，BST 用大小关系缩小搜索范围，堆用父子大小规律维护最值。哈希表走的是另一条路：不通过比较逐步逼近目标，而是先把关键字映射到某个桶位置，再在局部处理冲突。
这是一种非常重要的思想跃迁。它意味着：
- 结构不再强调整体有序。
- 查找速度不再主要来自“比较次数减少”，而来自“映射直接命中”。
- 性能瓶颈从比较路径转向哈希函数和冲突分布。
2. 哈希表的组成
一个典型哈希表通常包含三部分：
- 桶数组。
- 哈希函数。
- 冲突解决策略。
若不同关键字被映射到同一个桶，就发生冲突。冲突不是异常，而是哈希表设计中必须接受并处理的常态。