algorithm - 布隆过滤器或布谷鸟哈希？

Question

你更偏向于哪个，为什么？

它们都可以用来完成相似的任务，但是我很好奇，看看人们在实际应用中使用了什么，以及这样做的理由。

Answer 1

Bloom过滤器和Cuckoo过滤器在类似的情况下使用，但是通常有很多差异，这些差异通常确定哪个是更好的选择。

Bloom过滤器在数据库引擎内部使用，尤其是Apache Cassandra。正如其他张贴者所说，其原因是为了减少慢速设置操作的成本。基本上，任何“成本高昂”的操作都可以使用布隆过滤器来减少已完成检查的次数。

当今SaaS模型的另一个常见示例是带有按次计费的远程REST服务。任何具有二进制答案的API调用（例如“此地址是否无效”）都可以使用布隆过滤器消除90％以上的重复查询！请注意，由于Bloom和Cuckoo过滤器具有误报，因此它们对于逆运算“此地址有效”无效。

要记住的重要一点是，Bloom和Cuckoo过滤器没有误报。这使得这些过滤器可用于诸如“是否肯定不是垃圾邮件”之类的检查，但不适用于无法接受误报的操作（如检查用户权限）。在这方面，它们可以在概念上被视为与高速缓存相反。布卢姆/布谷鸟过滤器和高速缓存都主要用于降低具有布尔答案的昂贵操作的成本，除了高速缓存没有误报，布卢姆/杜鹃没有误报。

杜鹃/花朵之间的显着差异包括：


组合。只要使用相同的参数创建Bloom过滤器，就可以有效地合并它们。既快速又几乎没有带宽。这就是为什么您看到它们在大规模分布式系统中频繁使用的原因，而交换Bloom过滤器的速度很快。布谷鸟过滤器不容易组合，因此在这种情况下使用率会降低。
误报率。布谷鸟过滤器更节省空间。这两种结构的许多用例都集中在底层网络上。在弱硬件上，对于相同的误报率，杜鹃过滤器的效率提高约40％可能很重要。使用c ++的参考实现对每个存储桶中的项目进行排序，以节省更多空间，并利用存储桶中项目的位置存储较小的指纹。我稍后会提到的其他库（包括我的库）似乎都没有这样做。如果有人使用过我的库，我可以添加它:)。
恒定的误报率。布隆过滤器超出设计尺寸时，其误报率渐近恶化。您可以永远插入项目，但最终您的误报率将接近100％。基于Cuckoo散列的Cuckoo筛选器具有一定的容量，实际插入将失败。重复插入非随机项目哈希值可能会导致布谷鸟过滤器插入失败，可能远远超出其设计的填充水平。
速度。这是主观的，并且在很大程度上取决于硬件，但是在一般情况下（以我的经验），布谷鸟过滤器通常更快。大多数布隆过滤器设计都会运行一次哈希函数两次。特别是在使用安全哈希函数时，与仅对插入的项目哈希一次的Cuckoo过滤器相比，这可能是一个很大的障碍。我看过的代码对Bloom和Cuckoo过滤器使用了各种哈希函数。 Google的Guava Bloom使用Murmur3，许多其他实现使用SHA1或其他方式。如果可以为您的用例利用哈希冲突，请确保库使用安全哈希。重要的是要知道，布隆过滤器的插入时间大致恒定，而布谷鸟过滤器的插入时间则是平均时间。随着布谷鸟过滤器进入容量的百分之几之内，插入速度会大大降低。即使这样，只有插入速度变慢，所有其他操作都是恒定的平均时间。
灵活性。 Bloom过滤器仅支持插入和包含。布谷鸟过滤器还支持删除和有限计数。在参考设计中，布谷鸟过滤器可以确定插入项目的次数，最多7次。布隆过滤器只能确定是/否。布谷鸟过滤器还支持删除插入的项目，与Bloom相比，在很多用例中都有很大的好处。使用Bloom过滤器时，由于您无法删除旧项目，因此在“满”（估计误报率超过阈值）时从头开始重新创建过滤器是相当标准的。请注意，当插入开始失败时，使用Cuckoo过滤器仍会重建过滤器，因此，根据使用情况，这可能没有意义。在某些情况下，布谷鸟过滤器更有用，因为您可以删除项目以使其保持在过滤器限制之内，而不用重建。
支持。布谷鸟过滤器是新的，稳定的库对于许多语言来说根本不存在。


Bloom过滤器的最大优点是，它们在大多数语言中都具有更成熟的库支持。科学家还更好地理解了布隆过滤器背后的数学原理。布谷鸟过滤器的大多数特性都是凭经验确定的，而布隆过滤器具有坚实的数值基础。这不包括用于实时系统和关键系统的Cuckoo过滤器，这些过滤器必须对其性能进行验证，即使实验证据表明Cuckoo过滤器在大多数情况下的性能也更好。

Shameless Plug：我是Java的Cuckoo筛选器库的开发人员。 CuckooFilter4J。它缺少本文中使用的存储桶半排序，因此空间效率略低于参考实现。在项目自述文件中，我具有我所知道的其他实现的链接。哪种结构更好取决于您的用例，但主要取决于您的语言是否存在可靠的Cuckoo过滤器实现。

在生产中使用布谷鸟/布鲁姆滤清器之前，您绝对应该查看源代码。在编写我自己的库之前，我通读了各种库。由于32位底层数组或明显的性能问题，它们中的许多都有静默的大小限制。多数测试为零。 Google的Guava Bloom实施迄今为止具有最佳的代码质量和测试（并支持64位数组限制）。 Guava Bloom的唯一缺点是它没有使用安全哈希函数的选项，并且不是多线程的。

在生产系统中，您可能需要多线程以提高速度。番石榴绽放的答案是为每个线程创建不同的过滤器，并偶尔合并它们。由于无法合并Cuckoo过滤器，因此我在Cuckoo过滤器库中添加了并发线程。我知道的另一个线程不是线程安全的或不是并发的。