哈希表解决碰撞的常见方法及其原理如下：
1. 链地址法（Chaining）
- 原理：每个哈希表的桶（bucket）维护一个链表（或动态数组），当多个键哈希到同一索引时，它们被依次存储在该链表中。
- 操作：
- 插入：计算哈希值，找到对应桶，将键添加到链表尾部。
- 查找：找到桶后，遍历链表匹配键。
- 删除：遍历链表找到键并移除。
- 优点：实现简单，适用于高碰撞率场景。
- 缺点：链表过长时查找效率退化为O(n)；需额外空间存链表指针。
- 典型应用：Java
HashMap、Python 字典。
2. 开放寻址法（Open Addressing）
- 原理：冲突时按特定规则探测下一个可用槽位，而非链表。
- 常用方法：
- 线性探测：从原索引开始顺序查找空位（易产生聚集）。
- 二次探测：索引递增步长为平方数（
i + i²），分散分布。 - 双重哈希：使用两个哈希函数，冲突时用第二个函数计算新索引。
- 操作：
- 插入：若槽位占用且非删除标记，继续探测直至找到空位。
- 查找：类似插入过程，需区分有效键、空位和删除标记。
- 删除：标记槽位为已删除（避免干扰后续探测）。
- 优点：内存利用率高，无额外指针开销。
- 缺点：负载因子需严格控制（如≤0.67）；删除复杂度高。
- 典型应用：C++
unordered_map（部分实现）。
3. 再哈希法（Rehashing）
- 原理：冲突时使用另一个哈希函数重新计算索引，多次尝试直至成功。
- 特点：
- 需预先设计多个哈希函数。
- 适用于哈希函数质量不高的场景。
- 缺点：计算成本较高，较少单独使用，常与开放寻址法结合。
4. 分离链法（Separate Chaining with Hash Tables）
- 原理：每个桶是一个小型哈希表，进一步分散碰撞。
- 优点：结合链表和哈希表优势，减少链表长度。
- 缺点：空间复杂度略高，实现稍复杂。
5. 动态扩容（Resize Mechanism）
- 原理：当元素数量超过负载因子（如0.75），创建更大数组并重新哈希所有键。
- 作用：降低负载因子，预防碰撞加剧。
- 实现：通常为2倍扩容，保证摊还时间复杂度。
6. 其他优化策略
- 布隆过滤器（Bloom Filter）：用于快速过滤不存在的键，减少无效查找。
- Robin Hood 哈希：通过平衡键值长度分布，减少长链现象。
方法对比与选择
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 链地址法 | O(1)（均摊）、O(n)（最坏） | O(n) | 内存充足，允许适度碰撞 |
| 开放寻址法 | O(1)（低负载）、O(n)（高负载） | O(n) | 内存敏感，需严格控制负载因子 |
| 分离链法 | O(1)（均摊） | O(n) | 高频碰撞场景，需平衡性能与空间 |
| 动态扩容 | O(n)（扩容时） | O(n) | 自动调节负载，长期稳定数据集 |
总结
- 链地址法和开放寻址法是最主流的解决方案，前者侧重易实现，后者追求内存效率。
- 再哈希法和分离链法适用于特定需求（如多哈希函数或子哈希优化）。
- 动态扩容是辅助机制，确保哈希表长期高效运行。
- 选择依据：根据应用场景对时间、空间的权衡，以及哈希函数质量等因素综合决定。