一、布隆过滤器原理

如果想要判断一个元素是不是在一个集合中存在，一般的想法是将所有元素保存起来，然后再拿着这个元素在集合中一个一个进行比对。但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢。 针对这种需要在大量数据中去判断某一个值是事否存在的情况，1970年由布隆提出了布隆过滤器的概念。布隆过滤器本质是一个位数组，位数组就是数组的每个元素都只占用 1 bit 。每个元素只能是 0 或者 1。这样申请一个 10000 个元素的位数组只占用 10000 / 8 = 1250 字节 的空间。布隆过滤器除了一个位数组，还有 n个哈希函数。

它具体的实现思想是并不将具体的数据存储在数组中，而是通过hash函数对要存储的数据进行三次hash运算，并将hash运算的结果做为位数组的下标，将对应的数组元素修改为1。

例如：我们要将"oracle"、"database"、"filter"存储到布隆过滤器中可以这样做。如下图所示

从上图中可以看到，我们有三个hash函数（h1()、h2()、h3()）和一个位数组，oracle经过三个hash函数，得到第1、4、5位为1，database同理得到2、5、10位1，这样如果我们需要判断oracle是否在此位数组中，则通过hash函数判断位数组的1、4、5位是否均为1，如果均为1，则判断oracle在此位数组中，database同理。这就是布隆过滤器判断元素是否在集合中的原理。

但同学们也会发现，如果我们现在要判断"mysql"是否存在，例如它通过三次hash运算得到的值分别是4,5,10。现在即使你的位数中没有存储“mysql”,布隆过滤器也会判断它存在。这是因为"oracle"、"database"、"filter"算出的hash值已经导致上面的三个位置的值被改为了1，这样就会导致误判。但是可以保证的是，如果布隆过滤器判断一个元素不在一个集合中，那这个元素一定不会再集合中。

产生上面误判的主要原因是hash碰撞导致的。但如果我们将位数组设置的足够大，并且让hash运算执行的次数多一些，这样就会降低误判率。

布隆过率器还有另一个问题就是不能删除。这是因为在位数组上的同一个点有可能有多个输入值的映射，如果删除了会影响布隆过滤器里其他元素的判断结果。

所以我们可以总结出布隆过滤器的优缺点如下：

• 优点：
• 所占空间小（并不存储真正的数据），空间效率高
• 查询时间短
• 缺点:
• 元素添加到数组中后，不能被删除
• 有一定的误判率

二、布隆过滤器使用场景

• 解决缓存穿透问题，缓存穿透是指查询一个一定不存在的数据，由于缓存是不命中就到数据库中去查，并且出于容错考虑，如果从数据库中查不到数据则不写入缓存，这将导致这个不存在的数据每次请求都要到数据库中去查询，失去了缓存的意义。在流量大时，可能数据库就挂掉了，要是有人利用不存在的key频繁攻击我们的应用，这就是漏洞。这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则再到数据库中查。如果不在布隆器中，则直接返回
• 在业务场景中可以用来判断用户是否阅读过某些文章或视频，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。
• 黑名单：比如在邮件系统中可以使用布隆器设置黑名单，判断邮件地址是否在黑名单中。也可以设IP黑名单防止网格爬虫等。
• 垃圾邮件过滤，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱。

三、实践

3.1通过 Java 编程手动实现布隆过滤器

package com.heima.rbac.controller;

import java.util.BitSet;

public class MyBloomFilter {

    /**
     * 位数组的大小
     */
    private static final int DEFAULT_SIZE = 2 << 24;
    /**
     * 通过这个数组可以创建 6 个不同的哈希函数
     */
    private static final int[] SEEDS = new int[]{5, 17, 48, 73, 93, 132};

    /**
     * 位数组。数组中的元素只能是 0 或者 1
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);

    /**
     * 存放包含 hash 函数的类的数组
     */
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    /**
     * 初始化多个包含 hash 函数的类的数组，每个类中的 hash 函数都不一样
     */
    public MyBloomFilter() {
        // 初始化多个不同的 Hash 函数
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    /**
     * 添加元素到位数组
     */
    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    /**
     * 判断指定元素是否存在于位数组
     */
    public boolean contains(Object value) {
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    /**
     * 静态内部类。用于 hash 操作！
     */
    public static class SimpleHash {

        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        /**
         * 计算 hash 值
         */
        public int hash(Object value) {
            int h;
            return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16)));
        }

    }
}

3.2Redis 中的布隆过滤器

redis 在 4.0 的版本中加入了 module 功能，布隆过滤器可以通过 module 的形式添加到 redis 中，所以使用 redis 4.0 以上的版本可以通过加载 module 来使用 redis 中的布隆过滤器。但是这不是最简单的方式，使用 docker 可以直接在 redis 中体验布隆过滤器。

> docker run -d -p 6379:6379 --name bloomfilter redislabs/rebloom

> docker exec -it bloomfilter redis-cli

redis 布隆过滤器主要就两个命令：

• bf.add 添加元素到布隆过滤器中：bf.add urls http://www.itcast.com。
• bf.exists 判断某个元素是否在过滤器中：bf.exists urls http://www.itcast.com。

上面说过布隆过滤器存在误判的情况，在 redis 中有两个值决定布隆过滤器的准确率：

• error_rate：允许布隆过滤器的错误率，这个值越低过滤器的位数组的大小越大，占用空间也就越大。
• initial_size：布隆过滤器可以储存的元素个数，当实际存储的元素个数超过这个值之后，过滤器的准确率会下降。

redis 中有一个命令可以来设置这两个值：

bf.reserve urls 0.01 100

三个参数的含义：

• 第一个值是过滤器的名字。
• 第二个值为 error_rate 的值。
• 第三个值为 initial_size 的值。

使用这个命令要注意一点：执行这个命令之前过滤器的名字应该不存在，如果执行之前就存在会报错：(error) ERR item exists