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

Question

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

Answer 1

我相当确定它只是:

对于每个元素:

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

现在有两个问题:

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

我不认为这些问题中的任何一个都可以在限制条件下避免——这两个问题都是(仅)使用布隆过滤器的组成部分。

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