共计 4012 个字符，预计需要花费 11 分钟才能阅读完成。
一、过滤器应用场景：
比方有如下几个需要：
1、本来有 10 亿个号码，当初又来了 10 万个号码，要疾速精确判断这 10 万个号码是否在 10 亿个号码库中？
解决办法一：将 10 亿个号码存入数据库中，进行数据库查问，准确性有了，然而速度会比较慢。
解决办法二：将 10 亿号码放入内存中，比方 Redis 缓存中，这里咱们算一下占用内存大小：10 亿 * 8 字节 =8GB，通过内存查问，准确性和速度都有了，然而大概 8gb 的内存空间，挺节约内存空间的。
2、接触过爬虫的，应该有这么一个需要，须要爬虫的网站千千万万，对于一个新的网站 url，咱们如何判断这个 url 咱们是否曾经爬过了？
解决办法还是下面的两种，很显然，都不太好。
3、同理还有垃圾邮箱的过滤。
那么对于相似这种，大数据量汇合，如何精确疾速的判断某个数据是否在大数据量汇合中，并且不占用内存，过滤器应运而生了。
二、布隆过滤器（Bloom Filter）
布隆过滤器：一种数据结构（bitmap），是由一串很长的二进制向量组成，能够将其看成一个二进制数组。既然是二进制，那么外面寄存的不是 0，就是 1，然而初始默认值都是 0。
布隆过滤器应用 exists()来判断某个元素是否存在于本身构造中。当布隆过滤器断定某个值存在时，其实这个值只是有可能存在；当它说某个值不存在时，那这个值必定不存在，这个误判概率大概在 1% 左右。
工作流程 - 增加元素
布隆过滤器次要由位数组和一系列 hash 函数形成，其中位数组的初始状态都为 0。
上面对布隆过滤器工作流程做简略形容，如下图所示：
当应用布隆过滤器增加 key 时，会应用不同的 hash 函数对 key 存储的元素值进行哈希计算，从而会失去多个哈希值。依据哈希值计算出一个整数索引值，将该索引值与位数组长度做取余运算，最终失去一个位数组地位，并将该地位的值变为 1。每个 hash 函数都会计算出一个不同的地位，而后把数组中与之对应的地位变为 1。通过上述过程就实现了元素增加 (add) 操作。
工作流程 - 断定元素是否存在
当咱们须要判断一个元素是否存时，其流程如下：首先对给定元素再次执行哈希计算，失去与增加元素时雷同的位数组地位，判断所得地位是否都为 1，如果其中有一个为 0，那么阐明元素不存在，若都为 1，则阐明元素有可能存在。
为什么是可能“存在”
您可能会问，为什么是有可能存在？其实起因很简略，那些被置为 1 的地位也可能是因为其余元素的操作而扭转的。比方，元素 1 和 元素 2，这两个元素同时将一个地位变为了 1（图 1 所示）。在这种状况下，咱们就不能断定“元素 1”肯定存在，这是布隆过滤器存在误判的根本原因。
将这个新的数据通过下面自定义的几个哈希函数，别离算出各个值，而后看其对应的中央是否都是 1，如果存在一个不是 1 的状况，那么咱们能够说，该新数据肯定不存在于这个布隆过滤器中。
反过来说，如果通过哈希函数算进去的值，对应的中央都是 1，那么咱们可能必定的得出：这个数据肯定存在于这个布隆过滤器中吗？
答案是否定的，因为多个不同的数据通过 hash 函数算进去的后果是会有反复的，所以会存在某个地位是别的数据通过 hash 函数置为的 1。
咱们能够失去一个论断：布隆过滤器能够判断某个数据肯定不存在，然而无奈判断肯定存在。
3. 布隆过滤器优缺点
长处：长处很显著，二进制组成的数组，占用内存极少，并且插入和查问速度都足够快。
毛病：随着数据的减少，误判率会减少；还有无奈判断数据肯定存在；另外还有一个重要毛病，无奈删除数据。
1. 将算法和 bitmap 数据放在 client
2. 算法在 client，bitmap 数据在 redis
3. 讲算法和 bitmap 数据都放在 redis
升级版的布隆过滤器（Counting Bloom Filter）
原理就是把位图的位 降级为计数器 (Counter). 增加元素, 就给对应的 Counter 别离 +1; 删除元素, 就给对应的 Counter 别离减一. 用多出几倍存储空间的代价, 来实现删除性能
三、布谷鸟过滤器（Cuckoo filter）
为了解决布隆过滤器不能删除元素的问题, 论文《Cuckoo Filter：Better Than Bloom》作者提出了布谷鸟过滤器。相比布谷鸟过滤器，布隆过滤器有以下有余：查问性能弱、空间利用效率低、不反对反向操作（删除）以及不反对计数。
1、查问性能弱是因为布隆过滤器须要应用多个 hash 函数探测位图中多个不同的位点，这些位点在内存上跨度很大，会导致 CPU 缓存行命中率低。
2、空间效率低是因为在雷同的误判率下，布谷鸟过滤器的空间利用率要显著高于布隆，空间上大略能节俭 40% 多。不过布隆过滤器并没有要求位图的长度必须是 2 的指数，而布谷鸟过滤器必须有这个要求。从这一点登程，仿佛布隆过滤器的空间伸缩性更强一些。
3、不反对反向删除操作这个问题着实是击中了布隆过滤器的软肋。在一个动静的零碎外面元素总是一直的来也是一直的走。布隆过滤器就好比是印迹，来过去就会有痕迹，就算走了也无奈清理洁净。比方你的零碎里原本只留下 1kw 个元素，然而整体上来过了上亿的流水元素，布隆过滤器很无奈，它会将这些散失的元素的印迹也会永远寄存在那里。随着工夫的散失，这个过滤器会越来越拥挤，直到有一天你发现它的误判率太高了，不得不进行重建。
4、布谷鸟哈希
最简略的布谷鸟哈希构造是一维数组构造，会有两个 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 位就是最终的对偶地位。
