给定一个大小为 N 位的布隆过滤器和 K 个哈希函数，其中设置了过滤器的 M 位（其中 M <= N）。
是否可以估计插入布隆过滤器的元素数量？
简单示例
我一直在考虑下面的例子，假设一个 100 位的 BF 和 5 个设置为 10 位的散列函数......
最好的情况：假设散列函数真的很完美，并且唯一地映射了一些 X 数量的值，那么给定 10 位已经设置，我们可以说只有 2 个元素插入到 BF
最坏的情况：假设哈希函数不好并且始终映射到同一个位（但彼此之间是唯一的），那么我们可以说 10 个元素已插入到 BF
该范围似乎是 [2,10]，其中该范围内的大约可能由过滤器的误报概率决定 - 我被困在这一点上。
这个问题让我有点担心，因为有更好的算法可以用少量存储来近似计算不同元素的数量。
尽管如此，如果我们必须使用布隆过滤器，让我们假设散列函数是随机预言（所有值都是独立选择的，或者“非常完美”，不要与完美散列混淆）。现在我们有一个球和箱子的问题：假设箱子M里N有球，我们扔了多少球？设B为投出的球数；项目的数量是B/K，因为对于每个项目我们都扔K球。
球和箱过程的标准近似是将每个箱建模为独立的泊松过程；垃圾箱被占用之前的时间呈指数分布。假设1扔所有球所需的时间λ，这个指数分布速率的最大似然估计满足Pr(Exponential[λ] < 1) = M/N，所以1 - exp(-λ) = M/N和λ = -log(1 - M/N)。该参数λ类似于球的数量，因此项目数量的估计值为B ≈ -N log(1 - M/N)/K。
编辑：有N垃圾箱，所以我们需要乘以N.
Wikipedia上的条目为您提供了设置任何特定位的概率的公式，假设哈希函数使所有内容随机化。这是1 - (1-1/m)^kn. 由于过滤器中有m位，这意味着设置的预期/平均位数将为m(1-(1-1/m)^kn). n因此，您可以通过选择n使该值等于实际设置的位数来得出一个合理合理的猜测。
为了了解这种猜测可能有多准确，最好了解所设置的位数的方差。你可以准确地解决这个问题，但这有点让人头疼。您可以使用Var(X) = E(X^2) - E(X)^2. 在这种情况下，E(X^2)主要取决于位对都将被设置的概率，您可以通过考虑诸如“位0已设置且位1已清除且所有其他位均已清除”和“位0是清晰的”和“除了0和之外的所有位1都是清晰的”。