共计 3932 个字符，预计需要花费 10 分钟才能阅读完成。
起源：www.cnblogs.com/Courage129/p/14337466.html
大家都晓得, 在计算机中,IO 始终是一个瓶颈, 很多框架以及技术甚至硬件都是为了升高 IO 操作而生, 明天聊一聊过滤器, 先说一个场景:
咱们业务后端波及数据库, 当申请音讯查问某些信息时, 可能先查看缓存中是否有相干信息, 有的话返回, 如果没有的话可能就要去数据库外面查问, 这时候有一个问题, 如果很多申请是在申请数据库基本不存在的数据, 那么数据库就要频繁响应这种不必要的 IO 查问, 如果再多一些, 数据库大多数 IO 都在响应这种毫无意义的申请操作, 那么如何将这些申请阻挡在外呢? 过滤器由此诞生:
布隆过滤器
布隆过滤器 (Bloom Filter) 大略的思路就是, 当你申请的信息来的时候, 先检查一下你查问的数据我这有没有, 有的话将申请压给数据库, 没有的话间接返回, 是如何做到的呢?
如图, 一个 bitmap 用于记录,bitmap 原始数值全都是 0, 当一个数据存进来的时候, 用三个 Hash 函数别离计算三次 Hash 值, 并且将 bitmap 对应的地位设置为 1, 上图中,bitmap 的 1,3,6 地位被标记为 1, 这时候如果一个数据申请过去, 仍然用之前的三个 Hash 函数计算 Hash 值, 如果是同一个数据的话, 势必仍旧是映射到 1,3,6 位, 那么就能够判断这个数据之前存储过, 如果新的数据映射的三个地位, 有一个匹配不上, 如果映射到 1,3,7 位, 因为 7 位是 0, 也就是这个数据之前并没有退出进数据库, 所以间接返回。
布隆过滤器的问题
下面这种形式, 应该你曾经发现了, 布隆过滤器存在一些问题:
第一方面, 布隆过滤器可能误判:
如果有这么一个情景, 放入数据包 1 时, 将 bitmap 的 1,3,6 位设置为了 1, 放入数据包 2 时将 bitmap 的 3,6,7 位设置为了 1, 此时一个并没有存过的数据包申请 3, 做三次哈希之后, 对应的 bitmap 位点别离是 1,6,7, 这个数据之前并没有存进去过, 然而因为数据包 1 和 2 存入时将对应的点设置为了 1, 所以申请 3 也会压倒数据库上, 这种状况, 会随着存入的数据减少而减少。
第二方面, 布隆过滤器没法删除数据, 删除数据存在以下两种窘境:
一是, 因为有误判的可能, 并不确定数据是否存在数据库里, 例如数据包 3。
二是, 当你删除某一个数据包对应位图上的标记后, 可能影响其余的数据包, 例如下面例子中, 如果删除数据包 1, 也就意味着会将 bitmap1,3,6 位设置为 0, 此时数据包 2 来申请时, 会显示不存在, 因为 3,6 两位曾经被设置为 0。
布隆过滤器增强版
为了解决下面布隆过滤器的问题, 呈现了一个增强版的布隆过滤器(Counting Bloom Filter), 这个过滤器的思路是将布隆过滤器的 bitmap 更换成数组, 当数组某地位被映射一次时就 +1, 当删除时就 -1, 这样就防止了一般布隆过滤器删除数据后须要从新计算其余数据包 Hash 的问题, 然而仍旧没法防止误判。
布谷鸟过滤器
为了解决布隆过滤器不能删除元素的问题, 论文《Cuckoo Filter：Better Than Bloom》作者提出了布谷鸟过滤器。相比布谷鸟过滤器，布隆过滤器有以下有余：查问性能弱、空间利用效率低、不反对反向操作（删除）以及不反对计数。
查问性能弱 是因为布隆过滤器须要应用多个 hash 函数探测位图中多个不同的位点，这些位点在内存上跨度很大，会导致 CPU 缓存行命中率低。
空间效率低 是因为在雷同的误判率下，布谷鸟过滤器的空间利用率要显著高于布隆，空间上大略能节俭 40% 多。不过布隆过滤器并没有要求位图的长度必须是 2 的指数，而布谷鸟过滤器必须有这个要求。从这一点登程，仿佛布隆过滤器的空间伸缩性更强一些。
不反对反向删除操作 这个问题着实是击中了布隆过滤器的软肋。在一个动静的零碎外面元素总是一直的来也是一直的走。布隆过滤器就好比是印迹，来过去就会有痕迹，就算走了也无奈清理洁净。比方你的零碎里原本只留下 1kw 个元素，然而整体上来过了上亿的流水元素，布隆过滤器很无奈，它会将这些散失的元素的印迹也会永远寄存在那里。随着工夫的散失，这个过滤器会越来越拥挤，直到有一天你发现它的误判率太高了，不得不进行重建。
布谷鸟过滤器在论文里宣称本人解决了这个问题，它能够无效反对反向删除操作。而且将它作为一个重要的卖点，引诱你们放弃布隆过滤器改用布谷鸟过滤器。
为啥要取名布谷鸟呢?
有个成语，「鸠占鹊巢」, 布谷鸟也是, 布谷鸟从来不本人筑巢。它将本人的蛋产在他人的巢里，让他人来帮忙孵化。待小布谷鸟破壳而出之后，因为布谷鸟的体型绝对较大，它又将养母的其它孩子（还是蛋）从巢里挤走 —— 从低空摔下夭折了。
布谷鸟哈希
最简略的布谷鸟哈希构造是一维数组构造，会有两个 hash 算法将新来的元素映射到数组的两个地位。如果两个地位中有一个地位为空，那么就能够将元素间接放进去。然而如果这两个地位都满了，它就不得不「鸠占鹊巢」，随机踢走一个，而后本人霸占了这个地位。
p1 = hash1(x) % l
p2 = hash2(x) % l
复制代码不同于布谷鸟的是，布谷鸟哈希算法会帮这些受害者（被挤走的蛋）寻找其它的窝。因为每一个元素都能够放在两个地位，只有任意一个有空地位，就能够塞进去。所以这个伤心的被挤走的蛋会看看本人的另一个地位有没有空，如果空了，本人挪过来也就大快人心了。然而如果这个地位也被他人占了呢？好，那么它会再来一次「鸠占鹊巢」，将受害者的角色转嫁给他人。而后这个新的受害者还会反复这个过程直到所有的蛋都找到了本人的巢为止。
布谷鸟哈希的问题
然而会遇到一个问题，那就是如果数组太拥挤了，间断踢来踢去几百次还没有停下来，这时候会重大影响插入效率。这时候布谷鸟哈希会设置一个阈值，当间断占巢行为超出了某个阈值，就认为这个数组曾经简直满了。这时候就须要对它进行扩容，从新搁置所有元素。
还会有另一个问题，那就是可能会存在挤兑循环。比方两个不同的元素，hash 之后的两个地位正好雷同，这时候它们一人一个地位没有问题。然而这时候来了第三个元素，它 hash 之后的地位也和它们一样，很显著，这时候会呈现挤兑的循环。不过让三个不同的元素通过两次 hash 后地位还一样，这样的概率并不是很高，除非你的 hash 算法太挫了。
布谷鸟哈希算法看待这种挤兑循环的态度就是认为数组太拥挤了，须要扩容（实际上并不是这样）。
优化
下面的布谷鸟哈希算法的均匀空间利用率并不高，大略只有 50%。到了这个百分比，就会很快呈现间断挤兑次数超出阈值。这样的哈希算法价值并不显著，所以须要对它进行改进。
改进的计划之一是减少 hash 函数，让每个元素不止有两个巢，而是三个巢、四个巢。这样能够大大降低碰撞的概率，将空间利用率进步到 95% 左右。
另一个改进计划是在数组的每个地位上挂上多个座位，这样即便两个元素被 hash 在了同一个地位，也不用立刻「鸠占鹊巢」，因为这里有多个座位，你能够随便坐一个。除非这多个座位都被占了，才须要进行挤兑。很显著这也会显著升高挤兑次数。这种计划的空间利用率只有 85% 左右，然而查问效率会很高，同一个地位上的多个座位在内存空间上是间断的，能够无效利用 CPU 高速缓存。
所以更加高效的计划是将下面的两个改进计划交融起来，比方应用 4 个 hash 函数，每个地位上放 2 个座位。这样既能够失去工夫效率，又能够失去空间效率。这样的组合甚至能够将空间利用率提到高 99%，这是十分了不起的空间效率。
布谷鸟过滤器
布谷鸟过滤器和布谷鸟哈希构造一样，它也是一维数组，然而不同于布谷鸟哈希的是，布谷鸟哈希会存储整个元素，而布谷鸟过滤器中只会存储元素的指纹信息（几个 bit，相似于布隆过滤器）。这里过滤器就义了数据的精确性换取了空间效率。正是因为存储的是元素的指纹信息，所以会存在误判率，这点和布隆过滤器一模一样。
首先布谷鸟过滤器还是只会选用两个 hash 函数，然而每个地位能够搁置多个座位。这两个 hash 函数抉择的比拟非凡，因为过滤器中只能存储指纹信息。当这个地位上的指纹被挤兑之后，它须要计算出另一个对偶地位。而计算这个对偶地位是须要元素自身的，咱们来回顾一下后面的哈希地位计算公式。
fp = fingerprint(x)
p1 = hash1(x) % l
p2 = hash2(x) % l咱们晓得了 p1 和 x 的指纹，是没方法间接计算出 p2 的。
非凡的 hash 函数
布谷鸟过滤器奇妙的中央就在于设计了一个独特的 hash 函数，使得能够依据 p1 和 元素指纹 间接计算出 p2，而不须要残缺的 x 元素。
fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp) // 异或从下面的公式中能够看出，当咱们晓得 fp 和 p1，就能够间接算出 p2。同样如果咱们晓得 p2 和 fp，也能够间接算出 p1 —— 对偶性。
p1 = p2 ^ hash(fp)所以咱们基本不须要晓得以后的地位是 p1 还是 p2，只须要将以后的地位和 hash(fp) 进行异或计算就能够失去对偶地位。而且只须要确保 hash(fp) != 0 就能够确保 p1 != p2，如此就不会呈现本人踢本人导致死循环的问题。
兴许你会问为什么这里的 hash 函数不须要对数组的长度取模呢？实际上是须要的，然而布谷鸟过滤器强制数组的长度必须是 2 的指数，所以对数组的长度取模等价于取 hash 值的最初 n 位。在进行异或运算时，疏忽掉低 n 位 之外的其它位就行。将计算出来的地位 p 保留低 n 位就是最终的对偶地位。
近期热文举荐：
1.1,000+ 道 Java 面试题及答案整顿(2022 最新版)
2. 劲爆！Java 协程要来了。。。
3.Spring Boot 2.x 教程，太全了！
4. 别再写满屏的爆爆爆炸类了，试试装璜器模式，这才是优雅的形式！！
5.《Java 开发手册（嵩山版）》最新公布，速速下载！
感觉不错，别忘了顺手点赞 + 转发哦！