- 布隆过滤器
三、布隆过滤器实战
布隆过滤器有很多实现和优化，由 Google 开发著名的 Guava 库就提供了布隆过滤器（Bloom Filter）的实现。在基于 Maven 的 Java 项目中要使用 Guava 提供的布隆过滤器，只需要引入以下坐标：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>28.0-jre</version>
</dependency>
在导入 Guava 库后，我们新建一个 BloomFilterDemo 类，在 main 方法中我们通过 BloomFilter.create 方法来创建一个布隆过滤器，接着我们初始化 1 百万条数据到过滤器中，然后在原有的基础上增加 10000 条数据并判断这些数据是否存在布隆过滤器中：
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterDemo {
public static void main(String[] args) {
int total = 1000000; // 总数量
BloomFilter<CharSequence> bf =
BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
// 初始化 1000000 条数据到过滤器中
for (int i = 0; i < total; i++) {
bf.put("" + i);
}
// 判断值是否存在过滤器中
int count = 0;
for (int i = 0; i < total + 10000; i++) {
if (bf.mightContain("" + i)) {
count++;
}
}
System.out.println("已匹配数量 " + count);
}
}
当以上代码运行后，控制台会输出以下结果：
已匹配数量 1000309
很明显以上的输出结果已经出现了误报，因为相比预期的结果多了 309 个元素，误判率为：
309/(1000000 + 10000) * 100 ≈ 0.030594059405940593
如果要提高匹配精度的话，我们可以在创建布隆过滤器的时候设置误判率 fpp：
BloomFilter<CharSequence> bf = BloomFilter.create(
Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002
);
在 BloomFilter 内部，误判率 fpp 的默认值是 0.03：
// com/google/common/hash/BloomFilter.class
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
return create(funnel, expectedInsertions, 0.03D);
}
在重新设置误判率为 0.0002 之后，我们重新运行程序，这时控制台会输出以下结果：
已匹配数量 1000003
通过观察以上的结果，可知误判率 fpp 的值越小，匹配的精度越高。当减少误判率 fpp 的值，需要的存储空间也越大，所以在实际使用过程中需要在误判率和存储空间之间做个权衡。
参考链接：
https://zhuanlan.zhihu.com/p/94433082
- 字符串匹配（KMP算法）
https://blog.csdn.net/dark_cy/article/details/88698736
- 贪心算法
https://blog.csdn.net/effective_coder/article/details/8736718
https://www.cnblogs.com/xsyfl/p/6938642.html
