布隆过滤器：评估误报率

Question

给定固定数量的比特（例如槽）（m）和固定数量的哈希函数（k），如何计算理论误报率（p）？

根据维基百科http://en.wikipedia.org/wiki/Bloom_filter，对于误报率（p）和项目数量（n），所需的位数（m）由下式给出：

m = - n * l(p) / (l(2)^2) 

哈希函数的最佳数量 (k) 由

k = m / n * l(2)

给出。

根据维基百科页面给出的公式，我想我可以通过以下方式评估理论误报率（p）：

p = (1 - e(-(k * n/m)))^k

但是维基百科对 (p) 有另一个公式：

p = e(-m/n*(l(2)^2))

，我想，它假设 (k) 是哈希函数的最佳数量。

对于我的示例，我采用了

n = 1000000

和

m = n * 2

，(k) 的最佳值为 1.386，根据前面的公式，理论误报率 (p) 将为 0.382。 让我们选择函数的数量，计算给定固定 (k) 的理论误报率 (p)，并计算所需的理论位数 (m')：

for k = 1, p = .393 and m' = 1941401
for k = 2, p = .399 and m' = 1909344
for k = 3, p = .469 and m' = 1576527
for k = 4, p = .559 and m' = 1210636

过滤器中填充的位越多，我们得到的误报就越多。看起来合乎逻辑。

但是能否确认公式

p = (1 - e(-(k * n/m)))^k

是正确的，可以在给定固定 (k)、(m) 和 (n) 的情况下获得理论误报率？

注意：这个问题似乎已经在这里问过：使用固定数量的函数，在给定误报概率的情况下，如何计算布隆过滤器的大小？但没有答案与我的确切问题相符。 我的布隆过滤器需要多少个哈希函数？可能会令人感兴趣，但同样，它并不完全相同。

问候

Answer 1

m – number of elements in bit array
n – number of items in collection
p – false positive probability  // 0.0 – 1.0
^ – power

p = e^(-(m/n) * (ln(2)^2));

我写了一篇关于布隆过滤器的数学友好教程： https://web.archive.org/web/20141011213433/http://techeffigy.wordpress.com/2014/06/05/bloom-filter-tutorial/