计算布隆过滤器中的正确位数

Question

我正在尝试制作一个可配置的布隆过滤器。在构造函数中，您可以设置过滤器的预测必要容量(n)、期望错误率(p)和散列函数列表(大小为k)。

According to Wikipedia，则以下关系成立(m是位数)：

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

因为我得到了p、n和k作为参数，所以我需要求解m；我得到了以下结果：

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

然而，有一些事情让我觉得我做错了什么。首先，对于足够大的k，p ** (1 / k)将倾向于1，这意味着整个分数定义不明确(因为您可以想见地除以0)。

您可能会注意到的另一件事是，随着p (允许的最大错误率)的增长，m也在增长，这是完全向后的。

我哪里错了？

Answer 1

你确实正确地解决了这个方程式，但是请注意，维基百科声明：

The probability of all of them being 1, which would cause
the algorithm to erroneously claim that the element is in
the set, is often given as:

p ~= (1 - (1 - 1 / m) ** (k * n)) ** k ~= (1 - Exp(-k * n / m)) ** k

这与你所说的非常不同：

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

所以你真正想要的是

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

我把这个算出来了

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