如何解决哈希冲突？
目录
1. 链接法
2. 开放寻址法
2.1. 线性探测
2.2. 二次探测
2.3. 双重哈希
3. 再哈希法
4. 哈希桶扩容
5.方法比较
5.1. 链接法
5.2. 开放寻址法
5.3. 再哈希法
5.4. 哈希桶扩容
哈希表就是通过散列函数将键映射到定值，简单来说就是一个键对应一个值。
而通过散列函数映射时将两个键映射到了同一个值，即这两个键将被哈希表映射到同一个位置，这种情况就被称为哈希冲突。
解决哈希冲突通过有四种方法：
- 链接法
- 开放寻址法
- 再哈希法
- 哈希桶扩容
1. 链接法
每个哈希表的槽位维护一个链表或其他数据结构，当多个元素被哈希到同一个槽位时，它们会被放在这个槽位的链表中。查找时会遍历链表，插入时也会直接加到链表中。
假设我们有一个哈希表，哈希函数将键值映射到以下槽位：
- 0: [5, 15]
- 1: []
- 2: [2]
- 3: []
- 4: [4]
当我们插入键值 5 和 15 时，它们都被映射到槽位 0。因此，它们会形成一个链表：
槽位 0: [5 -> 15]
槽位 1: []
槽位 2: [2]
槽位 3: []
槽位 4: [4]
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. 哈希桶扩容
优点：
- 通过扩容可以有效降低负载因子，从而减少冲突。
- 能够保持较高的性能，特别是在处理大量数据时。
缺点：
- 扩容过程可能需要遍历整个哈希表，重新计算哈希值，导致短时间内性能下降。
- 增加了内存的使用和管理复杂度。