简介
布隆过滤器适合大数据判重的场景，如网络爬虫中判断一个URL是否已经爬取过，判断一个用户是否在黑名单中，判断一个邮件是否是垃圾邮件，等等。
优点：占用空间小，效率高，简而言之，就是以正确率换空间和时间。
缺点：有一定的误判率，一个URL经过布隆过滤器判断没爬取过，那么一定没爬取过，一个URL经过布隆过滤器判断爬取过，可能并没有爬取过，这种情况会有误判。
布隆过滤器本身是基于位图的，是对位图的一种改进，位图在java中的实现就是BitSet。
简单使用
java中的Guava工具包提供了BloomFilter的实现。
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>27.1-jre</version>
</dependency>
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.util.ArrayList;
import java.util.List;
public class Client {
public static void mainString[] args) {
int size = 1_000_000;
BloomFilter<Integer> bloomFilter = BloomFilter.createFunnels.integerFunnel), size);
for int i = 0; i < size; i++) {
bloomFilter.puti);
}
for int i = 0; i < size; i++) {
if !bloomFilter.mightContaini)) {
System.out.println"有坏人逃脱了");
}
}
List<Integer> list = new ArrayList<>1000);
for int i = size + 10000; i < size + 20000; i++) {
if bloomFilter.mightContaini)) {
list.addi);
}
}
System.out.println"有误伤的数量：" + list.size));
}
}
输出结果为
有误伤的数量：330
可以看到，不会有坏人逃脱，但会有误伤，误伤率大概为3%。
这种情况下大概要使用内存为7298440bit，约0.87M。
我们将误伤率改为0.0003
BloomFilter<Integer> bloomFilter = BloomFilter.createFunnels.integerFunnel), size, 0.0003);
误伤数量为2，使用内存为16883499bit，约2.013M。
