解决hash冲突方式有什么
Hash 冲突是指不同的键通过哈希函数映射到同一位置，解决方式主要有 开放寻址法、拉链法（链表法）、再哈希法 和 建立公共溢出区。这些方法通过调整存储或映射策略，确保所有键都能正确存取。
关键事实
- 冲突原因：
- 哈希函数将无限键映射到有限槽位，难免重复。
- 解决目标：
- 保证所有键可存储和查找。
- 常用方式：
- 在 Java HashMap 中，采用 拉链法 + 红黑树。
具体解决方式
1. 开放寻址法（Open Addressing）
- 原理：冲突时在数组中寻找下一个空位存储。
- 实现：
- 线性探测：依次检查下一位置（index + 1）。
- 二次探测：按平方步长（index + 1², index + 2²）。
- 双重哈希：用第二个哈希函数计算偏移。
- 优点：无需额外结构，空间利用高。
- 缺点：容易聚集（冲突集中），删除复杂。
2. 拉链法（Separate Chaining）
- 原理：冲突时用链表存储同一槽位的多个键值对。
- 实现：
- 数组每个槽位指向一个链表，冲突元素追加到链表。
- 优点：简单，动态扩展，无聚集问题。
- 缺点：链表过长查询慢，需额外空间。
- Java 应用：HashMap 默认用链表，JDK 8+ 链表超 8 转红黑树。
3. 再哈希法（Rehashing）
- 原理：冲突时用另一哈希函数重新计算位置，直到无冲突。
- 实现：
- 准备多个哈希函数，依次尝试。
- 优点：分布均匀，冲突少。
- 缺点：计算复杂，需设计多个函数。
4. 建立公共溢出区
- 原理：冲突的键值对存入单独的溢出区域。
- 实现：
- 主哈希表存无冲突数据，溢出表存冲突数据。
- 优点：主表查询快，冲突隔离。
- 缺点：溢出区管理复杂，空间浪费。
延伸与面试角度
- 与红黑树结合：
- HashMap（JDK 8+）：链表长度 > 8 转红黑树，查询从 O(n) 降到 O(log n)。
- 性能对比：
- 开放寻址：查询 O(1) 到 O(n)，空间高效。
- 拉链法：平均 O(1)，冲突多时 O(n) 或 O(log n)。
- 实际应用：
- HashMap：拉链法 + 红黑树。
- 数据库索引：有时用开放寻址。
- 优缺点：
- 开放寻址：紧凑但聚集。
- 拉链法：灵活但内存多。
- 面试点：
- 问“选择依据”时，提冲突率和查询需求。
- 问“HashMap 优化”时，提树化。
总结
解决 Hash 冲突的方式有开放寻址（探测空位）、拉链法（链表）、再哈希（多函数）和溢出区（隔离存储）。HashMap 用拉链法 + 红黑树，兼顾效率和扩展性。面试时，可画拉链法结构或提 JDK 8 优化，展示理解深度。