Guava中Bloom过滤器

1. 概述

在本文中，我们将研究来自Guava库的Bloom 过滤器 构造。Bloom 过滤器 是一种内存效率高的概率数据结构，我们可以用它来回答给定元素是否在集合中的问题。

Bloom 过滤器没有假阴性，所以当它返回false时，我们可以 100% 确定该元素不在集合中。

但是，Bloom 过滤器可能会返回误报，因此当它返回true时，该元素很有可能在集合中，但我们不能 100% 确定。

要更深入地分析Bloom 过滤器的工作原理，您可以阅读本教程 。

2. Maven依赖

我们将使用 Guava 的 Bloom 过滤器实现，所以让我们添加guava依赖项：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

最新版本可以在Maven Central 上找到。

3. 为什么使用Bloom 过滤器？

Bloom 过滤器被设计为节省空间和快速。使用它时，我们可以**指定我们可以接受的误报响应的概率，**并且根据该配置，Bloom 过滤器将占用尽可能少的内存。

由于这种空间效率，即使对于大量元素，**Bloom 过滤器也很容易适应内存。**一些数据库，包括 Cassandra 和 Oracle，在进入磁盘或缓存之前使用此过滤器作为第一个检查，例如，当对特定 ID 的请求进入时。

如果过滤器返回 ID 不存在，则数据库可以停止进一步处理请求并返回给客户端。否则，它会转到磁盘并返回如果在磁盘上找到元素。

4. 创建Bloom 过滤器

假设我们要为多达 500 个整数创建一个Bloom 过滤器，并且我们可以容忍百分之一 (0.01) 的误报概率。

我们可以使用Guava库中的BloomFilter类来实现这一点。我们需要传递我们期望插入过滤器的元素数量和所需的误报概率：

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

现在让我们在过滤器中添加一些数字：

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

我们只添加了三个元素，并且我们定义了最大插入次数为 500，因此我们的 Bloom 过滤器应该会产生非常准确的结果。让我们使用*mightContain()*方法对其进行测试：

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

顾名思义，当方法返回true时，我们不能 100% 确定给定元素实际上在过滤器中。

在我们的示例中，当mightContain()返回true时，我们可以 99% 确定该元素在过滤器中，并且结果为误报的概率为 1%。当过滤器返回false时，我们可以 100% 确定该元素不存在。

5. 过度饱和的Bloom 过滤器

当我们设计我们的Bloom 过滤器时，重要的是我们为预期的元素数量提供一个合理准确的值。否则，我们的过滤器将返回比预期高得多的误报率。让我们看一个例子。

假设我们创建了一个过滤器，其期望的误报概率为 1%，预期的一些元素等于 5，但随后我们插入了 100,000 个元素：

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

因为预期的元素数量很少，过滤器将占用很少的内存。

但是，随着我们添加的项目比预期的多，过滤器变得过饱和，并且返回误报结果的概率比期望的 1% 高得多：

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

请注意，即使对于我们之前没有插入过滤器的值，maycontatin()方法也会**返回true 。**