文章目录

原理
应用
实战
总结

布隆过滤器（Bloom Filter）是 1970 年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。
它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。

原理

在谈到原理之前，我们先来看看布隆过滤器的数据结构，它是一个bit数组。如下图所示：

这是一个长度为8，默认都是0的bit数组。如果我们想要映射一个值到布隆过滤器中，怎么操作呢？首先是使用多个不同的哈希函数生成多个哈希值，再把哈希值指向的bit位置1。例如：我们要将值“baidu”映射到布隆过滤器上，怎么操作呢？假如我们使用三个不同的哈希函数生成了三个哈希值分别是:1、3、6，那么上图就转变为下图这样：

从图中看出，标有浅蓝色的bit位的值都被置为1，表示该数据已经映射上了。接着我们再把值“alibaba”和三个不同哈希函数生成的值：2、6、8映射到上面布隆过滤器中，它就会变为下图的样子：

很显然，它把之前映射的哈希值6覆盖了，这就是布隆过滤器是有误报率的一个因素。如果这时候，我们想拿一个未插入映射的值“tencent”查询它是否在上面布隆过滤器中存在。该怎么操作呢？首先，把值“tencent”用上面三个不同哈希函数生成三个哈希值分别是：2、4、6；再去布隆过滤器上找这三个值对应的bit位的值是否都是1，我们发现2和6都返回了1，而4返回0，说明值“tencent”没有做过映射，即不存在。实际上我们并没有事先做过此值的插入映射操作。这当然是正确的。

总结：布隆过滤器的原理是，当一个元素被加入集合时，通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点（offset），把它们置为 1。检索时，我们只要看看这些点是不是都是 1 就（大约）知道集合中有没有它了：如果这些点有任何一个 0，则被检元素一定不在；如果都是 1，则被检元素很可能在。这就是布隆过滤器的基本思想。

简单来说就是准备一个长度为 m 的位数组并初始化所有元素为 0，用 k 个散列函数对元素进行 k 次散列运算跟 len(m)取余得到 k 个位置并将 m 中对应位置设置为 1。

SO：当我们搜索一个值的时候，若该值经过 K 个哈希函数运算后的任何一个索引位为 ”0“，那么该值肯定不在集合中。但如果所有哈希索引值均为 ”1“，则只能说该搜索的值可能存在集合中。

应用

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

网页爬虫对 URL 去重，避免爬取相同的 URL 地址；
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
Google Chrome 使用布隆过滤器识别恶意 URL；
Medium 使用布隆过滤器避免推荐给用户已经读过的文章；
Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆过滤器减少对不存在的行和列的查找。除了上述的应用场景之外，布隆过滤器还有一个应用场景就是解决缓存穿透的问题。所谓的缓存穿透就是服务调用方每次都是查询不在缓存中的数据，这样每次服务调用都会到数据库中进行查询，如果这类请求比较多的话，就会导致数据库压力增大，这样缓存就失去了意义。
解决缓存穿透

利用布隆过滤器我们可以预先把数据查询的主键，比如用户 ID 或文章 ID 缓存到过滤器中。当根据 ID 进行数据查询的时候，我们先判断该 ID 是否存在，若存在的话，则进行下一步处理。若不存在的话，直接返回，这样就不会触发后续的数据库查询。需要注意的是缓存穿透不能完全解决，我们只能将其控制在一个可以容忍的范围内。

实战

依赖：

<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 的值，需要的存储空间也越大，所以在实际使用过程中需要在误判率和存储空间之间做个权衡。

总结

本文主要介绍的布隆过滤器的概念和常见的应用场合，在实战部分我们演示了 Google 著名的 Guava 库所提供布隆过滤器（Bloom Filter）的基本使用，同时我们也介绍了布隆过滤器出现误报的原因及如何提高判断准确性。最后为了便于大家理解布隆过滤器，我们介绍了一个简易版的布隆过滤器 SimpleBloomFilter。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/162258.html