只有一个输入哈希的布隆过滤器仍然是布隆过滤器吗?

Question

如果我实现一个只使用一种哈希算法(例如杂音)的布隆过滤器，这仍然被认为是布隆过滤器吗？

例如，如果a哈希5，则将设置过滤器的第 5 位。如果b哈希1，则将设置过滤器的第 1 位，依此类推...

对于被视为布隆过滤器的东西，是否必须在过滤器中至少设置两个位？如果只设置了一个位，它是否称为其他东西？

Answer 1

它仍然是一个布隆过滤器：一个带有k=1的过滤器。根据每个元素的位数，它可能不是最节省空间的。但是人们可能会选择不round(bitsPerKey * log(2))k的原因有很多，主要是：

• 为了能够更好地压缩：这里最好使用带有k=1的布隆过滤器。另请参阅Michael Mitzenmacher的论文"压缩布隆过滤器"。
• 要加快查找和更新速度：使用较低的k速度更快。

顺便说一下，即使你只使用一个"应用程序哈希函数"(如 64 位的 Murmur 哈希)，您仍然可以选择最节省空间的k。您只需选择"Bloom 哈希函数"作为此"应用程序哈希函数"(64 位 Murmur 哈希)的函数，如下所示(假设int是 32 位，long是 64 位)：

long m = murmur(x)
h(x, i) = (int) (m >> 32) + i * (int) m 

这实际上比计算多个"应用程序哈希函数"更容易、更快捷。在一个循环中，它看起来像这样：

long m = murmur(x)
int hash = (int) (m >> 32);
int add = (int) m;
for (int i = 0; i < k; i++) {
... test / set the bit depending on "hash" ...
hash += add;
}

许多布隆过滤器库都是这样做的，例如 Guava 中的布隆过滤器实现。