algorithm - 我的布隆过滤器需要多少哈希函数？

Question

Wikipedia说:

An empty Bloom filter is a bit array of m bits, all set to 0. There must also be k different hash functions defined, each of which maps or hashes some set element to one of the m array positions with a uniform random distribution.

这篇文章我看了，但是我不明白k是怎么确定的。它是表大小的函数吗？

此外，在我编写的哈希表中，我使用了一种简单但有效的算法来自动增加哈希的大小。基本上，如果表中超过 50% 的桶被填满，我会将表的大小加倍。我怀疑您可能仍想使用布隆过滤器来减少误报。正确吗？

Answer 1

给定:

• n:您希望过滤器中有多少项(例如 216,553 )
• p:您可接受的误报率 {0..1}(例如 0.01 → 1%)

我们要计算:

• m:布隆过滤器需要的位数
• k:我们应该应用的哈希函数的数量

公式:

m = -n*ln(p)/(ln(2)^2) 位数
k = m/n * ln(2) 散列函数的数量

在我们的例子中:

• m = -216553*ln(0.01)/(ln(2)^2) = 997263/0.48045 = 2,075,686 位 (253 kB)
• k = m/n * ln(2) = 2075686/216553 * 0.693147 = 6.46 哈希函数(7 个哈希函数)

Note: Any code released into public domain. No attribution required.