JAVA:实现使用Cuckoo Hashing的哈希表算法（附带源码）
Java 实现使用 Cuckoo Hashing 的哈希表算法
一、项目背景详细介绍
在传统的哈希表实现中，最核心的问题就是如何解决 哈希冲突（Hash Collision）。当两个键映射到相同的位置时，如果没有良好的冲突解决策略，哈希表的性能会大大下降。常见的解决方案有：
-
拉链法（Separate Chaining）
每个桶存放一个链表或者红黑树，冲突时在桶中继续查找。 -
开放寻址法（Open Addressing）
冲突时，在数组中寻找其他空位置存放，常见方式有 线性探测、二次探测、双重哈希。
然而，拉链法会增加额外的内存开销，开放寻址法可能造成 聚集效应（Clustering），查找效率降低。
为了解决这些问题，Cuckoo Hashing（布谷鸟哈希） 被提出。
Cuckoo Hashing 的核心思想
布谷鸟哈希借鉴了布谷鸟在鸟巢中的行为：
-
每个元素最多有两个可能的位置（由两个不同的哈希函数决定）；
-
插入新元素时，如果某个位置已被占用，就会“赶走”原来的元素，并让它去它的另一个可能位置；
-
如果被赶走的元素在新位置也遇到冲突，就会继续“踢走”下一个，直到找到空位或触发重哈希。
这样，Cuckoo Hashing 保证了：
-
查找操作只需要检查两个位置，复杂度为 O(1)；
-
插入和删除在平均情况下也很高效。
缺点是：
-
插入可能会陷入“循环踢来踢去”的情况，此时需要 rehash（扩容或重新计算哈希函数）。
-
内存利用率稍低，因为需要为两个表/两个哈希函数预留位置。
二、项目需求详细介绍
我们要实现一个 基于 Cuckoo Hashing 的哈希表，其功能包括：
-
put(K key, V value)：插入或更新键值对
-
get(K key)：根据键查找值
-
remove(K key)：删除键值对
-
containsKey(K key)：判断键是否存在
-
size()：获取当前元素个数
-
rehash()：在陷入死循环或负载过高时触发扩容并重新哈希
具体需求：
-
使用两个哈希函数，分别映射到两张表（或者同一张表的两个区域）。
-
在插入时，如果冲突，就进行踢出操作。
-
设置一个最大踢出次数，超过时触发重哈希。
-
支持泛型键值对存储。
三、相关技术详细介绍
1. 哈希函数
需要至少两个不同的哈希函数 h1、h2，它们对同一个键生成两个可能的位置。
例如：
h1 = key.hashCode() % capacity; h2 = (key.hashCode() / capacity) % capacity;
2. 插入（Cuckoo 过程）
-
首先尝试放入位置 h1；
-
如果已被占用，则踢出原有元素，把它放到它的另一个位置；
-
如果被踢出的元素再次冲突，则继续踢；
-
如果踢的次数超过阈值，说明可能进入循环，触发重哈希。
3. 删除
在两个可能位置查找，如果找到就删除即可。
4. Rehash
当：
-
踢出次数超过上限；
-
或者负载因子超过阈值；
需要扩展表容量并重新插入所有元素。
四、实现思路详细介绍
-
定义一个内部类
Entry<K,V>存放键值对。 -
使用两个数组（表）
table1和table2存储元素。 -
put()时：-
先尝试放入 table1[h1]；
-
冲突时踢出并转移到 table2[h2]；
-
如果循环过多次，触发 rehash。
-
-
get()时：-
查找 table1[h1] 或 table2[h2]；
-
-
remove()时：-
如果在两个位置之一找到，设为 null。
-
-
rehash()时：-
扩展容量为原来的两倍；
-
将所有旧数据重新插入。
-
五、完整实现代码
// 文件：CuckooHashMap.java
import java.util.Arrays;
public class CuckooHashMap<K, V> {
private static final int DEFAULT_CAPACITY = 8; // 初始容量
private static final double LOAD_FACTOR = 0.5; // 负载因子（较低，避免冲突过多）
private static final int MAX_KICKS = 16; // 最大踢出次数
private Entry<K, V>[] table1;
private Entry<K, V>[] table2;
private int capacity;
private int size;
// 内部类 Entry
private static class Entry<K, V> {
K key;
V value;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
}
// 构造函数
public CuckooHashMap() {
this.capacity = DEFAULT_CAPACITY;
this.table1 = new Entry[capacity];
this.table2 = new Entry[capacity];
this.size = 0;
}
// 哈希函数1
private int hash1(Object key) {
return (key.hashCode() & 0x7fffffff) % capacity;
}
// 哈希函数2
private int hash2(Object key) {
return ((key.hashCode() / capacity) & 0x7fffffff) % capacity;
}
// 插入/更新
public void put(K key, V value) {
if (containsKey(key)) {
// 如果存在，更新
if (table1[hash1(key)] != null && table1[hash1(key)].key.equals(key)) {
table1[hash1(key)].value = value;
return;
}
if (table2[hash2(key)] != null && table2[hash2(key)].key.equals(key)) {
table2[hash2(key)].value = value;
return;
}
}
if ((double) size / (2 * capacity) > LOAD_FACTOR) {
resize(capacity * 2);
}
Entry<K, V> newEntry = new Entry<>(key, value);
for (int kick = 0; kick < MAX_KICKS; kick++) {
int pos1 = hash1(newEntry.key);
if (table1[pos1] == null) {
table1[pos1] = newEntry;
size++;
return;
} else {
// 踢出
Entry<K, V> temp = table1[pos1];
table1[pos1] = newEntry;
newEntry = temp;
}
int pos2 = hash2(newEntry.key);
if (table2[pos2] == null) {
table2[pos2] = newEntry;
size++;
return;
} else {
// 踢出
Entry<K, V> temp = table2[pos2];
table2[pos2] = newEntry;
newEntry = temp;
}
}
// 踢出过多次，触发rehash
resize(capacity * 2);
put(newEntry.key, newEntry.value);
}
// 查找
public V get(K key) {
int pos1 = hash1(key);
if (table1[pos1] != null && table1[pos1].key.equals(key)) {
return table1[pos1].value;
}
int pos2 = hash2(key);
if (table2[pos2] != null && table2[pos2].key.equals(key)) {
return table2[pos2].value;
}
return null;
}
// 删除
public void remove(K key) {
int pos1 = hash1(key);
if (table1[pos1] != null && table1[pos1].key.equals(key)) {
table1[pos1] = null;
size--;
return;
}
int pos2 = hash2(key);
if (table2[pos2] != null && table2[pos2].key.equals(key)) {
table2[pos2] = null;
size--;
}
}
// 是否包含
public boolean containsKey(K key) {
return get(key) != null;
}
// 当前大小
public int size() {
return size;
}
// 扩容并重新哈希
private void resize(int newCapacity) {
Entry<K, V>[] oldTable1 = table1;
Entry<K, V>[] oldTable2 = table2;
table1 = new Entry[newCapacity];
table2 = new Entry[newCapacity];
capacity = newCapacity;
size = 0;
for (Entry<K, V> e : oldTable1) {
if (e != null) put(e.key, e.value);
}
for (Entry<K, V> e : oldTable2) {
if (e != null) put(e.key, e.value);
}
}
// 打印哈希表
@Override
public String toString() {
return "Table1: " + Arrays.toString(table1) + "\nTable2: " + Arrays.toString(table2);
}
// 测试
public static void main(String[] args) {
CuckooHashMap<Integer, String> map = new CuckooHashMap<>();
map.put(1, "A");
map.put(9, "B");
map.put(17, "C");
map.put(25, "D");
System.out.println("Map大小: " + map.size());
System.out.println("取key=9: " + map.get(9));
System.out.println("取key=17: " + map.get(17));
map.remove(9);
System.out.println("删除key=9后，containsKey(9): " + map.containsKey(9));
// 扩容测试
for (int i = 0; i < 50; i++) {
map.put(i, "Val" + i);
}
System.out.println("扩容后大小: " + map.size());
}
}
六、代码详细解读
-
Entry<K,V>
存放键值对。 -
hash1 和 hash2
分别计算两个位置，保证一个 key 有两个可能存放位置。 -
put 方法
-
优先尝试放到 table1；
-
如果冲突，就踢出原来的元素，让它去 table2；
-
如果 table2 也冲突，就再踢；
-
如果超过最大踢出次数，触发 rehash。
-
-
get 方法
只需查两个位置，O(1)。 -
remove 方法
只要在两个位置之一找到，设为 null 即可。 -
resize 方法
容量翻倍，重新插入所有元素，避免死循环。
七、项目详细总结
通过实现 Cuckoo Hashing，我们得到了一种性能更稳定的哈希表：
-
查找操作只需检查两个位置，时间复杂度 O(1)；
-
插入可能触发多次踢出，但平均性能依旧较好；
-
删除操作也很高效；
-
需要注意控制负载因子，避免过多冲突。
与传统 HashMap 相比，Cuckoo Hashing 的优点是 查找稳定且可预测，缺点是实现复杂度更高。
八、项目常见问题及解答
问题1：为什么要用两个哈希函数？
答：保证每个元素至少有两个可能位置，降低冲突概率。
问题2：为什么要设置最大踢出次数？
答：避免陷入死循环，当循环过多次说明需要 rehash。
问题3：负载因子为什么取 0.5？
答：因为 Cuckoo Hashing 在高负载下容易频繁触发踢出，为了性能稳定，需要保持较低的负载。
问题4：rehash 是否一定要扩容？
答：不一定，可以只更换哈希函数。但在实现上更常见的是扩容。
九、扩展方向与性能优化
-
多哈希函数 Cuckoo Hashing
不止两个位置，可以使用 3 个或更多位置，进一步减少冲突概率。 -
随机化 rehash
当 rehash 时，可以随机改变哈希函数，减少循环踢出的风险。 -
并发优化
类似于 ConcurrentHashMap，可以分片锁实现线程安全的 Cuckoo Hashing。 -
内存优化
将两个表合并为一个大表，分别管理不同区间，提高缓存命中率。
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
27
0- 0
已为社区贡献484条内容
所有评论(0)