bloom-filter - 只有一个输入哈希的布隆过滤器仍然是布隆过滤器吗？

Question

如果我实现了只使用一种散列算法的布隆过滤器(例如 murmur)，这是否仍被视为布隆过滤器？

例如，如果 a散列到 5 ，然后将设置过滤器的第 5 位。如 b散列到 1 ，然后将设置过滤器的第 1 位，依此类推...

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

Answer 1

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

为了能够更好地压缩:这里是带有 k=1 的布隆过滤器是最好的。另见论文 "Compressed Bloom Filters"来自迈克尔·米岑马赫。

加速查找和更新:使用较低的 k是比较快的。

顺便说一句，你仍然可以选择 k成为最节省空间的一个，即使您只使用一个“应用程序哈希函数”(如 64 位的 Murmur 哈希)。您只需选择“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;
}

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