使用布隆过滤器的好处是什么？

Question

我正在阅读绽放过滤器，它们看起来很傻。使用Bloom
Bloom过滤器可以完成的任何事情，都可以使用单个哈希函数而不是多个哈希函数在更少的空间内更有效地完成，或者就是这样。为什么要使用布隆过滤器，它有什么用？

Answer 1

从维基百科：

与其他表示集的数据结构相比，Bloom筛选器在空间方面具有很大的优势，例如用于自平衡二进制html" target="_blank">搜索树，尝试，哈希表或简单数组或条目的链接列表的集合。其中大多数要求至少存储数据本身，这可能需要少量的位（对于小整数）到任意数量的位（例如对于字符串）（重试是例外，因为它们可以在具有相同前缀的元素）。链接结构会为指针带来额外的线性空间开销。另一方面，具有1％误差和k的最佳值的Bloom滤波器每个元素仅需要9.6位-不管元素的大小如何。这种优势部分是由于其紧凑性（继承自数组，部分是由于其概率性质。如果1％的误报率似乎过高，则每次我们为每个元素增加4.8位时，我们将其降低十倍。

我很清楚

Bloom过滤器不存储元素本身，这是关键点。您不使用Bloom过滤器来测试是否存在某个元素，而是使用它来测试它是否肯定 不
存在，因为它可以确保不会出现假阴性。这使您不必为集合中不存在的元素（例如用于查找它们的磁盘IO）做额外的工作。

而且所有这些空间都比哈希表之类的空间小得多（对于大型数据集，哈希表可能会部分地位于磁盘上）。尽管可以将Bloom过滤器与哈希表之类的结构 结合
使用，但是一旦确定该元素有可能出现。

因此，示例使用模式可能是：

您在磁盘上有很多数据-您决定要确定的错误界限（例如1％），该界限规定了 m 的值。然后确定最佳 k
（根据文章中给出的公式）。您一次从此磁盘绑定数据填充过滤器。

现在，您已将筛选器放入RAM。当需要处理某些元素时，可以查询过滤器以查看它是否有可能存在于数据集中。如果没有，则不会进行任何额外的工作。没有磁盘读取，等等。（如果是哈希或树，则必须这样做）。

否则，如果过滤器显示“是的，则在其中”，则有1％的可能性是错误的，因此您必须进行必要的工作才能找出答案。99％的时间，它确实 会
在那儿，所以这项工作并非一无是处。