一、哈希表冲突问题的引出
大家都知道，哈希表是一种很实用的数据结构，它能让我们快速地存储和查找数据。简单来说，哈希表就像是一个大仓库，每个数据都有自己的“房间”。这个“房间号”是通过哈希函数算出来的。不过呢，有时候就会出现问题，不同的数据经过哈希函数计算后，可能会得到相同的“房间号”，这就产生了冲突。
比如说，我们有一个简单的哈希函数，它把数据对 10 取余数作为“房间号”。现在有两个数据 12 和 22，12 % 10 = 2，22 % 10 也等于 2，这两个数据就都想住进“2 号房间”，冲突就这么产生了。
二、开放寻址法
1. 线性探测法
线性探测法是开放寻址法里比较简单的一种。当发生冲突时，它会按照顺序一个一个地往后找空“房间”。
下面是用 Java 实现的一个简单示例：
// Java 技术栈
class LinearProbingHashTable {
private int[] table;
private int size;
public LinearProbingHashTable(int size) {
this.size = size;
table = new int[size];
// 用 -1 表示“房间”为空
for (int i = 0; i < size; i++) {
table[i] = -1;
}
}
// 哈希函数
private int hash(int key) {
return key % size;
}
// 插入数据
public void insert(int key) {
int index = hash(key);
while (table[index] != -1) {
// 发生冲突，线性往后找
index = (index + 1) % size;
}
table[index] = key;
}
// 查找数据
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) % size;
// 如果回到起点还没找到，说明不存在
if (index == start) {
break;
}
}
return false;
}
}
public class Main {
public static void main(String[] args) {
LinearProbingHashTable hashTable = new LinearProbingHashTable(10);
hashTable.insert(12);
hashTable.insert(22);
System.out.println(hashTable.search(12)); // 输出 true
System.out.println(hashTable.search(22)); // 输出 true
System.out.println(hashTable.search(32)); // 输出 false
}
}
2. 线性探测法的优缺点
优点：实现简单，只需要简单的循环就能解决冲突。 缺点：容易产生“聚集”现象。就是说，当多个数据冲突后，会在某个区域形成一片连续的占用“房间”，这样后续查找和插入的效率就会降低。
3. 二次探测法
二次探测法和线性探测法类似，不过它不是一个一个地往后找，而是按照二次方的步长去找空“房间”。
下面是 Java 实现的示例：
// Java 技术栈
class QuadraticProbingHashTable {
private int[] table;
private int size;
public QuadraticProbingHashTable(int size) {
this.size = size;
table = new int[size];
for (int i = 0; i < size; i++) {
table[i] = -1;
}
}
private int hash(int key) {
return key % size;
}
public void insert(int key) {
int index = hash(key);
int i = 1;
while (table[index] != -1) {
// 二次探测
index = (index + i * i) % size;
i++;
}
table[index] = key;
}
public boolean search(int key) {
int index = hash(key);
int start = index;
int i = 1;
while (table[index] != -1) {
if (table[index] == key) {
return true;
}
index = (index + i * i) % size;
i++;
if (index == start) {
break;
}
}
return false;
}
}
public class Main2 {
public static void main(String[] args) {
QuadraticProbingHashTable hashTable = new QuadraticProbingHashTable(10);
hashTable.insert(12);
hashTable.insert(22);
System.out.println(hashTable.search(12)); // 输出 true
System.out.println(hashTable.search(22)); // 输出 true
System.out.println(hashTable.search(32)); // 输出 false
}
}
4. 二次探测法的优缺点
优点：能在一定程度上缓解线性探测法的“聚集”问题。 缺点：可能会出现找不到空“房间”的情况，尤其是在哈希表快满的时候。
三、链地址法
链地址法是另一种解决哈希冲突的方法。它的思路是，每个“房间”不再只放一个数据，而是放一个链表。当发生冲突时，就把新的数据添加到这个链表的后面。
下面是 Java 实现的示例：
// Java 技术栈
import java.util.LinkedList;
class ChainingHashTable {
private LinkedList<Integer>[] table;
private int size;
public ChainingHashTable(int size) {
this.size = size;
table = new LinkedList[size];
for (int i = 0; i < size; i++) {
table[i] = new LinkedList<>();
}
}
private int hash(int key) {
return key % size;
}
public void insert(int key) {
int index = hash(key);
table[index].add(key);
}
public boolean search(int key) {
int index = hash(key);
return table[index].contains(key);
}
}
public class Main3 {
public static void main(String[] args) {
ChainingHashTable hashTable = new ChainingHashTable(10);
hashTable.insert(12);
hashTable.insert(22);
System.out.println(hashTable.search(12)); // 输出 true
System.out.println(hashTable.search(22)); // 输出 true
System.out.println(hashTable.search(32)); // 输出 false
}
}
1. 链地址法的优缺点
优点：不会像开放寻址法那样产生“聚集”现象，插入和查找的效率比较稳定。而且哈希表的利用率比较高，不需要像开放寻址法那样预留很多空“房间”。 缺点：每个“房间”都要维护一个链表，会占用额外的内存空间。而且当链表很长时，查找的效率会降低。
四、开放寻址法和链地址法的性能对比
1. 插入性能
在插入数据时，开放寻址法如果遇到冲突，需要不断地找空“房间”，尤其是在哈希表快满的时候，插入的效率会明显降低。而链地址法只需要把数据添加到链表后面，插入的效率比较稳定。
2. 查找性能
开放寻址法查找数据时，也需要不断地比较和移动，尤其是在“聚集”严重的情况下，查找效率会大打折扣。链地址法查找数据时，只需要遍历对应的链表，相对来说查找效率更稳定。
3. 空间利用率
开放寻址法为了避免冲突，需要预留一些空“房间”，空间利用率相对较低。链地址法每个“房间”可以存储多个数据，空间利用率较高。
五、选择合适的冲突解决方法
1. 应用场景
如果哈希表的数据量比较小，而且对空间要求比较高，开放寻址法是一个不错的选择。比如说，在嵌入式系统中，内存资源有限，就可以考虑使用开放寻址法。
如果哈希表的数据量比较大，而且对插入和查找的效率要求比较高，链地址法更合适。比如在大型的数据库系统中，需要快速地存储和查找大量的数据，链地址法就能发挥它的优势。
2. 注意事项
使用开放寻址法时，要注意哈希表的负载因子。负载因子是指哈希表中已存储的数据数量和哈希表总容量的比值。当负载因子过高时，开放寻址法的效率会急剧下降。
使用链地址法时，要注意链表的长度。如果链表过长，查找的效率会降低。可以考虑在链表长度达到一定阈值时，将链表转换为红黑树等更高效的数据结构。
六、文章总结
哈希表冲突是一个在使用哈希表时经常会遇到的问题。开放寻址法和链地址法是两种常见的解决冲突的方法，它们各有优缺点。开放寻址法实现简单，但容易产生“聚集”现象，空间利用率较低。链地址法不会产生“聚集”，空间利用率高，但会占用额外的内存空间。在实际应用中，我们要根据具体的场景和需求，选择合适的冲突解决方法。同时，要注意一些使用过程中的注意事项，以保证哈希表的性能。
评论