data-structures - 布隆过滤器什么时候有用？

Question

我明白是什么让布隆过滤器成为一种有吸引力的数据结构；但是，我发现很难真正理解何时可以使用它们，因为您仍然必须执行您试图避免的昂贵操作，以确保您没有发现误报。因此，他们通常不会增加很多开销吗？例如，维基百科关于布隆过滤器的文章表明它们可用于数据同步。我看到当布隆过滤器为空时第一次会很棒，但说你没有改变任何东西，然后你再次同步你的数据。现在每次对布隆过滤器的查找都会报告文件已经被复制，但我们是否仍然需要执行我们试图避免的较慢的查找任务来实际确保它是正确的？

Answer 1

基本上，您使用布隆过滤器来避免证明数据结构中不存在项目的漫长而艰巨的任务。确定某些东西是否丢失几乎总是比它是否存在更难，因此过滤器有助于弥补寻找无论如何都找不到的东西的损失。它并不总是有效，但是当它起作用时，您会获得巨大的 yield 。