经典面试题：怎么解决哈希碰撞？

回答重点

Hash 碰撞是指在使用哈希算法时，不同的输入数据通过哈希函数计算后，得到了相同的哈希值（即散列值）。因为哈希值相同，所以这些键会被映射到哈希表的同一个位置，从而引发“碰撞”。

常见有以下几种方式解决哈希碰撞问题：

1）拉链法（链地址法）：

将哈希表中每个槽的位置变成一个链表，当多个键的哈希值相同时，将它们存储在同一个链表中。

2）开放寻址法：

如果出现碰撞，寻找哈希表中的下一个可用位置。

3）再哈希法（双重哈希）：

在出现碰撞时，使用第二个哈希函数计算新的索引位置，减少碰撞的概率。

扩展知识

拉链法（链地址法）

使用链表来处理冲突，每个哈希表的槽（bucket）不仅存储单个元素，而是存储指向链表头部的指针。所有具有相同哈希值的元素都会被放入到同一个链表中。

优点：

• 简单易实现，扩展性好。
• 在处理大量数据时，性能更为稳定。

缺点：

• 如果碰撞频繁，链表会变长，导致查询性能下降。
• 需要额外的内存来存储链表的指针。

红黑树优化

当冲突产生的链表长度超过一定阈值时，可以将链表转换为红黑树。红黑树的查找时间复杂度为 O(log n)，相较于链表 O(n) 的查找复杂度，性能更高。

这个优化可以大幅提升在极端情况下的查找性能。

缺点就是实现复杂，且需要更多的内存空间。

在 Java 8 中的 HashMap 使用了链表转红黑树的解决方案。详细可看为什么 JDK 1.8 对 HashMap 进行了红黑树的改动？

开放寻址法

在哈希表中寻找下一个空闲的槽位以存储发生碰撞的元素，常见寻找方式有线性探查、平方探查和双重散列。

优点：

• 不需要额外的内存来存储指针或链表结构。
• 如果负载因子低，查找和插入的效率较高。

缺点：

• 随着哈希表的填充度增加，探查的次数会增加，导致性能下降。
• 删除元素时候，不能真的删除，只能打标，否则会导致查找错误。只能在下一个元素插入时，发现标记后才能替换原来的元素。

寻找方式

1）线性探查法：

在哈希表中查找下一个连续的空槽，将碰撞的键存入该槽中。

2）平方探查法：

类似于线性探查，但探查的步长是二次方，减少了聚集问题。

3）双散列法：

使用两个不同的哈希函数，第一次哈希决定初始位置，第二次哈希决定探查步长。

几种寻址方式本质原理都差不多，仅演示下线性探测过程：

再哈希法（双重哈希）

在出现碰撞时，使用第二个哈希函数计算新的索引位置，减少碰撞的概率