腾讯面试：如何解决哈希冲突？

我们面试时经常被问到HashMap是怎么解决哈希冲突的，很多同学对其含糊其词、一知半解。因此小编对相关知识进行了总结，希望帮助读者加深对其理解。

哈希表就是通过散列函数将键映射到定值，简单来说就是一个键对应一个值。

而通过散列函数映射时将两个键映射到了同一个值，即这两个键将被哈希表映射到同一个位置，这种情况就被称为哈希冲突。

解决哈希冲突通过有四种方法：

• 链接法
• 开放寻址法
• 再哈希法
• 哈希桶扩容

1. 链接法

每个哈希表的槽位维护一个链表或其他数据结构，当多个元素被哈希到同一个槽位时，它们会被放在这个槽位的链表中。查找时会遍历链表，插入时也会直接加到链表中。

假设我们有一个哈希表，哈希函数将键值映射到以下槽位：

0: [5, 15]1: []2: [2]3: []4: [4]当我们插入键值 5 和 15 时，它们都被映射到槽位 0。因此，它们会形成一个链表：

槽位 0: [5 -> 15]槽位 1: []槽位 2: [2]槽位 3: []槽位 4: [4]

另外：
推荐一个程序员免费学习的编程网站：我爱编程网（www.love-coding.com）
涵盖 Java几乎覆盖了所有主流技术面试题，还有市面上最全的技术精品系列教程，免费提供。

2. 开放寻址法

当发生冲突时，算法会寻找下一个可用的槽位。常见的探查方式有线性探查、二次探查和双重哈希等。这种方法不使用额外的存储结构，而是在哈希表内部处理所有元素。开放寻址法的几种常见探测方法确实包括线性探测、二次探测和双重散列。以下是每种方法的详细说明和示例：

2.1. 线性探测

在发生冲突时，线性探测会逐个检查后续的槽位，直到找到一个空槽。例如：

假设哈希函数为 h(k) = k % 5。

• 插入 1 → 槽位 1（成功）
• 插入 6 → 槽位 1（冲突），检查 2（成功）
• 插入 11 → 槽位 1（冲突），2（冲突），3（成功）

最终哈希表：

槽位 0: []
槽位 1: [1]
槽位 2: [6]
槽位 3: [11]
槽位 4: []

2.2. 二次探测

二次探测在发生冲突时采用平方递增的方式查找空槽。例如：

哈希函数仍然假设是 h(k) = k % 5。

• 插入 1 → 槽位 1（成功）
• 插入 6 → 槽位 1（冲突），检查 1^2 → 2（成功）
• 插入 11 → 槽位 1（冲突），检查 1^2（冲突），2^2 → 4（成功）

最终哈希表：

槽位 0: []
槽位 1: [1]
槽位 2: []
槽位 3: []
槽位 4: [6]

2.3. 双重哈希

双重散列使用第二个哈希函数来决定步长，以解决冲突。例如：

假设第一个哈希函数 h1(k) = k % 5，第二个哈希函数 h2(k) = 1 + (k % 4)。

插入 1 → 槽位 1（成功）插入 6 → 槽位 1（冲突），步长 h2(6) = 1 + (6 % 4) = 3，检查 1 + 3 = 4（成功）插入 11 → 槽位 1（冲突），步长 h2(11) = 1 + (11 % 4) = 3，检查 1 + 3 = 4（冲突），再检查 4 + 3 = 2（成功）

最终哈希表：

槽位 0: []
槽位 1: [1]
槽位 2: [11]
槽位 3: []
槽位 4: [6]

3. 再哈希法

在发生冲突后，可以使用另一个哈希函数对该元素进行再哈希，找到一个新的槽位。

使用初始哈希函数 h1(k) = k % 5，当插入 10 时：

• h1(10) = 0（槽位 0 已占用）

• 使用新的哈希函数

  h2(k) = (k / 5) % 5
  

  ，计算：

• • h2(10) = 2（槽位 2 已占用）

• 再次使用

  h1
  

  计算：

• • h1(10 + 1) = 1（槽位 1 已占用）
  • h1(10 + 2) = 3（放入槽位 3）

最终哈希表如下：

槽位 0: [0]
槽位 1: [1]
槽位 2: [2]
槽位 3: [10]
槽位 4: [4]

4. 哈希桶扩容

如果哈希表的负载因子超过某个阈值，可以增加哈希表的大小，并重新计算所有元素的哈希值并重新分配到新的槽位。这有助于减少冲突并提高性能

哈希表的负载因子是一个衡量哈希表填充程度的重要指标，通常用公式表示为：负载因子 = 哈希表中的元素数量 / 哈希表的槽位总数负载因子的意义：高负载因子：当负载因子接近或超过 1 时，表示哈希表的槽位几乎被填满，可能导致更多的哈希冲突，从而影响查找、插入和删除的性能。
低负载因子：负载因子较低时，哈希表的空槽较多，冲突较少，性能较好，但会导致内存浪费。
负载因子的调整：通常，当负载因子超过某个设定的阈值（例如 0.7 或 0.75），就会进行扩容。扩容时，哈希表的槽位数量增加，所有元素需要重新哈希并放入新的槽位中。

假设哈希表的大小为 5，当前负载因子超过 0.7，我们决定扩容到 10。在扩容时，所有元素的哈希值需要重新计算：

• 原哈希表：

槽位 0: [0]
槽位 1: [1]
槽位 2: [2]
槽位 3: [3]
槽位 4: [4]

• 扩容后，哈希函数改为 h(k) = k % 10，插入后的哈希表：

槽位 0: []
槽位 1: [1]
槽位 2: [2]
槽位 3: [3]
槽位 4: [4]
槽位 5: [5]
槽位 6: []
槽位 7: []
槽位 8: []
槽位 9: []

5.方法比较

5.1. 链接法

优点：

• 容易实现，简单明了。
• 动态性好，可以存储任意数量的元素，只受限于内存。
• 插入和删除操作较快，不需要重新哈希。

缺点：

• 在某些情况下，链表可能会很长，导致查找性能下降。如果链表过长，可能导致性能接近于线性查找。
• 需要额外的内存来存储链表节点。

5.2. 开放寻址法

优点：

• 所有元素都存储在哈希表内部，节省了额外的内存。
• 不需要额外的链表，查找时不需要遍历。

缺点：

• 哈希表的负载因子需要控制在较低水平，通常小于 0.7，否则性能显著下降。
• 在频繁冲突的情况下，查找效率会下降，且可能需要进行多次探测。
• 删除操作复杂，可能导致“探测链”的问题，影响后续查找性能。

5.3. 再哈希法

优点：

• 通过使用不同的哈希函数，能有效地减少冲突。
• 可与其他方法结合使用，灵活性高。

缺点：

• 需要额外的计算和存储开销，可能导致性能下降。
• 在大量元素插入时，可能需要频繁地进行哈希计算。

5.4. 哈希桶扩容

优点：

• 通过扩容可以有效降低负载因子，从而减少冲突。
• 能够保持较高的性能，特别是在处理大量数据时。

缺点：

• 扩容过程可能需要遍历整个哈希表，重新计算哈希值，导致短时间内性能下降。
• 增加了内存的使用和管理复杂度。