布隆过滤器（Bloom Filter）详解

布隆过滤器是由 Burton Bloom 在 1970 年提出，因此也称为 Bloom Filter。

• 作用

• 判断一个元素是否在一个集合

• 实现

• 通过一个很长的二进制向量和一系列的随机映射函数实现

• 优点

• 插入/查询速度快，且有较好的时间和空间效率。时间/空间复杂度都是常量 O(K)

• 缺点

• 有误算率：判定不存在则一定不存在，判定存在则可能实际不存在。随着插入元素数量增加，误算率也增大

• 不能进行删除

• 使用场景

• 防止缓存击穿

• Web 拦截器

• 网页爬虫对 URL 去重

• 反垃圾邮件，判断某个邮箱是否是垃圾邮

• ......

1. 实现原理

当需要判断一个元素是否在某个集合中时，我们首先想到的是使用集合类（链表、树、散列表等）来实现。但是使用集合类，我们是直接将所有元素保存在集合中，随着集合中元素数量的增加，集合所需要的存储空间也会线性增长，同时查询速度也会越来越慢。

使用数组或列表时，插入项的位置和要插入的值没有对应关系，这样当需要查找某个值时就必须遍历已有的元素；当数组或列表中存在的元素数据很多时，就会影响查询效率。

针对上述数组查询问题，我们改为使用哈希表。哈希表通过对“值”进行哈希计算，然后模哈希桶大小，得到存放该值的列表索引位置。查询时根据值的哈希值快速定位到存放该值的索引位置，然后在索引位置列表中进行查找该值是否存在，这样缩小了查询范围，提高了查询的效率。因为我们是将所有值存放在哈希表中，所以当存放值的数量变多时，会占用大量的存储空间，从而影响查询效率或者发生内存溢出。

这时，我们可以使用布隆过滤器（Bloom Filter）。不管是集合类还是布隆过滤器，都用到了哈希函数（Hash Function），我们先来看看哈希函数的定义。

哈希函数

哈希函数，也称为散列函数，给定一个输入值 x，那么经过哈希函数计算输出 H(x)，这个计算结果我们称为哈希值或者散列值。哈希函数具有以下特征：

• 输入 x 可以任意长度

• 输出结果 H(x) 的长度固定

• 计算 H(x) 过程高效，长度为 n 的 x，H(x) 的时间复杂度应为 O(n)

• 单向散列：当两个散列值不相同时，那么计算它们的输入值一定也不相同

• 散列碰撞：当两个散列值相同，但是计算它们的输入值不相同时，我们称这种情况为散列碰撞

• 隐匿性：通过 H(x) 结果，不能从计算上逆向推导出 x，不存在比穷举法更好的方法

布隆过滤器数据结构

布隆过滤器（Bloom Filter）本质上是一个长度为 m 的位向量或位列表，仅包含二进制的 0 或 1。最初所有的值均为 0。

为了减少哈希碰撞，布隆过滤器使用 K 个不同的哈希函数，并将哈希结果对应的位置为 1。

如上图所示：当输入 January 时，通过设置当 3 个哈希函数计算得到索引位置 1、4、6，我们将这 3 个索引位置置为 1。

然后再输入 February，根据哈希函数得到索引位置 1、5、8。因为索引位 1 上已经是 1，因此只需要将 5、8 索引位置 1。

当查询某个值是否存在时，同样通过设置的哈希函数计算出索引位置，如果相应索引位置上都是 1 则说明该值已存在（存在误判的情况），否则该值一定不存在。

布隆过滤器为什么不能删除？如上所示，我们如果删除 February，则将索引位置 1、5、8 置 0。此时我们再来判断查询 January 是否存在，因为索引位 1 已经置 0，根据判断规则，则判定 January 不存在。因此在布隆过滤器中删除元素会导致其他已存在元素的误判。

2. Guava Bloom Filter 实现

Google 的 Guava 库中提供了 Bloom Filter 的实现。我们使用它来实现一个从 1000 万数据中判断随机的 10000 条数据是否存在。

- 引入 guava 库

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

- 代码示例

import com.google.common.base.Charsets;import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels;
import java.util.Random;
public class BloomFilterDemo {
    public static void main(String[] args) {        // 放入 1000 万条数据        int total = 10000000;        BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);        for (int i = 0; i < total; i++) {            bloomFilter.put("" + i);        }
        // 随机查找 10000 个数        long startTime = System.currentTimeMillis();        int count1 = 0;        int count2 = 0;        for (int i = 0; i < 10000; i++) {            int num = new Random().nextInt(100000000);            if (num < total) {                count1++;            }            String numStr = num + "";            if (bloomFilter.mightContain(numStr)) {                count2++;            }        }        System.out.println("匹配数据:" + count2 + "条，耗时" + (System.currentTimeMillis() - startTime) + "ms");        if (count1 != count2) {            System.out.println("误判:" + Math.abs(count2 - count1) + "条");        }    }
}

- 代码输出

匹配数据:1276条，耗时9ms误判:286条

如上代码所示，布隆过滤器存在误判率，使用 Guava Bloom Filter 时，我们可以在创建布隆过滤器时设置误判率 FPP 来提高匹配准确度。如将上述代码中 BloomFilter 的创建语句改为：

BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total, 0.0001);

Guava BloomFilter 默认误判率 fpp 为 `0.03D`，fpp 越小，匹配精度越高，相应的需要的存储空间越大，所以在实际应用中根据实际业务情况在误判率和存储空间之间选取一个合适的值。