引言
布谷鸟哈希（Cuckoo Hashing）是一种保证 $O(1)$ 最坏情况查询时间的动态哈希表技术，其核心思想借鉴了布谷鸟的巢寄生行为：当新元素到来时，若目标位置被占用，则”踢出”原有元素，被踢出的元素再寻找自己的备选位置，形成一条踢出链。本文将用Java实现布谷鸟哈希表，讲解多哈希函数设计、踢出链循环检测与表扩容重哈希策略。读者将理解为什么这种看似暴力的冲突解决方法，反而能提供比开放寻址法和链地址法更强的最坏情况保证。
算法原理
双表双哈希结构
经典布谷鸟哈希使用两张大小为 $m$ 的表 $T_1, T_2$，以及两个独立的哈希函数 $h_1, h_2$。每个元素 $x$ 要么存储在 $T_1[h_1(x)]$，要么存储在 $T_2[h_2(x)]$。
插入与踢出机制
插入元素 $x$：
1. 尝试放入 $T_1[h_1(x)]$，若空则成功
2. 若被 $y$ 占用，将 $y$ 踢出，$x$ 占据该位置
3. 将 $y$ 尝试放入其另一张表的备选位置
4. 重复此过程，若出现循环踢出则触发重哈希
循环检测与扩容
若踢出链长度超过阈值（如 $O(\log n)$ 或固定最大迭代次数），认为当前哈希函数导致循环，需要：
1. 选择新的哈希函数
2. 扩大表容量（通常翻倍）
3. 将所有元素重新插入
Java实现
import java.util.*;
/**
* 布谷鸟哈希表 - 多哈希函数与踢出链冲突解决
* @param <K> 键类型
* @param <V> 值类型
*/
public class CuckooHashMap<K, V> {
// 默认参数
private static final int DEFAULT_CAPACITY = 16;
private static final double LOAD_FACTOR_THRESHOLD = 0.45;
private static final int MAX_KICKOUT_CHAIN = 500; // 最大踢出链长度
private static final int HASH_SEED_1 = 0x9e3779b9;
private static final int HASH_SEED_2 = 0x85ebca6b;
@SuppressWarnings("unchecked")
static class Entry<K, V> {
K key;
V value;
Entry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public String toString() {
return key + "=" + value;
}
}
private Entry<K, V>[] table1;
private Entry<K, V>[] table2;
private int capacity;
private int size;
private int kickoutSeed; // 用于生成哈希函数的随机种子
private int rehashCount; // 重哈希次数统计
@SuppressWarnings("unchecked")
public CuckooHashMap() {
this.capacity = DEFAULT_CAPACITY;
this.table1 = new Entry[capacity];
this.table2 = new Entry[capacity];
this.size = 0;
this.kickoutSeed = new Random().nextInt();
this.rehashCount = 0;
}
/**
* 第一个哈希函数
*/
private int hash1(K key) {
int h = key.hashCode() ^ HASH_SEED_1;
h ^= (h >>> 16);
h *= 0x85ebca6b;
h ^= (h >>> 13);
return Math.abs(h % capacity);
}
/**
* 第二个哈希函数（使用不同种子和混合策略）
*/
private int hash2(K key) {
int h = key.hashCode() ^ HASH_SEED_2 ^ kickoutSeed;
h ^= (h >>> 16);
h *= 0xc2b2ae35;
h ^= (h >>> 13);
return Math.abs(h % capacity);
}
/**
* 获取键在另一张表的备选位置
*/
private int alternateIndex(K key, int tableIndex, int currentIndex) {
return tableIndex == 0 ? hash2(key) : hash1(key);
}
/**
* 插入键值对
*/
public void put(K key, V value) {
if (key == null) throw new IllegalArgumentException("Key cannot be null");
// 检查是否已存在
Entry<K, V> existing = findEntry(key);
if (existing != null) {
existing.value = value;
return;
}
// 检查负载因子
if ((double) size / (2 * capacity) > LOAD_FACTOR_THRESHOLD) {
resize();
}
Entry<K, V> newEntry = new Entry<>(key, value);
// 尝试插入，可能触发踢出链
if (!insertWithKickout(newEntry, 0, hash1(key), 0)) {
// 出现循环，需要重哈希
rehash();
// 重试插入
if (!insertWithKickout(newEntry, 0, hash1(key), 0)) {
// 仍然失败，扩容后再试
resize();
insertWithKickout(newEntry, 0, hash1(key), 0);
}
}
size++;
}
/**
* 带踢出机制的插入
* @param entry 待插入条目
* @param tableIndex 当前目标表（0或1）
* @param index 目标位置
* @param depth 当前踢出链深度
* @return 是否成功插入
*/
private boolean insertWithKickout(Entry<K, V> entry, int tableIndex, int index, int depth) {
if (depth > MAX_KICKOUT_CHAIN) {
return false; // 踢出链过长，可能存在循环
}
Entry<K, V>[] table = tableIndex == 0 ? table1 : table2;
if (table[index] == null) {
table[index] = entry;
return true;
}
// 位置被占用，踢出原有元素
Entry<K, V> evicted = table[index];
table[index] = entry;
// 将被踢出的元素放入另一张表
int otherTable = 1 - tableIndex;
int otherIndex = otherTable == 0 ? hash1(evicted.key) : hash2(evicted.key);
return insertWithKickout(evicted, otherTable, otherIndex, depth + 1);
}
/**
* 根据键查找条目
*/
private Entry<K, V> findEntry(K key) {
int idx1 = hash1(key);
if (table1[idx1] != null && table1[idx1].key.equals(key)) {
return table1[idx1];
}
int idx2 = hash2(key);
if (table2[idx2] != null && table2[idx2].key.equals(key)) {
return table2[idx2];
}
return null;
}
/**
* 根据键获取值
*/
public V get(K key) {
Entry<K, V> entry = findEntry(key);
return entry != null ? entry.value : null;
}
/**
* 删除键值对
*/
public boolean remove(K key) {
int idx1 = hash1(key);
if (table1[idx1] != null && table1[idx1].key.equals(key)) {
table1[idx1] = null;
size--;
return true;
}
int idx2 = hash2(key);
if (table2[idx2] != null && table2[idx2].key.equals(key)) {
table2[idx2] = null;
size--;
return true;
}
return false;
}
/**
* 检查是否包含键
*/
public boolean containsKey(K key) {
return findEntry(key) != null;
}
/**
* 表扩容（容量翻倍）
*/
@SuppressWarnings("unchecked")
private void resize() {
Entry<K, V>[] oldTable1 = table1;
Entry<K, V>[] oldTable2 = table2;
int oldCapacity = capacity;
capacity *= 2;
table1 = new Entry[capacity];
table2 = new Entry[capacity];
size = 0;
// 重新插入所有元素
for (int i = 0; i < oldCapacity; i++) {
if (oldTable1[i] != null) {
put(oldTable1[i].key, oldTable1[i].value);
}
if (oldTable2[i] != null) {
put(oldTable2[i].key, oldTable2[i].value);
}
}
}
/**
* 重哈希（更换哈希函数种子）
*/
private void rehash() {
kickoutSeed = new Random().nextInt();
rehashCount++;
// 收集所有元素
List<Entry<K, V>> allEntries = new ArrayList<>();
for (int i = 0; i < capacity; i++) {
if (table1[i] != null) allEntries.add(table1[i]);
if (table2[i] != null) allEntries.add(table2[i]);
}
// 清空表
Arrays.fill(table1, null);
Arrays.fill(table2, null);
size = 0;
// 重新插入
for (Entry<K, V> entry : allEntries) {
put(entry.key, entry.value);
}
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public int getRehashCount() {
return rehashCount;
}
/**
* 打印哈希表内部结构（调试）
*/
public void printStructure() {
System.out.println("=== 布谷鸟哈希表结构 ===");
System.out.println("容量: " + capacity + ", 元素数: " + size);
System.out.println("重哈希次数: " + rehashCount);
System.out.println("\nTable1:");
for (int i = 0; i < capacity; i++) {
if (table1[i] != null) {
System.out.printf(" [%d] -> %s (h2=%d)%n", i, table1[i], hash2(table1[i].key));
}
}
System.out.println("\nTable2:");
for (int i = 0; i < capacity; i++) {
if (table2[i] != null) {
System.out.printf(" [%d] -> %s (h1=%d)%n", i, table2[i], hash1(table2[i].key));
}
}
}
/**
* 验证哈希表一致性
*/
public boolean validate() {
for (int i = 0; i < capacity; i++) {
if (table1[i] != null) {
if (hash1(table1[i].key) != i) return false;
}
if (table2[i] != null) {
if (hash2(table2[i].key) != i) return false;
}
}
return true;
}
public static void main(String[] args) {
CuckooHashMap<String, Integer> map = new CuckooHashMap<>();
// 基础CRUD测试
System.out.println("=== 基础功能测试 ===");
String[] keys = {"apple", "banana", "cherry", "date", "elderberry",
"fig", "grape", "honeydew", "kiwi", "lemon"};
for (int i = 0; i < keys.length; i++) {
map.put(keys[i], i * 10);
}
System.out.println("插入后大小: " + map.size());
System.out.println("get('cherry'): " + map.get("cherry"));
System.out.println("get('mango'): " + map.get("mango"));
map.remove("banana");
System.out.println("删除后大小: " + map.size());
System.out.println("containsKey('banana'): " + map.containsKey("banana"));
// 大规模测试
System.out.println("\n=== 大规模性能测试 ===");
CuckooHashMap<Integer, String> bigMap = new CuckooHashMap<>();
int n = 10000;
long start = System.currentTimeMillis();
for (int i = 0; i < n; i++) {
bigMap.put(i, "value_" + i);
}
long insertTime = System.currentTimeMillis() - start;
start = System.currentTimeMillis();
int found = 0;
for (int i = 0; i < n; i++) {
if (bigMap.get(i) != null) found++;
}
long queryTime = System.currentTimeMillis() - start;
System.out.printf("插入 %d 条: %d ms%n", n, insertTime);
System.out.printf("查询 %d 条: %d ms%n", n, queryTime);
System.out.printf("命中率: %d/%d%n", found, n);
System.out.printf("重哈希次数: %d%n", bigMap.getRehashCount());
System.out.println("一致性验证: " + bigMap.validate());
// 与HashMap对比查询性能
System.out.println("\n=== 与Java HashMap查询对比 ===");
HashMap<Integer, String> jdkMap = new HashMap<>();
for (int i = 0; i < n; i++) jdkMap.put(i, "value_" + i);
start = System.currentTimeMillis();
for (int i = 0; i < n; i++) jdkMap.get(i);
long jdkQueryTime = System.currentTimeMillis() - start;
System.out.printf("CuckooHashMap查询: %d ms%n", queryTime);
System.out.printf("Java HashMap查询: %d ms%n", jdkQueryTime);
}
}
复杂度分析
| 指标 | 平均情况 | 最坏情况 | 说明 |
|---|---|---|---|
| 查询 | $O(1)$ | $O(1)$ | 只需检查两个固定位置 |
| 插入 | $O(1)$ | $O(n)$（触发扩容） | 踢出链平均长度 $O(1)$ |
| 删除 | $O(1)$ | $O(1)$ | 直接清空对应位置 |
| 空间利用率 | $\approx 45\%$ | — | 为保证低碰撞率需保留余量 |
理论保证
当负载因子 $\alpha < 0.5$ 且使用两个独立哈希函数时：
– 插入成功的概率趋近于1
– 踢出链的期望长度为 $O(1)$
– 扩容的期望次数为 $O(1)$
若使用 $d > 2$ 个哈希函数和对应数量的表，负载因子可提升至 $90\%$ 以上（如 $d=4$ 时可达 $97\%$）。
扩展思考
- 多路布谷鸟哈希：使用3+个哈希函数和表，显著提升空间利用率，但增加单次查询的内存访问次数（缓存不友好）
- d-left哈希：布谷鸟哈希的变体，每个桶容纳多个槽位，在SSD和分布式存储中广泛应用
- 并发布谷鸟哈希：通过细粒度锁或乐观并发控制实现线程安全，是高性能键值存储（如Memcached）的底层候选方案
总结
本文通过Java实现了布谷鸟哈希表，展示了多哈希函数与踢出链机制如何实现 $O(1)$ 最坏情况保证。与开放寻址法（可能退化为线性探测）和链地址法（查询需遍历链表）相比，布谷鸟哈希的查询确定性使其在实时系统和缓存设计中具有独特优势。代码中完整的踢出链检测、自动扩容和重哈希机制构成了生产级哈希表的基础框架，读者可进一步扩展为支持并发访问的高性能数据结构。
