什么是布隆过滤器？#

布隆过滤器的巨大作用 ，就是能够迅速判断一个元素是否存在一个集合中。因此次他有如下几个使用场景

• 网站爬虫对URL的去重，避免爬取相同的URL
• 反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否是垃圾邮件（同理，垃圾短信）
• 缓存穿透，将所有可能的数据缓存放到布隆过滤器中，当黑客访问不存在的缓存时，迅速返回避免缓存以及DB挂掉。

原理#

布隆过滤器其内部维护了一个全为0的bit数组，需要说明的是，布隆过滤器有一个误判的概念，误判率越低，则数组越长，所占空间越大。误判率越高则数组越小，所占的空间多少。

假设，根据误判率，我们生成一个10位的bit数组，以及2个hash函数 f1 和 f2，如下图所示：生成的数组的位数 和 hash函数的数量，我们不用去关心如何生成的，这是有数学论文进行验证。

然后我们输入一个集合，集合中包含 N1 和 N2，我们通过计算 f1(N1) = 2，f2(N1) = 5，则将数组下标为2 和下标为5的位置设置成1，就得到了下图

同理，我们再次进行计算 N2的值， f1(N2) = 3，f2(N2) = 6。得到如下所示的图

这个时候，假设我们有第三个数N3过来了，我们需要判断N3是否在集合 [N1,N2]中，我们需要做的操作就是，使用f1 和 f2 计算出数组中的地址

• 若值恰巧都位于上图的红色位置，我们认为 N3在集合 [N1,N2] 中
• 若值有一个不位于上图的红色部分，我们认为N3不在集合[N1,N2] 中

这就是布隆过滤器的计算原理

使用#

在java中使用布隆过滤器，我们需要首先引入依赖，布隆过滤器拥有Google提供的一个开箱即用的组件，来帮助我们实现布隆过滤器，其实布隆过滤器的核心思想其实并不难，难的是在于如何设计随机映射函数，到底映射几次，二进制向量设置多少比较合适。

1
<dependencies>
2
    <dependency>
3
        <groupId>com.google.guava</groupId>
4
        <artifactId>guava</artifactId>
5
        <version>22.0</version>
6
    </dependency>
7
</dependencies>

然后我们编写代码，测试某元素是否存在于百万元素集合中

1
    private static int size = 1000000;//预计要插入多少数据
2

3
    private static double fpp = 0.01;//期望的误判率
4

5
    private static BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);
6

7
    public static void main(String[] args) {
8
        //插入数据
9
        for (int i = 0; i < 1000000; i++) {
10
            bloomFilter.put(i);
11
        }
12
        int count = 0;
13
        for (int i = 1000000; i < 2000000; i++) {
14
            if (bloomFilter.mightContain(i)) {
15
                count++;
16
                System.out.println(i + "误判了");
17
            }
18
        }
19
        System.out.println("总共的误判数:" + count);
20
    }

代码分析#

上面的代码中，我们创建了一个布隆过滤器，其中有两个重要的参数，分别是我们要预计插入的数据和我们所期望的误判率，误判率率不能为0。

我们首先向布隆过滤器中插入 0 ~ 100万条数据，然后在用 100万 ~ 200万的数据进行测试

我们输出结果，查看一下误判率

1
1999501误判了
2
1999567误判了
3
1999640误判了
4
1999697误判了
5
1999827误判了
6
1999942误判了
7
总共的误判数:10314

现在有100万不存在的数据，误判了10314次，我们计算一下误判率

1
10314 / 1000000 = 0.010314

和我们之前定义的误判率为0.01相差无几