在计算机科学的世界里，哈希表是一种非常重要的数据结构，它能让我们以接近常量时间复杂度来存储和查找数据。不过，哈希表在实际使用时会碰到一个棘手的问题——哈希冲突。今天咱们就来聊聊解决哈希冲突的两种常用方法：开放寻址法和链地址法，对比一下它们的性能，还会给出源码实现。
一、哈希冲突是怎么回事
想象一下，你去参加一场大型派对，主办方给每个人都分配了一个独特的房间号。不过，由于房间号的生成方式有点特殊，结果出现了两个人被分配到同一个房间的情况。这就是哈希冲突啦。在哈希表中，哈希函数会把数据映射到一个固定大小的数组索引上，要是不同的数据被映射到了同一个索引位置，就产生哈希冲突了。
比如，我们有一个简单的哈希表，数组大小为 5，哈希函数是 hash(key) = key % 5。当我们要插入 3 和 8 时，3 % 5 = 3，8 % 5 = 3，这时候就会发生哈希冲突，因为 3 和 8 都要放到数组索引为 3 的位置。
二、开放寻址法
基本原理
开放寻址法的基本思路是，当发生哈希冲突时，我们就去寻找数组中的其他空位来存放数据。就好像在派对上，两个人被分到同一个房间后，他们会尝试去找其他空着的房间。开放寻址法有几种常见的方式，比如线性探测、二次探测和双重哈希。
线性探测
线性探测就是在发生冲突后，依次检查下一个位置，直到找到一个空位为止。下面是用 Java 实现的一个简单的线性探测哈希表示例：
class LinearProbingHashTable {
private int[] table;
private int size;
// 初始化哈希表
public LinearProbingHashTable(int capacity) {
table = new int[capacity];
// -1 表示该位置为空
for (int i = 0; i < capacity; i++) {
table[i] = -1;
}
size = 0;
}
// 哈希函数
private int hash(int key) {
return key % table.length;
}
// 插入操作
public void insert(int key) {
int index = hash(key);
while (table[index] != -1) {
// 线性探测下一个位置
index = (index + 1) % table.length;
}
table[index] = key;
size++;
}
// 查找操作
public boolean search(int key) {
int index = hash(key);
int start = index;
while (table[index] != -1) {
if (table[index] == key) {
return true;
}
index = (index + 1) % table.length;
// 回到起始位置，说明找遍了整个表
if (index == start) {
break;
}
}
return false;
}
}
二次探测
二次探测是在发生冲突后，按照二次方的步长去寻找空位。比如，第一次冲突后检查下一个位置，第二次冲突后检查下 4 个位置，第三次检查下 9 个位置，以此类推。
双重哈希
双重哈希使用两个哈希函数，当发生冲突时，用第二个哈希函数计算步长来寻找空位。
优缺点
优点：
- 不需要额外的链表结构，节省了空间。
- 缓存命中率相对较高，因为数据都存储在一个数组中。
缺点：
- 容易出现聚集现象，尤其是线性探测，会导致查找、插入和删除操作的效率降低。
- 当哈希表接近满时，性能会急剧下降。
应用场景
开放寻址法适用于哈希表规模较小、对空间要求较高的场景，比如嵌入式系统。
三、链地址法
基本原理
链地址法的做法是，在哈希表的每个数组位置上都维护一个链表。当发生哈希冲突时，就把新的数据添加到对应位置的链表中。这就好比在派对上，同一个房间可以容纳多个人，这些人通过某种联系（链表）组织在一起。
下面是用 Java 实现的一个链地址法哈希表示例：
import java.util.LinkedList;
class ChainingHashTable {
private LinkedList<Integer>[] table;
private int size;
// 初始化哈希表
public ChainingHashTable(int capacity) {
table = new LinkedList[capacity];
for (int i = 0; i < capacity; i++) {
table[i] = new LinkedList<>();
}
size = 0;
}
// 哈希函数
private int hash(int key) {
return key % table.length;
}
// 插入操作
public void insert(int key) {
int index = hash(key);
table[index].add(key);
size++;
}
// 查找操作
public boolean search(int key) {
int index = hash(key);
return table[index].contains(key);
}
}
优缺点
优点：
- 处理哈希冲突的能力强，不会出现聚集现象。
- 插入、查找和删除操作的平均时间复杂度都是 O(1)。
缺点：
- 需要额外的链表结构，占用更多的空间。
- 链表节点的内存不连续，缓存命中率较低。
应用场景
链地址法适用于哈希表规模较大、数据量不确定的场景，比如数据库系统。
四、性能对比
时间复杂度
在理想情况下，开放寻址法和链地址法的插入、查找和删除操作的平均时间复杂度都是 O(1)。不过，当哈希表的负载因子（数据数量与数组大小的比值）增加时，开放寻址法的性能会下降得比较快，因为聚集现象会越来越严重。而链地址法的性能相对比较稳定，因为它只是在链表中进行操作。
空间复杂度
开放寻址法只需要一个数组来存储数据，空间复杂度是 O(n)。链地址法除了数组外，还需要额外的链表节点，空间复杂度也是 O(n)，但实际占用的空间会比开放寻址法多一些。
五、注意事项
对于开放寻址法
- 要选择合适的哈希函数，避免过多的冲突。
- 当哈希表接近满时，要及时进行扩容，以保证性能。
对于链地址法
- 要注意链表的长度，如果链表过长，会影响查找效率。可以考虑在链表长度达到一定阈值时，将链表转换为红黑树。
六、总结
开放寻址法和链地址法是解决哈希冲突的两种常用方法，各有优缺点。开放寻址法节省空间，缓存命中率高，但容易出现聚集现象；链地址法处理冲突能力强，性能稳定，但占用更多的空间。在实际应用中，我们要根据具体的场景来选择合适的方法。如果对空间要求较高，哈希表规模较小，可以选择开放寻址法；如果数据量不确定，哈希表规模较大，链地址法是更好的选择。
评论