什么是Hash碰撞？怎么解决哈希碰撞？

Hash碰撞是指在哈希算法中，不同的输入数据（通常称为键）通过哈希函数计算后得到相同的哈希值，从而映射到哈希表中的同一个槽（bucket）或位置。这种情况不可避免，因为哈希函数需要将大量可能的输入压缩到有限的槽位中，因此总会有不同的键共享同一哈希值。

解决哈希碰撞的方法主要有以下几种：

1. 链地址法（Chaining）

每个哈希表的槽位不直接存放单个元素，而是存放一个链表（或其他数据结构，如平衡树），所有映射到同一槽位的元素都插入该链表中。在查询时，只需遍历该链表来查找目标元素。

2. 开放地址法（Open Addressing）

当发生碰撞时，不在原位置存放冲突数据，而是在哈希表中寻找下一个空槽。常见策略包括：

• 线性探测（Linear Probing）： 顺序检查后续槽位，直到找到空位。
• 二次探测（Quadratic Probing）： 根据二次函数公式计算探测间隔，减少连续碰撞。
• 双重散列（Double Hashing）： 使用第二个哈希函数计算探测步长，进一步分散冲突。

3. 扩容+再哈希操作

• 扩容（Resize）：
  当哈希表中的元素过多时，单个槽位的冲突概率增大。这时会增加哈希表的槽位数量，从而降低每个槽位上的平均负载。
• 再哈希（Rehashing）：
  扩容之后，原有键在旧哈希表中的位置可能不再适用于新表。再哈希的过程就是重新计算每个键的哈希值，并根据新的哈希函数（或相同哈希函数在更大容量下的效果）将键重新分布到新表中。这样可以更均匀地分布数据，降低碰撞的概率。

4. 其他高级方法

如布谷鸟哈希（Cuckoo Hashing）和跳跃哈希（Hopscotch Hashing）等，通过设计特殊的存储和探测机制来进一步优化冲突解决和查询效率。

选择具体的解决方案通常依赖于应用场景、数据量和对性能的要求。总体来说，合理设计哈希函数和选择合适的碰撞解决策略，是构建高效哈希表的关键。

Hash碰撞是指不同的输入数据经过哈希函数后得到相同的哈希值，导致它们被映射到哈希表中的同一位置。为了解决哈希碰撞，常用的方法有：

1. 链地址法（Chaining）： 每个槽位存储一个链表或其他数据结构，所有映射到同一槽位的元素放在一起，查询时遍历该结构。
2. 开放地址法（Open Addressing）： 当发生碰撞时，通过探测（如线性探测、二次探测或双重散列）寻找其他空槽来存放冲突的元素。
3. 扩容+再哈希（Rehashing）： 当负载因子过高时，扩展哈希表的容量，并重新计算所有键的哈希值，使数据分布更加均匀，降低碰撞概率。