什么是哈希碰撞？
哈希碰撞是指不同的输入通过哈希函数计算后得到了相同的哈希值的情况。在哈希表（如 Java 中的 HashMap）中，键（Key）首先会被转换成一个哈希码（hashCode），然后这个哈希码被进一步处理以确定该键值对应该存储在数组中的哪个位置（即桶，bucket）。当两个或多个不同的键产生了相同的哈希码，并且这些哈希码经过处理后指向了同一个桶时，就发生了哈希碰撞。
如何解决哈希碰撞？
为了解决哈希碰撞，常见的策略主要有两种：链地址法（Separate Chaining） 和 开放地址法（Open Addressing）。Java 的 HashMap 主要采用的是链地址法，同时也结合了一些优化策略来处理哈希碰撞问题。
链地址法（Separate Chaining）
- 在这种方法中，每个桶实际上是一个数据结构（如链表或树）。当发生哈希碰撞时，新的键值对不会尝试寻找另一个空位，而是直接添加到对应桶的数据结构中。
- 在 Java 的
HashMap实现中，如果多个键映射到了同一个桶，则它们会形成一个链表。自 JDK 8 开始，如果链表长度超过一定阈值（默认是8），则链表将转换为红黑树，以提高查找效率。 - 这种方法的优点在于实现简单，插入和删除操作相对容易；缺点是在最坏的情况下（所有元素都映射到了同一个桶），查找的时间复杂度可能退化至 O(n)。
开放地址法（Open Addressing）
- 开放地址法则是寻找另一个空闲位置来存放新元素。有几种具体的实现方式：
- 线性探测（Linear Probing）：当碰撞发生时，从当前位置开始向后逐个检查直到找到一个空位。
- 二次探测（Quadratic Probing）：与线性探测类似，但是跳跃步长按照二次函数增长（例如 1, 4, 9, …）。
- 双重散列（Double Hashing）：使用第二个哈希函数生成步长，避免聚集现象。
- 这种方法的主要优点是可以减少内存开销，因为不需要额外的数据结构来存储冲突的元素；然而，它可能导致“聚集”问题，即连续的哈希冲突会导致性能下降。
其他优化策略
除了上述两种主要的方法外，还有一些其他技术可以用来减少哈希碰撞的影响或概率：
- 良好的哈希函数设计：一个好的哈希函数应尽可能均匀地分布输出值，从而降低冲突的可能性。
- 扩容机制：当哈希表中的元素数量接近其容量限制时，增加哈希表的大小并重新分配所有的元素，这样可以减少未来的碰撞。
- 扰动函数：如 Java
HashMap中使用的额外的扰动步骤（将高16位与低16位进行异或运算），旨在使高位也参与决定索引位置，有助于分散哈希值，减少碰撞几率。
通过这些方法和技术，可以在很大程度上缓解哈希碰撞带来的负面影响，确保哈希表能够高效运行。在实际应用中，选择哪种方法取决于具体的应用场景和需求。例如，在 Java 的 HashMap 中，默认采用的是链地址法，并在特定条件下转为使用红黑树来提高效率。
THE END
