网友回复
什么是布隆过滤器
布隆过滤器（Bloom Filter）是由Howard Bloom在1970年提出的一种比较巧妙的概率型数据结构，它可以告诉你某种东西一定不存在或者可能存在。当布隆过滤器说，某种东西存在时，这种东西可能不存在；当布隆过滤器说，某种东西不存在时，那么这种东西一定不存在。 布隆过滤器相对于Set、Map 等数据结构来说，它可以更高效地插入和查询，并且占用空间更少，它也有缺点，就是判断某种东西是否存在时，可能会被误判。但是只要参数设置的合理，它的精确度也可以控制的相对精确，只会有小小的误判概率。Redis中布隆过滤器
之前的布隆过滤器可以使用Redis中的位图操作实现，直到Redis4.0版本提供了插件功能，Redis官方提供的布隆过滤器才正式登场。布隆过滤器作为一个插件加载到Redis Server中，就会给Redis提供了强大的布隆去重功能。布隆过滤器的基本使用
在Redis中，布隆过滤器有两个基本命令，分别是：bf.add：添加元素到布隆过滤器中，类似于集合的sadd命令，不过bf.add命令只能一次添加一个元素，如果想一次添加多个元素，可以使用bf.madd命令。
bf.exists：判断某个元素是否在过滤器中，类似于集合的sismember命令，不过bf.exists命令只能一次查询一个元素，如果想一次查询多个元素，可以使用bf.mexists命令。 比如：> bf.add one-more-filter fans1 (integer) 1 > bf.add one-more-filter fans2 (integer) 1 > bf.add one-more-filter fans3 (integer) 1 > bf.exists one-more-filter fans1 (integer) 1 > bf.exists one-more-filter fans2 (integer) 1 > bf.exists one-more-filter fans3 (integer) 1 > bf.exists one-more-filter fans4 (integer) 0 > bf.madd one-more-filter fans4 fans5 fans6 1) (integer) 1 2) (integer) 1 3) (integer) 1 > bf.mexists one-more-filter fans4 fans5 fans6 fans7 1) (integer) 1 2) (integer) 1 3) (integer) 1 4) (integer) 0上面的例子中，没有发现误判的情况，是因为元素数量比较少。当元素比较多时，可能就会发生误判，怎么才能减少误判呢？
布隆过滤器的高级使用
上面的例子中使用的布隆过滤器只是默认参数的布隆过滤器，它在我们第一次使用bf.add命令时自动创建的。Redis还提供了自定义参数的布隆过滤器，想要尽量减少布隆过滤器的误判，就要设置合理的参数。 在使用bf.add命令添加元素之前，使用bf.reserve命令创建一个自定义的布隆过滤器。bf.reserve命令有三个参数，分别是： key：键error_rate：期望错误率，期望错误率越低，需要的空间就越大。
capacity：初始容量，当实际元素的数量超过这个初始化容量时，误判率上升。
比如：> bf.reserve one-more-filter 0.0001 1000000
OK
如果对应的key已经存在时，在执行bf.reserve命令就会报错。如果不使用bf.reserve命令创建，而是使用Redis自动创建的布隆过滤器，默认的error_rate是 0.01，capacity是 100。 布隆过滤器的error_rate越小，需要的存储空间就越大，对于不需要过于精确的场景，error_rate设置稍大一点也可以。布隆过滤器的capacity设置的过大，会浪费存储空间，设置的过小，就会影响准确率，所以在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出设置值很多。总之，error_rate和 capacity都需要设置一个合适的数值。布隆过滤器的原理
布隆过滤器内部维护一个bitArray(位数组)， 开始所有数据全部置 0 。当一个元素过来时，能过多个哈希函数（hash1,hash2,hash3....）计算不同的在哈希值，并通过哈希值找到对应的bitArray下标处，将里面的值 0 置为 1 。 需要说明的是，布隆过滤器有一个误判率的概念，误判率越低，则数组越长，所占空间越大。误判率越高则数组越小，所占的空间越小。 下面以网址为例来进行说明, 例如布隆过滤器的初始情况如下图所示：
现在我们需要往布隆过滤里中插入baidu这个url，经过3个哈希函数的计算，hash值分别为1，4，7，那么我们就需要对布隆过滤器的对应的bit位置1， 就如图下所示：
接下来，需要继续往布隆过滤器中添加tencent这个url，然后它计算出来的hash值分别3，4，8，继续往对应的bit位置1。这里就需要注意一个点， 上面两个url最后计算出来的hash值都有4，这个现象也是布隆不能确认某个元素一定存在的原因，最后如下图所示：
布隆过滤器的查询也很简单，例如我们需要查找python，只需要计算出它的hash值， 如果该值为2，4，7，那么因为对应bit位上的数据有一个不为1， 那么一定可以断言python不存在，但是如果它计算的hash值是1，3，7，那么就只能判断出python可能存在，这个例子就可以看出来， 我们没有存入python，但是由于其他key存储的时候返回的hash值正好将python计算出来的hash值对应的bit位占用了，这样就不能准确地判断出python是否存在。
因此， 随着添加的值越来越多， 被占的bit位越来越多， 这时候误判的可能性就开始变高，如果布隆过滤器所有bit位都被置为1的话，那么所有key都有可能存在， 这时候布隆过滤器也就失去了过滤的功能。至此，选择一个合适的过滤器长度就显得非常重要。
从上面布隆过滤器的实现原理可以看出，它不支持删除， 一旦将某个key对应的bit位置0，可能会导致同样bit位的其他key的存在性判断错误。
布隆过滤器的准确性
布隆过滤器的核心思想有两点：
多个hash，增大随机性，减少hash碰撞的概率扩大数组范围，使hash值均匀分布，进一步减少hash碰撞的概率。
虽然布隆过滤器已经尽可能的减小hash碰撞的概率了，但是，并不能彻底消除，因此正如上面的小例子所举的小例子的结果来看， 布隆过滤器只能告诉我们某样东西一定不存在以及它可能存在。
布隆过滤器的应用
1、反垃圾邮件
2、爬虫url防止重复
3、解决缓存穿透
4、黑名单校验
发现存在黑名单中的，就执行特定操作。比如：识别垃圾邮件，只要是邮箱在黑名单中的邮件，就识别为垃圾邮件。假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的，布隆过滤器则是一个较好的解决方案。把所有黑名单都放在布隆过滤器中，再收到邮件时，判断邮件地址是否在布隆过滤器中即可。
布隆过滤器优缺点 优点：优点很明显，二进制组成的数组，占用内存极少，并且插入和查询速度都足够快。
缺点：随着数据的增加，误判率会增加；还有无法判断数据一定存在；另外还有一个重要缺点，无法删除数据。
布谷鸟过滤器
为了解决布隆过滤器优无法删除key的问题，后来出现了升级版的布谷鸟过滤器。
上图（a）(b)展示了一个基本的布谷鸟哈希表的插入操作，是由一个桶数组组成，每个插入项都有由散列函数h1(x)和h2(x)确定的两个候选桶，具体操作上文中已经描述，此处不再赘述。 而基本的布谷鸟过滤器也是由两个或者多个哈希函数构成，布谷鸟过滤器的布谷鸟哈希表的基本单位称为条目（entry）。 每个条目存储一个指纹（fingerprint），指纹指的是使用一个哈希函数生成的n位比特位，n的具体大小由所能接受的误判率来设置，论文中的例子使用的是8bits的指纹大小。 哈希表由一个桶数组组成，其中一个桶可以有多个条目（比如上述图c中有四个条目）。而每个桶中有四个指纹位置，意味着一次哈希计算后布谷鸟有四个“巢“可用，而且四个巢是连续位置，可以更好的利用cpu高速缓存。也就是说每个桶的大小是4*8bits。 插入
布谷鸟过滤器的插入是重点，与朴素的布谷鸟哈希不同，布谷鸟过滤器采取了两个并不独立的哈希函数，具体的 i1=hash(x) i2=i1⊕hash(f)
i1i2即计算出来两个桶的索引，其中第一个桶的索引是通过某个哈希函数计算出来，第二个是使用第一个索引和指纹的哈希做了一个异或操作，进行异或操作的好处是，因为异或操作的特性：同为0不同为1，且0和任何数异或是这个数的本身。那么i1也可以通过i2和指纹异或来计算。 换句话说，在桶中迁走一个键，我们直接用当前桶的索引i和存储在桶中的指纹计算它的备用桶。 具体的指纹是通过哈希函数取一定量的比特位 f=fingerprint(x)
为什么不直接用索引1和指纹做异或操作，关于这个问题文中给了解释，因为指纹一般只是key映射出来的少量bit位置，那么假如不进行哈希操作，当指纹的比特位与整个桶数组相比很小时，那么备用位置使用“i⊕指纹”，将被放置到离桶i1很近的位置，比如使用八位的指纹大小，最多只能改变i1的低八位，所以也就是两个候选通的位置最多相差256，不利于均匀分配。 查找
布谷鸟过滤器的查找过程很简单，给定一个项x，算法首先根据上述插入公式，计算x的指纹和两个候选桶。然后读取这两个桶：如果两个桶中的任何现有指纹匹配，则布谷鸟过滤器返回true，否则过滤器返回false。此时，只要不发生桶溢出，就可以确保没有假阴性。 删除
标准布隆过滤器不能删除，因此删除单个项需要重建整个过滤器，而计数布隆过滤器需要更多的空间。布谷鸟过滤器就像计数布隆过滤器，可以通过从哈希表删除相应的指纹删除插入的项，其他具有类似删除过程的过滤器比布谷鸟过滤器更复杂。 具体删除的过程也很简单，检查给定项的两个候选桶；如果任何桶中的指纹匹配，则从该桶中删除匹配指纹的一份副本。
不足
删除不完美，存在误删的概率。删除的时候知识删除了一份指纹副本，并不能确定此指纹副本是要删除的key的指纹。同时这个问题也导致了假阳性的情况。
插入复杂度比较高。随着插入元素的增多，复杂度会越来越高，因为存在桶满，踢出的操作，所以需要重新计算，但综合来讲复杂度还是常数级别。
存储空间的大小必须为2的指数的限制让空间效率打了折扣。
同一个元素最多插入kb次，（k指哈希函数的个数，b指的桶中能装指纹的个数也可以说是桶的尺寸大小）如果布谷鸟过滤器支持删除，则必须存储同一项的多个副本。 插入同一项kb+1次将导致插入失败。 这类似于计数布隆过滤器，其中重复插入会导致计数器溢出。
参考：https://www.cnblogs.com/heihaozi/p/12174478.html
