布隆过滤器的数据结构
布隆过滤器是一个 bit 向量或者说 bit 数组，长这样：
如果我们要把一个key映射到布隆过滤器中，就需要利用所有哈希函数对这个key进行映射，得到一系列的哈希值，把这些哈希值当成数据下标，把下标对应的数组元素置为1。
假设现在对对肯德基的菜单进行构建布隆过滤器：
首先，现在我们把“汉堡”这个key映射到布隆过滤器中，通过哈希函数映射的结果为1和7，我们现在把对应的bit元素标志为1。
Ok，我们现在再存一个值 “鸡腿”，如果哈希函数返回2和5的话，图继续变为：
image
接着我们想要查询某个key是不是在布隆过滤器中，只需要再通过哈希函数或者一系列的哈希值，然后把这些哈希值作为数组下标查看对应的元素是否为1。
这里有两种情况：
1. 不是所有位置都为1，肯定不在布隆过滤器中
瞧，如果我们要查询“可乐“这个key是否在布隆过滤器中的时候，发现通过哈希函数2映射的结果6对应的bit位是0。
因为如果“可乐”这个key如果在过滤器中的话，下标为2和6的bit位肯定都是1.所以我们可以很肯定的说，”可乐”这个key不在布隆过滤器中。
2.所有位置的bit位都是1，可能在布隆过滤器中
如果我们要查询“鸡肉卷”这个key是不是在布隆过滤器中的时候，发现通过哈希函数获得的哈希值所对应的bit都被置为1了，那这个值是不一定在布隆过滤器中的，为什么呢？
布隆过滤器的缺点
因为哈希函数可能是存在冲突的。在发生冲突的情况下，如果刚好所有的值都被置为1了，就会产生误判。为了能做到在时间和空间上的高效率，布隆过滤器牺牲了判断的准确率。所以对于不能接受误判的业务场景，通常需要在通过布隆过滤器之后再做一层判断。
另外布隆过滤器还有一个缺点就是删除比较困难，假如要删除一个key的话，不能简单的把这个key映射到的bit位都简单的置为0，因为哈希冲突的情况下，会影响其它key的判断。如果要删除的话，可以参考Counting Bloom Filter。
如何控制布隆过滤器的准确率
首先。布隆过滤器如果太小的话， bit 很快就会被全置为1，不论查询什么，结果都是“可能存在”，就起不到过滤效果了。所以布隆过滤器的长度会直接影响准确率，长度越长，准确率越高。
另外，哈希函数的个数也会影响布隆过滤器的准确率。哈希函数越多的话，对每个key进行映射的时候，被置为1的bit位也就越多，也会很快就把布隆过滤器打满。
假设我们的预估数据量为n，期望的误判率为fpp的话，bit数组大小和哈希函数个数k可以通过以下公式计算得到：
实战：使用Guava提供的布隆过滤器
首先需要引入依赖，在pom里面加上：
<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>29.0-jre</version>
</dependency>
然后测试一下误判率：
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterTest {
public static void main(String[] args) {
int total = 100000; //总数量
BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total);
// 初始化数据到布隆过滤器中
for (int i = 0; i < total; i++) {
bf.put(i);
}
// 判断值是否存在过滤器中
int count = 0;
for (int i = total; i < total + 10000; i++) {
if (bf.mightContain(i)) {
count++;
}
}
System.out.println("误判的数量 ～ " + count);
}
}
可以看到测试结果中，有286个元素不在布隆过滤器中，却被误判了。误判率= 281/10000 = 0.0281。
翻一下源码，可以看到误判率的默认值为0.03，和我们的测试结果差不多。
public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long expectedInsertions) {
return create(funnel, expectedInsertions, 0.03D);
}
然后我们修改误判率为0.01，再进行测试：
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterTest {
public static void main(String[] args) {
int total = 100000; //总数量
BloomFilter<Integer> bf = BloomFilter.create(Funnels.integerFunnel(), total, 0.01);
// 初始化数据到布隆过滤器中
for (int i = 0; i < total; i++) {
bf.put(i);
}
// 判断值是否存在过滤器中
int count = 0;
for (int i = total; i < total + 10000; i++) {
if (bf.mightContain(i)) {
count++;
}
}
System.out.println("误判的数量 ～ " + count);
}
}
可以看到误判率为93/10000 = 0.0093，差不多约等于我们期望的0.0.1。
布隆过滤器的其他使用场景
1. 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱
2. 爬虫过滤已抓到的url就不再抓，可用bloom filter过滤
3. Google Chrome 使用布隆过滤器识别恶意 URL
4. 使用布隆过滤器避免推荐给用户已经读过的文章/视频
网友评论