Why

布谷过滤器可以用来和 布隆过滤器一样快速、高性能的检测某一个内容是否已经存在，相对于布隆过滤器来说，布谷过滤器的优点在于更快、支持删除。

原理

布谷过滤器非常类似布隆过滤器，一样是将要处理的内容映射为hash值，并在一个表格中判断hash值是否存在。相应的因为hash碰撞，一样存在误判的可能。

布谷过滤器通过布谷散列实现，一般会生成两张表用来存放内容的hash值。

比如：A被put进来的时候，在第一张表某一个位置映射了hash(A)，当同样hash值的hash(B)被加入进来的，因为和A位置冲突了，A会自动被替到第二张表的hash(𝑓𝑖𝑛𝑔𝑒𝑟𝑝𝑟𝑖𝑛𝑡(A))位置上

这样不管判断hash(A)或者hash(𝑓𝑖𝑛𝑔𝑒𝑟𝑝𝑟𝑖𝑛𝑡(A))位置上有人，就可以判断出A存在布谷散列中

Demo

项目中引入依赖

1
2
3
4
5

 <dependency>
    <groupId>com.github.mgunlogson</groupId>
    <artifactId>cuckoofilter4j</artifactId>
    <version>1.0.1</version>
</dependency>

测试代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

 CuckooFilter<Integer> filter = new CuckooFilter.Builder<>(Funnels.integerFunnel(), 2000000).build();
// insert
if (filter.put(42)) {
    System.out.println("Insert Success!");
}
// contains
if (filter.mightContain(42)) {
    System.out.println("Found 42!");
}


if (filter.put(422)) {
    System.out.println("Insert Success!");
}
// count
System.out.println("Filter has " + filter.getCount() + " items");

// count
System.out.println("42 has been inserted approximately " + filter.approximateCount(42) + " times");

// % loaded
System.out.println("Filter is " + String.format("%.0f%%", filter.getLoadFactor() * 100) + " loaded");

// delete
if (filter.delete(42)) {
    System.out.println("Delete Success!");
}
if (filter.mightContain(42)) {
    System.out.println("Found 42!");
}