java - 布隆过滤器从 O(n) 中的整数流中删除重复项

Question

如何创建一个布隆过滤器以从 O(n) 时间复杂度和 O(1) 空间复杂度的整数流中删除重复元素？如果可能的话，如果有人能指出我正确的方向，我将不胜感激？

Answer 1

我很确定这只是：

对于每个元素：

• 检查它是否存在于布隆过滤器中，如果存在，则可能是重复的
• 将其插入布隆过滤器

现在有两个问题：

• 有误报的可能性
• 这不是真正的 O(1) 空间（但有些人可能会说是），因为大小需要在一定程度上取决于（唯一）元素的数量，否则，随着元素数量的增加，错误率会显着增加。

考虑到这些限制，我不相信这些问题中的任何一个都可以避免 - 两者都是使用（仅）布隆过滤器的组成部分。

如果我们处理的不是流，而是一个列表，我们可以通过记录布隆过滤器拾取的所有元素来消除误报，然后再次检查我们的候选列表，以确保它们'是实际的重复。这仍然是 O(n) 时间，但显然不是 O(1) 空间。

Answer 2

Google Guava 提供了一个布隆过滤器实现。

请注意，布隆过滤器本身是不够的。如果布隆过滤器声称一个数字不在其中，那么它不在其中。但是，如果它声称该数字已经在其中，则有可能是错误的。所以你需要有另一个数据结构来确定并使用bloomfilter来减少该数据结构中的查找次数。