“判断一个值是否在一个巨大的集合当中”（下文中统称为集合隶属测试），是一种常见的数据处理问题。在以往的经验中，如果允许一定的假阳性率，那么布隆过滤器是首选，而如今我们有了更好的选择：布谷鸟过滤器

布谷鸟过滤器在网络上已经有很多的介绍文章了，本文不再去详细阐述布谷鸟过滤器是什么、其原理是什么，我们直接拿他与布隆过滤器作比较，看看其在实际使用中的优劣

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

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

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

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

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

一是由于布谷鸟哈希表更加紧凑，因此可以更加节省空间。

二是因为在查询时，布隆过滤器要采用多种哈希函数进行多次哈希，而布谷鸟过滤器只需一次哈希，因此查询效率很高

三是布谷鸟过滤器支持删除，而布隆过滤器不支持删除

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

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

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

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

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

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

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

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

将上面的结论与布隆过滤器的每项 $1.44log_2(1/r)$ 对比，可以发现启用半排序时，当 r 4 n |= n >> 8 n |= n >> 16 n |= n >> 32 n++ return uint(n) } func getNumOfKindAndBit(b, f int) { cnt := 0 getNum(0, 0, b, f, &cnt) fmt.Printf("Num of kinds: %v, Num of needed bits: %v\n", cnt, math.Log2(float64(getNextPow2(uint64(cnt))))) }

在 b=4 时，总共有 3786 种排列，小于 4096，即用 12 位即可存储所有的排列索引，而如果直接存储所有指纹，则需要 4X4=16 位，这样节省了 4 位，即对每一个指纹节省了一位。

可以发现，在 b 为 2 时是否启用半排序需要存储的位数相同，没有意义。如果 b 太大则需要存储的索引也会急剧扩张，会在查询性能上有很大的损耗，因此 b=4 是一个性价比最高的选择。

此外编码存储四位指纹的选择是因为其刚好可以用一个十六进制表示，利于存储

使用半排序时的参数选择

使用半排序时，应保证 $ceil(b*(f-1)/8)