基于原论文，我实现了一个更全面的布谷鸟过滤器-木庄网络博客

本文摘自网络，作者，侵删。

原文地址

“判断一个值是否在一个巨大的集合当中”（下文中统称为集合隶属测试），是一种常见的数据处理问题。在以往的经验中，如果允许一定的假阳性率，那么布隆过滤器是首选，而如今我们有了更好的选择：布谷鸟过滤器。
最近的业务需要用到过滤器，搜索了一下发现我们的场景下布谷鸟过滤器性价比更高，要好于布隆过滤器。
为了确定最终的技术选型，我去读了一下原论文，后来确定要用布谷鸟过滤器时发现几乎没有 golang 的全面实现，当前在 GitHub 上的几个高 stars 实现都存在一些缺陷，并没有最大化空间利用率，因此自己参照原论文以及论文的原 C++实现，移植并优化了一版 Golang 的库，细节内容都在下文中。
代码地址在这，欢迎 star 、使用、贡献、debug： https://github.com/linvon/cuckoo-filter

布谷鸟过滤器

布谷鸟过滤器在网络上已经有很多的介绍文章了，这里不再做过多的介绍，只提一下要点，用于引出下面的内容

如果想要知道更多的细节，可以参考原论文，或者查看我的中文翻译版本

什么是布谷鸟过滤器？

是一种基于布谷鸟哈系算法实现的过滤器，本质上是存储了存储项哈希值的布谷鸟哈希表。

如果你了解布隆过滤器，你应该知道布隆过滤器原理是采用多种哈希方法，将存储项的不同哈希映射到位数组上，查询时通过对这些位进行检查来判断是否存在。

而布谷鸟过滤器是对存储项做哈希，将其哈希值取一定位数存储在数组中，查询时通过判断相等位数的哈希是否在数组中来判断是否存在。

为什么选择布谷鸟过滤器？

同样都是存储哈希值，本质上都是存储多位哈希，为什么布谷鸟过滤器更优？

一是由于布谷鸟哈希表更加紧凑，因此可以更加节省空间。
二是因为在查询时，布隆过滤器要采用多种哈希函数进行多次哈希，而布谷鸟过滤器只需一次哈希，因此查询效率很高
三是布谷鸟过滤器支持删除，而布隆过滤器不支持删除

优点有了，缺点呢？相比于布隆过滤器

布谷鸟过滤器采用一种备用候选桶的方案，候选桶与首选桶可以通过位置和存储值互相异或得出，这种对应关系要求桶的大小必须是 2 的指数倍
布隆过滤器插入时计算好哈希直接写入位即可，而布谷鸟过滤器在计算后可能会出现当前位置上已经存储了指纹，这时候就需要将已存储的项踢到候选桶，随着桶越来越满，产生冲突的可能性越来越大，插入耗时越来越高，因此其插入性能相比布隆过滤器很差
插入重复元素：布隆过滤器在插入重复元素时并没有影响，只是对已存在的位再置一遍。而布谷鸟过滤器对已存在的值会做踢出操作，因此重复元素的插入存在上限
布谷鸟过滤器的删除并不完美：有上述重复插入的限制，删除时也会出现相关的问题：删除仅在相同哈希值被插入一次时是完美的，如果元素没有插入便进行删除，可能会出现误删除，这和假阳性率的原因相同；如果元素插入了多次，那么每次删除仅会删除一个值，你需要知道元素插入了多少次才能删除干净，或者循环运行删除直到删除失败为止

优缺点都列出来了，我们再来总结一下。对于这种集合隶属测试问题，大部分情景都是读多写少的，而重复插入并没有什么意义，布谷鸟过滤器的删除虽然不完美但总好过没有，同时还有更优的查询和存储效率，应该说在绝大多数情况下其都是一个性价比更高的选择。

实战指南

细节实现

先说一下布谷鸟过滤器中的概念，过滤器是由很多桶组成的，每个桶存储插入项经过哈希计算后的值，该值只会存储固定位数。

过滤器中有 n 个桶，桶的数量是根据要存储的项的数量计算得来的。通过哈希算法我们可以计算出一个项应该存储在哪个桶中，此外每增加一个哈希算法，就可以对一个项产生一个候选桶，当重复插入时，会把当前存储的项踢到候选桶中去。理论上哈希算法越多，空间利用率越高，但实际测试使用 k=2 个哈希函数就可以达到 98% 的利用率了。

每一个桶会存储多个指纹，这受制于桶的大小，不同的指纹可能映射到同一个桶中。桶越大，空间利用率越高，但同时每次查询扫描同一桶中指纹数越多，因此产生假阳性的概率越高，此时就需要提高存储的指纹位数，用以降低冲突率，维持假阳性率。

在论文中提到了实现布谷鸟过滤器所需的几个参数，主要是

哈希函数个数（k）：哈希个数，取 2 就足够
桶大小（b）：每个桶存储多少个指纹
指纹大小（f）：每个指纹存储键的哈希值的多少位

详细阅读论文，在第五章中作者依靠试验数据告诉了我们如何选择最合适的构建参数，我们可以得到如下结论

过滤器无法 100% 填满，存在最大负载因子 α，那么均摊到每个项上的存储占用空间就是 f/α
当保持过滤器总大小不变时，桶越大负载因子越高，即空间利用率越高，但每个桶存储的指纹越多，查询时可能发生冲突的概率也越高，为了维持假阳性率不变，桶越大，就需要越大的指纹

根据上述的理论依据，得出的相关实验数据有：

使用 k=2 个哈希函数时，当桶大小 b=1（即直接映射哈希表）时，负载因子 α 为 50%，但使用桶大小 b=2、4 或 8 时则分别会增加到 84%、95% 和 98%
为了保证假阳性率 r，需要保证 $2b/2^f\leq r$ ，那么指纹 f 大小约为 $f ≥ log_2(2b/r)=log_2(1/r) + log_2(2b)$ ，那每个项的均摊成本即为 $C ≤ [log_2(1/r) + log_2(2b)]/α$
实验数据表明，当 r>0.002 时。每桶有两个条目比每桶使用四个条目产生的结果略好；当 r 减小到 0.00001<r≤0.002 时，每个桶四个条目可以最小化空间
如果使用半排序桶，可以对每一个存储项减少 1bit 的存储空间，但其仅作用于 b=4 的过滤器

这样一来我们便可以确定如何选择参数来构建我们的布谷鸟过滤器了：

阅读剩余部分