在哈希表中，为了处理哈希冲突（即多个元素映射到同一个哈希地址的问题），我们有两大类主要方法：链式地址法和开放寻址法。这两类方法有各自的特点、适用场景和性能表现。我们可以详细地了解它们的实现和区别。
1. 链式地址法（Chaining）
链式地址法是在哈希表的每个槽位（bucket）中维护一个链表，所有映射到相同槽位的元素都会加入该链表。
- 实现方法：每个槽位指向一个链表的头节点。发生冲突时，新的元素会被插入到该链表的末尾或头部。
- 查找操作：查找元素时，先根据哈希函数确定槽位，然后在链表中顺序查找目标元素。
- 插入操作：插入元素时，找到对应槽位，将元素插入链表（通常插入链表头部，以加快插入速度）。
- 删除操作：删除操作也相对简单，只需要在链表中查找目标元素并将其移除。
优缺点：
- 优点：链表在冲突频繁时依然可以处理数据，因此在负载因子较高时（接近或大于 1）仍然保持较好的性能。且哈希表大小不必固定，方便动态增长。
- 缺点：需要额外的存储空间来维护链表指针，且链表中的查找速度较慢（O (n) 级别），特别是当某个槽位出现大量冲突时。
适用场景：适合在哈希表装填因子较高或数据不均匀时使用，因为链表能容纳任意多的冲突元素。
2. 开放寻址法（Open Addressing）
开放寻址法是在哈希表本身找到一个“空闲”槽位来放置冲突的元素，而不是使用额外的结构来存储冲突元素。它的实现方式主要有三种：线性探测、平方探测和双重哈希。
2.1 线性探测（Linear Probing）
在发生冲突时，通过固定步长（通常是 1）依次探测下一个槽位，直到找到空位为止。
- 查找/插入操作：从冲突位置开始，按顺序探测下一个位置（i+1、i+2…），直到找到空位或匹配目标值。
- 删除操作：标记被删除元素的槽位为“已删除”，而不是真正删除它，以防止影响查找路径。
优缺点：
- 优点：实现简单，插入和查找较为连续，较好的利用 CPU 缓存。
- 缺点：容易产生“堆积”问题（即多个冲突项连续探测形成密集区域），导致查找速度下降。
适用场景：适合负载因子较低的情况（一般小于 0.7），这样才能减少堆积，提高查找效率。
2.2 平方探测（Quadratic Probing）
平方探测通过二次方的间隔来探测空闲槽位。即在冲突时，依次探测(i+1^2)、(i+2^2)、(i+3^2) 的位置。
- 查找/插入操作：从冲突槽位开始，按平方数增大步长（1, 4, 9, 16 等）进行探测。
- 删除操作：和线性探测类似，可以使用标记机制，避免影响查找路径。
优缺点：
- 优点：与线性探测相比，更加分散地探测槽位，减少了堆积现象。
- 缺点：实现略复杂，并且会导致表空间的利用率不高，当表过满时仍然会影响查找效率。
适用场景：在负载因子适中时可以更好地分散数据，降低堆积现象。
2.3 双重哈希（Double Hashing）
双重哈希在发生冲突时，使用一个辅助哈希函数来计算步长，从而进行探测。
- 实现方法：定义两个哈希函数，主哈希函数( h_1 (x) ) 决定槽位，辅助哈希函数( h_2 (x) ) 决定冲突时的步长。若槽位发生冲突，则按( i = h_1 (x) + j \times h_2 (x) )（(j=1, 2, \dots)）的方式探测。
- 查找/插入操作：先按( h_1 (x) ) 计算槽位，冲突时按( h_2 (x) ) 的步长进行探测。
- 删除操作：同样可以用标记机制来避免查找路径中断。
优缺点：
- 优点：探测过程更加分散，降低了堆积风险，是开放寻址法中最有效的探测方法。
- 缺点：实现相对复杂，需要仔细设计两个哈希函数，以避免二次冲突。
适用场景：适合较高负载因子的哈希表，但一般避免接近 1，否则查找效率会降低。
总结
| 方法 | 优点 | 缺点 | 适用场景 | | —– | —————– | ———————————————— | ————- | | 链式地址法 | 处理冲突灵活，适应高负载，方便扩展 | 需要额外存储空间，链表查找速度较慢
(转换为 ALV树 和 红黑树 就会提高性能) | 适合高负载因子及不均匀数据 | | 线性探测 | 实现简单，利用 CPU 缓存好 | 容易堆积，降低查找效率 | 适合负载因子低的情况 | | 平方探测 | 减少堆积现象，查找更加分散 | 不利于空间利用，较高负载因子时查找效率低 | 适中负载因子 | | 双重哈希 | 分散性好，有效减少堆积 | 设计复杂，需要两个哈希函数 | 适合较高负载因子 |
不同的冲突处理方式适用于不同的负载因子和数据分布，因此选择最合适的哈希冲突解决方法对哈希表的性能有着直接影响。