只有一个输入哈希的布隆过滤器仍然是布隆过滤器吗?
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 中的布隆过滤器实现。
如果我实现了仅使用一种哈希算法(例如 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 中的布隆过滤器实现。