Bloom Filter介绍

原文

概览

这篇文章我们谈谈Guava中的Bloom Filter, Bloom Filter是一种省内存的基于概率的数据结构，可判断一个元素是否在集合中。

Bloom Filter没有False Negative,即判断某元素时否在Bloom Filter中时，如果返回False, 则可以肯定该元素不在集合中，但是Bloom Filter存在False Positive, 即如果返回True, 并不能完全肯定元素就在集合中，但是有很大的概率确实在集合中。

详细地了解Bloom Filter原理可参考这里。

Maven依赖

使用Guava实现的Bloom Filter可在pom中添加如下依赖

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>22.0</version>
</dependency>

这是目前最新版本。

为什么使用Bloom Filter

Bloom Filter既省空间，速度又快，使用的时候可以指定我们可以接受的False Positive误判率，Bloom Filter使用尽可能少的空间满足误判率的要求。

因为Bloom Filter占用空间很少，完全可以放入内存，即使是有大量的元素。一些database就使用了Bloom Filter，比如Cassandra、Oracle，当一个特殊的请求ID到达时，先通过Bloom Filter判断请求的内容是否存在，如果Bloom Filter返回False,则代表请求的内容肯定不存在，可直接返回，节省时间，如果返回True，则再去内存或磁盘中查找请求的数据，如果找到就返回，当然也有很小的概率找不到。

创建Bloom Filter

假如集合中最多有500个整数时，我们创建的Bloom Filter能接受的False Positive误判率为1%时，使用Guava创建Bloom Filter如下，

BloomFilter<Integer> filter = BloomFilter.create(
  Funnels.integerFunnel(),
  500,
  0.01);

须将集合元素上线数和误判率作为参数传入，现在可以向集合中添加元素：

filter.put(1);
filter.put(2);
filter.put(3);

集合中最多可添加500个元素，目前我么仅添加了3个，因此误判率应该为0。使用mightContain()方法检测元素是否在集合中：

assertThat(filter.mightContain(1)).isTrue();
assertThat(filter.mightContain(2)).isTrue();
assertThat(filter.mightContain(3)).isTrue();
 
assertThat(filter.mightContain(100)).isFalse();

就像方法的名字一样，mightContain返回True时并不能100%肯定元素一定在集合中。

在我们这个例子中，当mightContain返回True时，可以99%确定元素在集合中，有1%的False Positive误判率；当mightContain返回False时，可以100%肯定元素不在集合中。

Bloom Filter超载

设计Bloom Filter时，一定要预估一个合理的集合元素个数上限值，如果插入集合中元素个数超过了设定的上限值，False Positive的误判率会高出期望误判率很多。

看一个例子，假如创建一个预计上限为5, 期望False Positive误判率为1%的Bloom Filter, 但实际上我们插入了100，000个元素：

BloomFilter<Integer> filter = BloomFilter.create(
  Funnels.integerFunnel(),
  5,
  0.01);
 
IntStream.range(0, 100_000).forEach(filter::put);

我们预估的上限很小，Bloom Filter占用很小的内存空间，然而实际上我们插入的元素个数超过了预估上限，Filter超载了，False Positive误判率会高出1%很多：

assertThat(filter.mightContain(1)).isTrue();
assertThat(filter.mightContain(2)).isTrue();
assertThat(filter.mightContain(3)).isTrue();
assertThat(filter.mightContain(1_000_000)).isTrue();

也就是mightContain()会返回True即使我们没有在集合中插入该元素。

总结

这篇文章我们介绍了基于Guava实现的概率性数据结构Bloom Filter, 可以从GitHub上找到以上例子中的代码, 这是一个Maven项目，可以很容易的导入并允许起来。