来源：www.cnblogs.com/Courage129/p/14337466.html众所周知，在计算机中，IO一直是瓶颈。很多框架、技术甚至硬件都是为了减少IO操作而诞生的。今天就来说说吧。说到过滤器，我们先说一个场景：我们的业务后端涉及到一个数据库。在请求消息查询某些信息时，我们可能会先检查缓存中是否有相关信息，如果有则返回。如果没有，我们可能会去数据库查询，这时候就有一个问题，如果很多请求都是在请求数据库中不存在的数据，那么数据库会频繁响应这种不必要的IO查询，如果多了，大部分的数据库IO都在响应这种不必要的有意义的请求操作，那么如何屏蔽这些请求呢？过滤器由此诞生：布隆过滤器布隆过滤器（BloomFilter）大意是，当你请求的信息到来时，首先检查你是否有查询数据？如果是，则向数据库发送请求。如果没有，直接退货。怎么做？如图，使用一张位图进行记录，位图的原始值全为0。当一个数据存入时，使用三个Hash函数计算三次Hash值，并设置该位图对应的位置bitmap为1。在上图中，bitmap的1、3、6位置被标记为1。如果此时有数据请求进来，仍然是使用前面的三个Hash函数计算Hash值。如果是同一个数据，肯定还是映射到了bits1,3,6，那么就可以判断数据之前已经存储过了。如果新数据映射的三个位置，其中一个无法匹配。如果映射到第1、3、7位，由于第7位为0，即这个数据之前没有加入数据库，所以直接返回。BloomFilter的问题你应该已经发现了上面的方法，Bloomfilter存在一些问题：首先，Bloomfilter可能会误判：如果出现这种情况，当packet1放入时，Setbits1,3,6ofbitmap为1，在放入数据包2时将bitmap的第3、6、7位设置为1，此时一个没有存入的数据包请求3，做3次hash后，对应的bitmap点是1、6、7，这个数据之前没有存储过，但是因为存储数据包1和2的时候对应的点都设置为1，所以请求3也会压垮数据库。这种情况会随着存储数据的增加而增多。第二个方面，Bloomfilter不能删除数据，删除数据有两个难点：第一，由于可能误判，不确定数据是否存在于数据库中，比如数据包3。第二，当你删除一个数据包对应的位图上的标志时，可能会影响到其他数据包。比如上面的例子，如果删除数据包1，就意味着bitmap1、3、6位会被置0，此时请求数据包2时，会显示不存在，因为3位和6位已经被设置为0。Bloomfilter增强版为了解决上述Bloomfilter的问题，出现了增强版的Bloomfilter（CountingBloomFilter）。这个过滤器的思路是用数组来代替布隆过滤器的位图。当数组的某个位置映射一次时，为+1，删除时为-1。这样就避免了普通Bloomfilter删除数据后，对剩余数据包重新计算hash的问题，但还是避免不了误判。Cuckoofilter为了解决Bloomfilter无法删除元素的问题，论文的作者《Cuckoo Filter：Better Than Bloom》提出了cuckoofilter。与cuckoofilter相比，Bloomfilter存在以下缺点：查询性能弱，空间利用效率低，不支持反向操作（删除），不支持计数。查询性能弱是因为布隆过滤器需要使用多个哈希函数来检测位图中的多个不同位置。这些位置在内存中跨度较大，会导致CPU缓存行命中率较低。空间效率低的原因是在相同的误判率下，cuckoofilter的空间利用率明??显高于Bloom，可以节省40%以上的空间。但是布隆过滤器不要求位图的长度必须是2的指数，而布谷鸟过滤器必须有这个要求。从这个角度来看，布隆过滤器似乎更具有空间可扩展性。不支持反向删除操作的问题，真是戳中了Bloomfilter的软肋。在动态系统中，元素总是来来去去。布隆过滤器就像污点，来来去去都会有痕迹，即使消失也无法清理。比如你的系统只剩下1kw个元素，但是整体有上亿个水元素，Bloomfilter很无奈，它会把这些丢失的元素的印记永远存在那里。随着时间的推移，这个过滤器会变得越来越拥挤，直到有一天你发现它的误报率太高而不得不重建它。cuckoofilter在论文中号称解决了这个问题，可以有效的支持逆向删除操作。并将其作为一个重要的卖点来诱使您放弃Bloom过滤器并改用布谷鸟过滤器。为什么叫布谷鸟呢？有成语，“鸠占鹊巢”，布谷鸟也是。布谷鸟从不自己筑巢。它在别人的巢里下自己的蛋，请别人帮忙孵化。布谷鸟宝宝孵化出来后，因为布谷鸟比较大，把养母的其他孩子（或卵）挤出了窝——从高空坠落而死。Cuckoohash最简单的cuckoohash结构是一维数组结构，会有两种哈希算法将新元素映射到数组的两个位置。如果两个位置之一为空，则可以直接将元素放入其中。但如果这两个位置满了，它就得“占鹊巢”，随便踢开一个，然后自己占据这个位置。p1=hash1(x)%lp2=hash2(x)%l复制代码和布谷鸟不同，布谷鸟哈希算法会帮助这些受害者（被压榨的鸡蛋）找到其他的巢穴。因为每个元素都可以放在两个位置，只要任意一个有空闲的位置，就可以插入。所以这个被挤出来的伤心蛋会看看他的另一个位置有没有空，如果有空，他就自己搬过去，大家就皆大欢喜了。可万一这个位置也被别人占据了呢？好吧，那就又是“鸽子占鹊巢”，把受害者的角色推给别人了。新的受害者然后重复这个过程，直到所有的鸡蛋都找到了它们的巢穴。cuckoohashing的问题，但是会有一个问题，就是如果数组太拥挤，会不停的踢上百次，这时候插入效率会受到严重影响。这时布谷鸟哈希会设置一个阈值。当连续占巢行为超过一定阈值时，阵列被认为快满了。这时需要扩建，所有元素搬迁。还会有另一个问题，那就是运行周期的可能性。比如对于两个不同的元素，hash后的两个位置是完全一样的。这个时候，他们各占一个位置是没有问题的。但是这时候第三个元素来了，它在hash之后的位置和他们一样。很明显，此时会有一个运行周期。但是，经过两次哈希后，三个不同元素的位置仍然相同。出现这种情况的概率不是很高，除非你的哈希算法实在是太受挫了。cuckoohash算法对这个运行周期的态度是数组太拥挤，需要扩容（其实不是）。优化上述布谷鸟哈希算法，平均空间利用率在50%左右。当达到这个百分比时，连续运行的次数很快就会超过阈值。这样的哈希算法的价值并不明显，因此需要改进。改进的方案之一是增加散列函数，使每个元素不仅有二嵌套，而且有三嵌套和四嵌套。这样可以大大降低碰撞的概率，将空间利用率提高到95%左右。还有一个改进就是在数组的每个位置挂上多个席位，这样即使两个元素在同一个位置哈希，也不需要马上“占鹊巢”，因为有多个席位，可以放心坐在一个。除非这些多个座位被占用，否则需要运行。显然，这也会显着减少运行次数。该方案的空间利用率只有85%左右，但是查询效率会很高。同一位置的多个席位在内存空间上是连续的，可以有效利用CPU缓存。因此，更高效的方案是将以上两种改进方案结合起来，比如使用4个哈希函数，每个位置放置2个席位。这样，时间效率和空间效率都可以获得。这样的组合甚至可以将空间利用率提升99%，这是非常了不起的空间效率。Cuckoofiltercuckoofilter和cuckoohash结构一样，也是一维数组，但是和cuckoohash不同的是，cuckoohash会存储整个元素，而cuckoofilter只会存储元素的指纹信息元素（几位，类似于布隆过滤器）。这里过滤器为了空间效率牺牲了数据准确性。正是因为存储了元素的指纹信息，所以才会有误报率，这和Bloomfilter完全一样。首先，布谷鸟过滤器仍然只使用了两个哈希函数，但每个位置可以放置多个席位。这两个哈希函数的选择比较特殊，因为过滤器中只能存储指纹信息。当这个位置的指纹被挤压时，需要计算另一个对偶位置。这个对偶位置的计算需要元素本身。让我们回顾一下之前的哈希位置计算公式。fp=fingerprint(x)p1=hash1(x)%lp2=hash2(x)%l我们知道p1和x的指纹，但是没有办法直接算出p2。特殊哈希函数布谷鸟过滤器的巧妙之处在于设计了独特的哈希函数，使得p2可以直接根据p1和元素指纹计算得到，不需要完整的x元素。fp=fingerprint(x)p1=hash(x)p2=p1^hash(fp)//XOR从上面的公式可以看出，当我们知道fp和p1时，我们可以直接计算p2。同样，如果我们知道p2和fp，我们也可以直接计算p1——对偶性。p1=p2^hash(fp)，所以我们不需要知道当前位置是p1还是p2，只需要将当前位置和hash(fp)异或即可得到对偶位置。而你只需要保证hash(fp)!=0就可以保证p1!=p2，这样就不会出现踢自己导致死循环的问题。也许你会问为什么这里的哈希函数不需要对数组的长度取模呢？其实是需要的，但是cuckoofilter强制要求数组长度必须是2的幂，所以对数组长度取模相当于取hash值的最后n位。进行异或运算时，忽略低n位以外的其他位。保留计算出的位置p的低n位就是最终的对偶位置。近期热点文章推荐：1.1000+Java面试题及答案（2022最新版）2.厉害了！Java协程来了。..3.SpringBoot2.x教程，太全面了！4.不要用爆破爆满画面，试试装饰者模式，这才是优雅的方式！！5.《Java开发手册（嵩山版）》最新发布，赶快下载吧！感觉不错，别忘了点赞+转发！
