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

Is a bloom filter with only one input hash still a bloom filter?

如果我实现了仅使用一种哈希算法(例如 murmur)的布隆过滤器,这仍被视为布隆过滤器吗?

例如,如果 a 散列为 5,则过滤器的位 5 将被设置。如果 b 散列为 1,则过滤器的位 1 将被设置,依此类推...

要将某些东西视为布隆过滤器,是否必须至少设置过滤器中的两位?如果只设置了一位,是不是叫别的?

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

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

顺便说一下,你仍然可以选择 k 作为最节省 space 的一个,即使你只使用一个 "application hash function"(比如 64 位的 Murmur 哈希) .您只需选择 "Bloom hash functions" 作为此 "application hash function"(64 位 Murmur 哈希)的函数,就像这样(假设 int 是 32 位而 long 是 64 位) :

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

这实际上比计算倍数 "application hash functions" 更容易 并且 更快。乍一看,它看起来像这样:

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 中的布隆过滤器实现。