在红花和杜鹃过滤器之间，哪一个在性能上更好？

Question

以往关于布鲁姆和布谷鸟滤波器比较的堆叠溢出问题是13年前(这里)提出的，比红模提前了10年。我想布谷鸟过滤器在收养方面已经相当成熟了。

因此，考虑到这一点，就redis实现而言，在性能方面哪种选择更好呢？考虑到额外的功能(比如删除和插入计数)，布谷鸟过滤器是一个明显的选择吗？有什么取舍吗？

我想实现这些过滤器的“现有用户名”无效。有什么更好的技术吗？

Answer 1

我想布谷鸟过滤器在收养方面已经相当成熟了。

布谷鸟过滤器相对简单，因此不需要“成熟过程”。

尽管如此，自布谷鸟在2014年过滤引言以来，已经提出了许多改进建议(并不断提出)，其中包括：

• 可配置桶
• 加减杜鹃滤光片
• Cuckoo滤波器中的降相关
• 带标签的布谷鸟滤波器
• 优化布库滤波器
• 指数独立布库滤波器(I2CF)
• 利用两种选择的力量在插入过程中选择更好的候选桶

甚至

• CFBF:集成布卢姆滤波器缩短布库滤波器插入时间

这些方法是否都能保证更好的结果(插入性能、查询性能、内存消耗等)对于每个用例，都需要进行比较分析(我不知道这种无偏见的研究)。

至于收养问题：

• 有用不同语言实现杜鹃过滤器的许多GitHub存储库。
• 无论是理论上的改进(见上文)还是布谷鸟滤波器的应用，学术界都有浓厚的兴趣。

因此，记住这一点，就Redis实现而言，在性能方面哪一个是更好的选择？考虑到额外的功能(比如删除和插入计数)，布谷鸟过滤器是一个明显的选择吗？有什么取舍吗？

关于这两种算法的性能和权衡，你提到的问题已经有了很好的答案。它还讨论了为什么性能不仅仅是一个度量(插入性能与查询性能；平均时间与最差时间，等等)。由于Redis实现了在原始布谷鸟滤纸中描述的数据结构(尽管是以高度优化的方式)，所以讨论的所有问题也适用于Redis实现。

请注意，除了Bloom和布谷鸟过滤器之外，还建议了几个附加的近似成员资格查询数据结构，包括异或滤波器、带状滤波器和二元熔断器滤波器。

哪一个最适合于每个用例，需要一个非平凡的分析。