其实在之前的文章中提到过bitmaps这种数据结构，【Redis从入门到放弃系列 十三】Redis的高级数据结构，其实有一种比bitmaps还要狠的方式，就是布隆过滤器。有如下场景可能需要用到：
- 邮箱系统的垃圾邮件过滤？
- 现有50亿个电话号码，现有10万个电话号码，如何要快速准确的判断这些电话号码是否已经存在？
- 1亿个用户，判断1000个黑名单用户
- 解决缓存穿透问题，判断key是否存在
诸如此类的大数问题。
布隆过滤器基本概念
布隆过滤器（Bloom Filter）是由Howard Bloom在1970年提出的一种比较巧妙的概率型数据结构，它可以告诉你某种东西一定不存在或者可能存在。
- 当布隆过滤器说，某种东西存在时，这种东西可能不存在
- 当布隆过滤器说，某种东西不存在时，那么这种东西一定不存在。
布隆过滤器相对于Set、Map 等数据结构来说，它可以更高效地插入和查询，并且占用空间更少，它也有缺点，就是判断某种东西是否存在时，可能会被误判。但是只要参数设置的合理，它的精确度也可以控制的相对精确，只会有小小的误判概率
布隆过滤器原理
Redis中布隆过滤器的数据结构就是一个很大的位数组和几个不一样的无偏哈希函数（能把元素的哈希值算得比较平均，能让元素被哈希到位数组中的位置比较随机）
- 向布隆过滤器中添加元素时，会使用多个无偏哈希函数对元素进行哈希，算出一个整数索引值，然后对位数组长度进行取模运算得到一个位置，每个无偏哈希函数都会得到一个不同的位置。再把位数组的这几个位置都设置为1，这就完成了bf.add命令的操作。
- 从布隆过滤器中获取元素时，和添加元素一样，也会把哈希的几个位置算出来，然后看看位数组中对应的几个位置是否都为1，只要有一个位为0，那么就说明布隆过滤器里不存在这个元素。如果这几个位置都为1，并不能完全说明这个元素就一定存在其中，有可能这些位置为1是因为其他元素的存在，这就是布隆过滤器会出现误判的原因
Redis中的BloomFilter使用
之前的布隆过滤器可以使用Redis中的bitmaps操作实现，直到Redis4.0版本提供了插件功能，Redis官方提供的布隆过滤器才正式登场。布隆过滤器作为一个插件加载到Redis Server中，就会给Redis提供了强大的布隆去重功能
布隆过滤器使用
在Redis中，布隆过滤器有两个基本命令，分别是：
- bf.add：添加元素到布隆过滤器中，类似于集合的sadd命令，不过
bf.add命令只能一次添加一个元素，如果想一次添加多个元素，可以使用bf.madd命令 - bf.exists：判断某个元素是否在过滤器中，类似于集合的sismember命令，不过
bf.exists命令只能一次查询一个元素，如果想一次查询多个元素，可以使用bf.mexists命令。
操作命令如下：
> bf.add name tml (integer) 1 > bf.add name tml2 (integer) 1 > bf.add name tml3 (integer) 1 > bf.exists name tml1 (integer) 1 > bf.exists name tml2 (integer) 1 > bf.exists name tml3 (integer) 1 > bf.exists name tml4 (integer) 0 > bf.madd name tml4 tml5 tml6 1) (integer) 1 2) (integer) 1 3) (integer) 1 > bf.mexists name tml4 tml5 tml6 tml7 1) (integer) 1 2) (integer) 1 3) (integer) 1 4) (integer) 0
上面的例子中，没有发现误判的情况，是因为元素数量比较少。当元素比较多时，可能就会发生误判，怎么才能减少误判呢？
如何减少误判
上面的例子中使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次使用bf.add命令时自动创建的。Redis还提供了自定义参数的布隆过滤器，想要尽量减少布隆过滤器的误判，就要设置合理的参数。
在使用bf.add命令添加元素之前，使用bf.reserve命令创建一个自定义的布隆过滤器。bf.reserve命令有三个参数，分别是：
- key：键
- error_rate：期望错误率，期望错误率越低，需要的空间就越大。同时需要的hash函数也越多
- capacity：初始容量，当实际元素的数量超过这个初始化容量时，误判率上升。
按照这个参数这么执行：
> bf.reserve name 0.0001 1000000 OK
如果对应的key已经存在时，在执行bf.reserve命令就会报错。如果不使用bf.reserve命令创建，而是使用Redis自动创建的布隆过滤器，默认的error_rate是 0.01，capacity是 100。
- 布隆过滤器的error_rate越小，需要的存储空间就越大，对于不需要过于精确的场景，error_rate设置稍大一点也可以。
- 布隆过滤器的capacity设置的过大，会浪费存储空间，设置的过小，就会影响准确率
所以在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出设置值很多。总之，error_rate和 capacity都需要设置一个合适的数值。
