什么是布隆过滤器（BloomFilter）？

关于

布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。

布隆过滤器可以用于检索一个元素是否可能在一个集合中。

• 优点：空间效率和查询时间都比一般的算法要好的多，
• 缺点：有一定的误识别率，不能删除。
  • 其变种“Counting Bloom filter”可以用来测试元素计数个数是否绝对小于某个阈值，它支持元素删除。

通常判断某个元素是否存在用的是什么？

HashMap！

将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内返回结果，效率奇高。

但是 HashMap 的实现也有缺点，例如存储容量占比高：

考虑到负载因子的存在，通常空间是不能被用满的，而数据量大的时候，HashMap 占据的内存大小就变得很可观了。

由此就需要一种查询效率近似 HashMap，但空间占用更少的结构来进行大数据量的判断。

原理

布隆过滤器是一个 bit 向量或者说 bit 数组（仅包含 0 或 1 值）：

要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并将每个哈希值所指向的 bit 位置为 1：

如下，添加元素“semlinker”：

如下，添加元素“kakuqo”：

在进行元素判定时，同样通过多个哈希函数生成多个哈希值，并查找哈希值所指向的 bit 位：

如下，查找元素“semlinker”：

如下，查找元素“fullstack”：

查找元素“bullshit”：

可以看出，判定结果为：元素“semlinker”、“fullstack”都在集合中，“bullshit”不在集合中。

但是其实“fullstack”并不在其中，是误报。

• 产生误报的原因是由于哈希碰撞导致的巧合而将不同的元素存储在相同的比特位上。

如上，可以看出 Bloom Filter 的判定结果：

1. 哈希值比特位都为 1，元素可能在集合中；
2. 哈希值比特位有 0，元素一定不在集合中。

即，布隆过滤器用于检索一个元素是否可能在一个集合中。

“布隆过滤器长度”（m）和“哈希函数个数”（k）

“布隆过滤器长度”与“哈希函数个数”直接影响 Bloom Filter 的效率：

• 布隆过滤器的长度会直接影响误报率：布隆过滤器越长其误报率越小。

  布隆过滤器长度过小，则很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了；

• 哈希函数的个数则需要在效率与误报率间平衡：

  个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

以：k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率，其关系如下：

极端情况下，当布隆过滤器没有空闲空间时（满），每一次查询都会返回 true 。这也就意味着 m 的选择取决于期望预计添加元素的数量 n ，并且 m 需要远远大于 n 。

实际情况中，以如下公式确定 k、m：

而误报率也可由公式得到：

应用

在实际工作中，布隆过滤器常见的应用场景如下：

• 网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
• 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；【邮箱配置中常见】
• Google Chrome 使用布隆过滤器识别恶意 URL；
• Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
• Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。

除了上述的应用场景之外，布隆过滤器还有一个应用场景就是解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。

• 需要注意的是缓存穿透不能完全解决，我们只能将其控制在一个可以容忍的范围内。

布隆过滤器实战

布隆过滤器有很多实现和优化，由 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 的值，需要的存储空间也越大，所以在实际使用过程中需要在误判率和存储空间之间做个权衡。