图解布隆过滤器和布谷鸟过滤器成功原理

布隆过滤器和布谷鸟过滤器是两种概率型数据结构，重要用于高效的检査一个元素能否属于一个汇合，然而在实事成功、性能个性和经常使用场景上存在必定的差异，上方我们来聊聊这两种过滤器。

1、布隆过滤器

布隆过滤器的原理是对一个key启动n个hash算法失掉n个值，而后经过这些值在比特数组中将这n个值对应的bit位设为1，如下图所示的：

我们元数据经过两个哈希函数函数之后失掉2和7两个值，而后将2和7这个两个值对应的bit位上的值设置为1，这样我们就将元数据寄存到布隆过滤器上。

查问元数据能否在布隆过滤器上的时刻，我们一样对元数据启动两次哈希失掉对应的哈希值，而后经过哈希值在布隆过滤器上寻觅对应的bit位上的值能否都是1，或者有如下的状况：

（1）假设bit位上不都是1，说明元数据不在布隆过滤器上，如下所示：

（2）假设bit位上都是1，如下所示：

那么此时只能说明元数据或者在布隆过滤器上，由于布隆过滤器存在必定的误判，上方解释为什么bit位上全是1然而元数据不必定在布隆过滤器上，如下图所示：

元数据“龙虾”和元数据“编程”经过哈希函数参与到布隆过滤器上，然而元数据“龙虾编程”没有参与到布隆过滤器上。当我们经过哈希函数计算元数据“龙虾编程”的哈希值后，寻觅对应bit位上的发现其值都是1，这就产生了误判的状况。为了缩小布隆过滤器的误判率我们可以参与哈希函数的个数（如原来两个哈希函数，如今我们参与到4个哈希函数）。

布隆过滤器存在必定的弊病，如不允许删除元素，一旦对位数组启动了赋值后不可将其删除，并且其空间应用率也是较低的。

2、布谷鸟过滤器

布隆过滤器不允许删除元素，而布谷鸟过滤器允许删除元素、允许灵活参与元素并且效率比布隆过滤器成果更高。

布谷鸟过滤器底层是桶数组造成的，而且桶中可以经过参数来设置每个桶存储多少个元素，如下如所示的布谷鸟过滤器：

每个桶中有四个指纹位置，象征着一次性哈希计算后布谷鸟有四个“巢“可用，而且四个巢是延续位置。桶中的元素不是我们的元数据，而是经过哈希函数生成bit位，这个bit位我们称之为指纹。

2.1布谷鸟过滤器的桶位置计算函数

布谷鸟过滤器的拔出是经过两个不独立的哈希函数计算出元素须要存储到哪两个桶中，函数如下所示：

h1是间接经过hash函数失掉一个下标，这就是第一个桶的位置；h2经过h1下标与前面的指纹值的哈希结果启动异或，这样就失掉第二桶的位置。h1和h2是经过异或的相关失掉，这样也是布谷鸟过滤器设计的精妙之处，我们经过一个桶的位置就可以计算出另一个桶的位置。

2.2布谷鸟过滤器参与元素

第一步经过指纹哈希函数失掉对应的指纹（如指纹值为5），随后经过哈希元数据失掉第一个桶的位置（如桶1的位置是2），而后拿第一个桶的位置与指纹的哈希值异或失掉第二个桶的位置（如桶2的位置是4）。

假定每个桶中可以寄存两个元素，经过计算失掉桶的位置之后就须要判别两个桶中能否还有位置寄存元素的指纹值，或者的状况如下所示：

（1）假设两个桶中都有位置寄存指纹值，那么会随机筛选一个桶来寄存指纹值，如下所示：

（2）一个桶中曾经存满了，另一个桶还有位置，此时会选用另外的桶寄存指纹，如下所示：

（3）两个桶都存满了指纹值

假设两个桶都存满了指纹值，这个时刻布谷鸟过滤器就会随机筛选一个桶并将桶中的随机的一个指纹值踢掉，把的指纹值寄存出来，如下所示：

此时被踢掉的元素会去寻觅它的另一个桶（由于每个元数据有两个桶），那么寻觅桶的环节就是经过异或的哈希函数成功的，如下所示：

极其的状况下，指纹3存在的另一个桶中也满了，此时就会在桶中随机剔除一个指纹（假定为指纹x），指纹x也就重复指纹值3的环节，这样就会不时递归直到找到桶将一切的指纹寄存下去。当然我们也是可以设置递归的次数，不会让其有限度的递归下去。

随着拔出的元素增多，布谷鸟过滤器的拔出复杂度也就逐渐回升，由于桶的数据越满，那么它的踢出数据的频率就越高，所以须要从新计算的次数也会变多。

2.3布谷鸟过滤器查问元素

由于每个元素都是经过两个并不独立的哈希函数计算之后只会存在特定的桶中，所以查找的时刻只会在特定的桶位置拿到桶中一切的指纹值，而后将桶中的指纹值与的元数据指纹值做对比，如下所示：

我们此时只有要判别能否有元数据的指纹值，假设比对成功那么就证实元数据存在布谷鸟过滤器中（存在也不必定是真存在），反之就就不在布谷鸟过滤器中。

2.4布谷鸟过滤器的元素散布

布谷鸟过滤器在拔出的时刻并不会先去判别这个桶中能否存在相反的指纹，而是间接拔出元数据的指纹，这也就代表同一个桶中存在多个相反的指纹，如下图所示：

也或者出如今布谷鸟过滤器中多个桶中存在雷同的指纹，如下图所示：

这样就产生了雷同的指纹出如今不同的桶中这也就给查问带来必定的假阳性。

2.5布谷鸟过滤器的删除元素

由于我们寄存的是元数据的指纹，因此我们经过查问逻辑找到对应桶中的一切指纹，而后找到元数据的指纹，间接删除这个指纹，如下所示：

然而我们这里须要留意的是，同一个桶中或者会存在多个指纹的相反的正本，此时也就被删除了。

总结：

布隆过滤器和布谷鸟过滤器都有各自的特点，所以也就有各自的经常使用场景。

（1）假设须要一个成熟、便捷且不须要删除元素的概率型数据结构，布隆过滤器是一个很好的选用。

（2）假设须要允许删除操作并且对误报率有更严厉的要求，布谷鸟过滤器或者是更好的选用。在选用数据结构时，须要思考实践运行的需求和性能要求。