算法概述
Cuckoo Filter 是 Fan 等人于 2014 年提出的概率型数据结构，作为布隆过滤器的现代替代品，支持高效的集合成员检测与动态删除。其核心思想源自布谷鸟哈希（Cuckoo Hashing）：每个元素通过两个哈希函数映射到两个候选桶，桶中存储指纹（fingerprint）而非完整元素。当插入导致桶满时，按布谷鸟策略”踢出”已有指纹并重新安置。
与布隆过滤器相比，Cuckoo Filter 支持删除操作、查询性能更稳定（最坏 O(1)），且在相同假阳性率下通常更节省空间。
核心原理
- 指纹提取：对元素计算哈希，取高若干位作为指纹（如 8~16 位）。
- 双桶定位：
- 桶1 = hash(element)
- 桶2 = 桶1 xor hash(fingerprint)
- 插入策略：优先放入空位；若两桶均满，随机踢出一个已有指纹，被踢出的指纹按同样规则寻找新的安置桶。
- 查询策略：检查两个候选桶中是否存在目标指纹。
- 删除策略：从两个候选桶中移除一个匹配的指纹（注意可能误删不同元素的相同指纹）。
Java 实现
import java.nio.charset.StandardCharsets;
import java.util.Random;
/**
* Cuckoo Filter 布谷鸟过滤器实现
* 支持插入、查询、删除操作
* 假阳性率取决于指纹长度和桶大小
*/
public class CuckooFilter {
// 每个桶的槽位数
private static final int BUCKET_SIZE = 4;
// 最大踢出次数，防止无限循环
private static final int MAX_KICKS = 500;
// 指纹位数（8~16 位推荐）
private final int fingerprintBits;
// 指纹掩码
private final int fingerprintMask;
// 桶数组，每个桶有 BUCKET_SIZE 个槽位，存储指纹（0 表示空）
private final int[][] buckets;
// 桶数量（2 的幂次便于取模）
private final int numBuckets;
// 当前元素计数
private int count;
// 随机数生成器，用于踢出选择
private final Random random;
/**
* 构造函数
* @param capacity 期望容纳的元素数量
* @param fingerprintBits 指纹位数，越大假阳性率越低
*/
public CuckooFilter(int capacity, int fingerprintBits) {
if (fingerprintBits < 4 || fingerprintBits > 16) {
throw new IllegalArgumentException("指纹位数应在 4~16 之间");
}
this.fingerprintBits = fingerprintBits;
this.fingerprintMask = (1 << fingerprintBits) - 1;
// 桶数量向上取整为 2 的幂次
this.numBuckets = Integer.highestOneBit(
Math.max(capacity / BUCKET_SIZE * 2, 1)) << 1;
this.buckets = new int[numBuckets][BUCKET_SIZE];
this.count = 0;
this.random = new Random(42);
}
/**
* MurmurHash3 32 位版本
*/
private int hash(String data) {
byte[] bytes = data.getBytes(StandardCharsets.UTF_8);
int h = 0x12345678;
int len = bytes.length;
int len4 = len / 4;
for (int i = 0; i < len4; i++) {
int idx = i * 4;
int k = (bytes[idx] & 0xff)
| ((bytes[idx + 1] & 0xff) << 8)
| ((bytes[idx + 2] & 0xff) << 16)
| ((bytes[idx + 3] & 0xff) << 24);
k *= 0xcc9e2d51;
k = Integer.rotateLeft(k, 15);
k *= 0x1b873593;
h ^= k;
h = Integer.rotateLeft(h, 13);
h = h * 5 + 0xe6546b64;
}
// 剩余字节
int k = 0;
switch (len % 4) {
case 3: k ^= (bytes[len4 * 4 + 2] & 0xff) << 16;
case 2: k ^= (bytes[len4 * 4 + 1] & 0xff) << 8;
case 1: k ^= (bytes[len4 * 4] & 0xff);
k *= 0xcc9e2d51;
k = Integer.rotateLeft(k, 15);
k *= 0x1b873593;
h ^= k;
}
h ^= len;
h ^= h >>> 16;
h *= 0x85ebca6b;
h ^= h >>> 13;
h *= 0xc2b2ae35;
h ^= h >>> 16;
return h;
}
/**
* 计算指纹
*/
private int fingerprint(String item) {
return (hash(item) & fingerprintMask) | 1; // 确保指纹不为 0
}
/**
* 计算候选桶索引
*/
private int index(String item) {
return (hash(item) & 0x7fffffff) % numBuckets;
}
/**
* 计算备用桶索引
*/
private int alternateIndex(int idx, int fp) {
// idx xor hash(fp)
int h = (fp * 0x5bd1e995) ^ (fp >>> 16);
return (idx ^ (h & 0x7fffffff)) % numBuckets;
}
/**
* 向过滤器中插入元素
* @param item 待插入的字符串
* @return 插入成功返回 true，空间不足返回 false
*/
public boolean insert(String item) {
if (contains(item)) return true;
int fp = fingerprint(item);
int i1 = index(item);
int i2 = alternateIndex(i1, fp);
// 尝试放入两个候选桶
if (addToBucket(i1, fp)) { count++; return true; }
if (addToBucket(i2, fp)) { count++; return true; }
// 两桶均满，随机选择一个桶踢出
int i = random.nextBoolean() ? i1 : i2;
for (int n = 0; n < MAX_KICKS; n++) {
int j = random.nextInt(BUCKET_SIZE);
int oldFp = buckets[i][j];
buckets[i][j] = fp;
fp = oldFp;
i = alternateIndex(i, fp);
if (addToBucket(i, fp)) { count++; return true; }
}
return false; // 插入失败
}
/**
* 将指纹放入指定桶的空槽
*/
private boolean addToBucket(int bucketIdx, int fp) {
int[] bucket = buckets[bucketIdx];
for (int i = 0; i < BUCKET_SIZE; i++) {
if (bucket[i] == 0) {
bucket[i] = fp;
return true;
}
}
return false;
}
/**
* 查询元素是否可能存在于集合中
* @param item 待查询元素
* @return true 表示可能存在，false 表示一定不存在
*/
public boolean contains(String item) {
int fp = fingerprint(item);
int i1 = index(item);
int i2 = alternateIndex(i1, fp);
return bucketContains(i1, fp) || bucketContains(i2, fp);
}
/**
* 检查桶中是否包含指定指纹
*/
private boolean bucketContains(int bucketIdx, int fp) {
for (int f : buckets[bucketIdx]) {
if (f == fp) return true;
}
return false;
}
/**
* 从过滤器中删除元素
* @param item 待删除元素
* @return 删除成功返回 true
*/
public boolean delete(String item) {
int fp = fingerprint(item);
int i1 = index(item);
int i2 = alternateIndex(i1, fp);
if (removeFromBucket(i1, fp) || removeFromBucket(i2, fp)) {
count--;
return true;
}
return false;
}
/**
* 从桶中移除一个匹配指纹
*/
private boolean removeFromBucket(int bucketIdx, int fp) {
int[] bucket = buckets[bucketIdx];
for (int i = 0; i < BUCKET_SIZE; i++) {
if (bucket[i] == fp) {
bucket[i] = 0;
return true;
}
}
return false;
}
/**
* 获取当前元素数量
*/
public int size() {
return count;
}
@Override
public String toString() {
return "CuckooFilter(count=" + count + ", buckets=" + numBuckets +
", fpBits=" + fingerprintBits + ")";
}
// ==================== 测试入口 ====================
public static void main(String[] args) {
CuckooFilter filter = new CuckooFilter(10000, 12);
// 插入测试
int insertCount = 5000;
for (int i = 0; i < insertCount; i++) {
if (!filter.insert("item_" + i)) {
System.out.println("插入失败于 i=" + i);
break;
}
}
System.out.println("插入完成，当前数量: " + filter.size());
// 查询测试（应全部命中）
int falseNegatives = 0;
for (int i = 0; i < insertCount; i++) {
if (!filter.contains("item_" + i)) falseNegatives++;
}
System.out.println("假阴性（漏报）: " + falseNegatives);
// 查询未插入元素（统计假阳性）
int falsePositives = 0;
for (int i = insertCount; i < insertCount + 5000; i++) {
if (filter.contains("item_" + i)) falsePositives++;
}
System.out.println("假阳性（误报）: " + falsePositives +
", 率=" + (falsePositives * 100.0 / 5000) + "%");
// 删除测试
for (int i = 0; i < 1000; i++) {
filter.delete("item_" + i);
}
System.out.println("删除后数量: " + filter.size());
// 验证删除后不再包含
int stillContains = 0;
for (int i = 0; i < 1000; i++) {
if (filter.contains("item_" + i)) stillContains++;
}
System.out.println("删除后仍被查询到: " + stillContains +
" (因指纹冲突可能不为 0)");
}
}
复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| insert | 均摊 O(1) | O(1) |
| contains | O(1) | O(1) |
| delete | O(1) | O(1) |
空间占用约为 numBuckets * BUCKET_SIZE * fingerprintBits 位，比同假阳性率的布隆过滤器更紧凑。
适用场景
- 需要支持删除的缓存过滤（如 CDN 缓存淘汰）
- 数据库查询优化中的布隆过滤替代
- 分布式系统中的去重与集合同步
- 网络数据包过滤与黑名单检测
