[未完结]Bloom过滤器综述

布隆过滤器是相当优秀的设计----利用极小的位数组表达对象的存在信息，空间占用小、查询效率高的优点更是让程序员们欲罢不能。当然bloom过滤器也不是完美的，比如不支持删除数据，有缺点就会有人会尝试改进 — Counting Bloom Filter 、Cuckoo Filter 应运而生。下面介绍一下普通BloomFilter及其改进。

一、Bloom Filter

1.普通布隆过滤器的设计

假设我们定义三个hash函数，hash0，hash1，hash2，插入一个对象A，hash0(A) = 0，hash1(A) = 3，hash2(A) = 7，这时候我们就需要把BitMap中的第0位、第3位、第7位设置为1，判断A是否在Bloom Filter中只需要做同样的hash，然后判断以hash值作为索引的位是否都为1，如果是则可能存在对象A，否则必然不存在。

2.如何理解判断的结果？

在hash函数中，我们熟知的一个问题就是hash碰撞，如果对两个对象A和B进行hash，hash0(A) = hash0(B)，hash1(A) = hash1(B)，hash2(A) = hash2(B)，Bloom Filter中只插入了A对象，但是如果我们查询B对象，结果还是true，因为hash值对应的位都为1，而这些位就是碰撞的A对象设置的位。

还有一种情况，假设我们存在对象A、B、C、D，现在对四个对象进行hash，hash0(A) = hash0(D)，hash1(B) = hash1(D)，hash2© = hash2(D)，Bloom Filter同时插入对象A、B、C，但是如果我们查询D对象，结果还是true，因为hash值对应的位都为1，而这些位就是A、B、C分别设置的位。

第二种情况尤为常见，只要在Bloom Filter中被置1的位足够多，就能导致误判率大大升高。

二、Counting Bloom Filter

1.为什么需要Counting Bloom Filter ？

因为普通布隆过滤器只支持插入和查询两种操作，而Counting Bloom Filter 在此基础上增加了删除操作，实现了Bloom Filter 的动态性。

2.Counting Bloom Filter 的设计

（上面的图片来自网络，无法确定出处）左边是普通Bloom Filter的设计，插入一个对象时，通过多个hash函数将BitMap中的对应下标的位置1，但是如果需要删除，因为一个对象同时占有多个位，但是这些位可能跟其他对象共享，如果贸然删除就会导致影响到其他对象在BitMap的映射。为了解决删除时对其他映射的影响，Counting Bloom Filter 采用计数器对每一位的映射次数进行统计，当插入一个对象计算出多个hash值，将每个hash值对应索引的计数器增加1，从而保证每个条目都能容纳一定数量的对象的共享而且计数上又互相独立。据说选择4bit作为计数器是比较优良的选择，具体分析请看:https://blog.csdn.net/jiaomeng/article/details/1498283（论文式写法，极端优秀）

三、Cuckoo Filter

1.为什么需要布谷鸟过滤器(Cuckoo Filter)？

Cuckoo Filter不能进行元素的删除。参照https://blog.csdn.net/qq_17305249/article/details/94996252博主的说法，布谷鸟过滤器是为了在保证低失误率下优化空间性能–减少访存次数和空间占用。

按照博主的说法，因为布隆过滤器是使用k位存储一个对象，每次查询需要进行k次hash然后访问对应的比特； 而布谷鸟过滤器只需要进行最多k次访存（k用于限制踢出元素的最大次数）。这两个的区别与B树和B+树的区别极端相似—B树具有较好的查询效率但空间局部性差 ，B+树具有稳定的查询效率和优秀的空间局部性。

2.布谷鸟过滤器(Cuckoo Filter)的设计

假设一个指纹函数fingerprint，该函数返回8bit的正整数，一个hash函数，我们插入一个对象A：

1、如果hash(A)所在位置的条目为0，则说明该位置没有对象，将该条目的值设置为fingerprint(A)；

2、如果hash(A)所在位置的条目不为0，则说明该位置存在对象B，剔除对象B – 将该位置设置为fingerprint(A)，B在备选表2中寻找位置hash(A) ⊕ fingerprint(B)的条目，如果该条目为0，说明不存在对象，将条目的值设置为fingerprint(B)；否则，假设存在对象C，剔除对象C – -- 将该位置设置为fingerprint(B)；C又回到备选表1中寻找位置hash(B) ⊕ fingerprint©，如此循环。

如果两个表都是满的、这就会出现无限循环的情况，所以我们要限制踢的次数，当踢出对象的次数到达某个次数时，需要对表进行扩容。

四、应用

海量数据去重：例如推荐系统防止重复推荐。
从用户观看历史中筛选出没有看过的新闻进行推送，就需要数据库中频繁的使用exists进行查询，但是当用户量很大时，数据库很难顶住压力。

黑白名单：因为bloomFilter对于不存在的判断是确定的，而且黑白名单的数据相对较少，可以先通过BloomFilter判断数据是否不存在，如果BloomFilter的结果为存在，返回数据源进行确定。

缓存穿透：在缓存穿透上的应用，是为了避免恶意用户频繁请求缓存中不存在DB也不存在的值，会导致缓存失效、DB负载过大，可以使用BloomFilter把所有数据放到bit数组中，当用户请求时存在的值肯定能放行，部分不存在的值也会被放行，绝大部分会被拦截，这些少量漏网之鱼对于DB的影响就会比大量穿透好的多了。

恶意URL拦截

敏感词过滤勉强能用：https://blog.csdn.net/lidelin10/article/details/102868723

现在还剩几个问题：

1、布谷鸟过滤器和普通Bloom过滤器的对比，优势在哪？（据说空间性能好、访存次数少），如何进行测评？

2、还有好几种变种的Bloom Filter，需要再研读https://me.csdn.net/jiaomeng这位兄弟的博客