图解布隆过滤器和布谷鸟过滤器实现原理

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）如果需要支持删除操作并且对误报率有更严格的要求，布谷鸟过滤器可能是更好的选择。在选择数据结构时，需要考虑实际应用的需求和性能要求。