algorithm - 使用布隆过滤器有什么好处？

Question

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

Answer 1

来自 Wikipedia :

Bloom filters have a strong space advantage over other data structures for representing sets, such as self-balancing binary search trees, tries, hash tables, or simple arrays or linked lists of the entries. Most of these require storing at least the data items themselves, which can require anywhere from a small number of bits, for small integers, to an arbitrary number of bits, such as for strings (tries are an exception, since they can share storage between elements with equal prefixes). Linked structures incur an additional linear space overhead for pointers. A Bloom filter with 1% error and an optimal value of k, on the other hand, requires only about 9.6 bits per element — regardless of the size of the elements. This advantage comes partly from its compactness, inherited from arrays, and partly from its probabilistic nature. If a 1% false positive rate seems too high, each time we add about 4.8 bits per element we decrease it by ten times.

对我来说很清楚。

布隆过滤器本身不存储元素，这是关键点。您不使用布隆过滤器来测试元素是否存在，而是使用它来测试它是否肯定是 不是 目前，因为它保证没有漏报。这使您无需为集合中不存在的元素做额外的工作(例如磁盘 IO 来查找它们)。

并且所有空间都比哈希表之类的空间要小得多(对于大型数据集，它可能部分位于磁盘上)。尽管您可以将布隆过滤器与哈希表等结构结合使用，但一旦您确定该元素有机会出现。

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

你在磁盘上有很多数据——你决定你想要的错误界限(例如 1%)，它规定了 m 的值。然后确定最优k(根据文章中给出的公式)。您可以使用此磁盘绑定(bind)数据填充过滤器一次。

现在您在 RAM 中拥有过滤器。当您需要处理某些元素时，您可以查询过滤器以查看它是否有可能存在于您的数据集中。如果没有，则不会进行额外的工作。没有磁盘读取等(如果它是散列或树等，您将不得不这样做)。

否则，如果过滤器显示“是的，它就在那里”，则有 1% 的可能性是错误的，因此您需要做一些必要的工作来找出答案。 99% 的情况下，它真的会在那里，所以这项工作并非徒劳。