1.Filter使用场景：例如有如下需求：1.本来有10亿个数，现在有10万个数。需要快速准确判断10亿号码池中是否有10万个号码？ 方案一：在数据库中存储10亿个数字，进行数据库查询。精度提高了，但是速度会变慢。 方案二：将10亿个数放入内存，比如Redis缓存，这里计算占用内存大小：10亿*8字节=8GB，通过内存查询，精度和速度都达到了，但是内存空间大约8gb是相当浪费内存空间。2、接触过爬虫的应该都有这样的需求。有成千上万的网站需要爬虫。对于一个新的网站url，我们如何判断是否已经抓取过这个url呢？解决办法还是上面两种，显然，都不是很好。3、同样，还有垃圾邮箱的过滤。 那么对于这么大的数据集合，如何在不占用内存的情况下准确快速的判断某个数据是否在大数据集合中，过滤器就应运而生了。2、布隆过滤器（BloomFilter）布隆过滤器：一种数据结构（位图），由一串很长的二进制向量组成，可以看成是一个二进制数组。由于它是二进制的，所以它存储0或1，但初始默认值为0。Bloom过滤器使用exists()来确定元素是否存在于它自己的结构中。当布隆过滤器判断某个值存在时，这个值可能真的存在；当它说某个值不存在，那么这个值肯定不存在，误判的概率在1%左右。工作流程——添加元素布隆过滤器主要由一个位数组和一系列哈希函数组成，位数组的初始状态为0。下面简单介绍一下布隆过滤器的工作流程，如下图所示：当使用布隆过滤器添加一个key时，会使用不同的哈希函数对key中存储的元素值进行哈希计算，从而得到多个哈希值。根据哈希值计算一个整数索引值，对索引值和位数组的长度进行取余运算，最后得到一个位数组位置，并将这个位置的值改为1。每个哈希函数都会计算一个不同的位置，然后将数组中对应的位置改为1。通过以上过程完成了元素的添加（add）操作。工作流程——判断一个元素是否存在当我们需要判断一个元素是否存在时，流程如下：首先对给定的元素再次进行哈希计算，得到与添加元素时相同的位数组位置，判断是否存在得到的位置都是1，如果其中一个为0，则该元素不存在，如果都为1，则该元素可能存在。为什么有可能“存在”你可能会问，为什么有可能存在？其实原因很简单，那些设置为1的位置也有可能因为其他元素的操作而改变。比如元素1和元素2，这两个元素同时改变一个位置为1（如图1）。在这种情况下，我们无法确定“元素1”一定存在，这就是布隆过滤器误判的根本原因。将这个新数据通过上面几个自定义的hash函数计算出每一个值，然后检查对应的地方是否都是1，如果有不为1的情况，那么我们就可以说新数据一定不存在于这个Bloom中筛选。反之，如果哈希函数计算出的值对应的是1，那么我们就可以肯定的得出结论：这个布隆过滤器中一定存在这个数据吗？答案是否定的，因为多个不同的数据通过hash函数计算出来的结果会重复，所以会有某个位置其他数据通过hash函数置1。我们可以得出一个结论：布隆过滤器可以判断某条数据一定不存在，但不能判断一定存在。3.Bloomfilter的优缺点优点：优点很明显，二进制数组占用内存很少，插入和查询速度足够快。缺点：随着数据的增加，误判率会增加；无法判断数据一定存在；还有一个重要的缺点是数据无法删除。1.把算法和位图数据放到client2上。算法在客户端，位图数据在redis3。算法和位图数据都放在redis升级版布隆过滤器（CountingBloomFilter）上。原理是将位图的位提升为计数器（Counter）。添加一个元素，对应的Counter分别+1；删除一个元素，对应的Counter会分别减1。删除功能是以多几倍的存储空间为代价实现的。3.布谷过滤器（Cuckoofilter）为了解决布隆过滤器无法删除元素的问题，论文作者《Cuckoo Filter：Better Than Bloom》提出了布谷过滤器。与cuckoofilter相比，Bloomfilter存在以下缺点：查询性能弱，空间利用效率低，不支持反向操作（删除），不支持计数。1、查询性能弱是因为布隆过滤器需要使用多个哈希函数来检测位图中的多个不同位置。这些位置在内存中跨度较大，会导致CPU缓存行命中率较低。2、空间效率低的原因是在相同的误判率下，布谷鸟过滤器的空间利用率明??显高于布卢姆，可以节省40%以上的空间。但是布隆过滤器不要求位图的长度必须是2的指数，而布谷鸟过滤器必须有这个要求。从这个角度来看，布隆过滤器似乎更具有空间可扩展性。3.不支持反向删除操作的问题，确实击中了Bloomfilter的弱点。在动态系统中，元素总是来来去去。布隆过滤器就像污点，来来去去都会有痕迹，即使消失也无法清理。比如你的系统只剩下1kw个元素，但是整体有上亿个水元素，Bloomfilter很无奈，它会把这些丢失的元素的印记永远存在那里。随着时间的推移，这个过滤器会变得越来越拥挤，直到有一天你发现它的误报率太高而不得不重建它。4.Cuckoohash最简单的cuckoohash结构是一维数组结构，会有两种hash算法将新元素映射到数组的两个位置。如果两个位置之一为空，则可以直接将元素放入其中。但如果两个位置都满了，它会随机踢开一个，然后自己占据这个位置。p1=hash1(x)%lp2=hash2(x)%l与布谷鸟不同的是，布谷鸟哈希算法会帮助这些受害者（被压榨的蛋）找到其他的巢穴。因为每个元素都可以放在两个位置，只要任意一个有空闲的位置，就可以插入。所以这个被挤出来的伤心蛋会看看他的另一个位置有没有空，如果有空，他就自己搬过去，大家就皆大欢喜了。可万一这个位置也被别人占据了呢？好吧，那就又是“鸽子占鹊巢”，把受害者的角色推给别人了。新的受害者然后重复这个过程，直到所有的鸡蛋都找到了它们的巢穴。cuckoohashing的问题，但是会有一个问题，就是如果数组太拥挤，会不停的踢上百次，这时候插入效率会受到严重影响。这时布谷鸟哈希会设置一个阈值。当连续占巢行为超过一定阈值时，阵列被认为快满了。这时需要扩建，所有元素搬迁。还会有另一个问题，那就是运行周期的可能性。比如对于两个不同的元素，hash后的两个位置是完全一样的。这个时候，他们各占一个位置是没有问题的。但是这时候第三个元素来了，它在hash之后的位置和他们一样。很明显，此时会有一个运行周期。但是，经过两次哈希后，三个不同元素的位置仍然相同。出现这种情况的概率不是很高，除非你的哈希算法实在是太受挫了。cuckoohash算法对这个run-oncycle的态度是数组太拥挤，需要扩充（其实不是这样的）。上面优化后的布谷鸟哈希算法平均空间利用率不高，只有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位就是最终的对偶位置。
