给定一个大小为 N 位的布隆过滤器和 K 个哈希函数，其中设置了过滤器的 M 位(其中 M <= N)。
是否可以估算插入布隆过滤器的元素数量？
简单示例
我一直在考虑以下示例，假设 BF 为 100 位和 5 个哈希函数，其中设置了 10 位...
最佳情况:假设散列函数非常完美并且可以唯一地映射一些 X 个值，然后给定 10 位，我们可以说只有 2 个元素插入到 BF 中
最坏的情况:假设哈希函数是错误的并且始终映射到相同的位(但彼此之间是唯一的)，那么我们可以说 BF 中插入了 10 个元素
范围似乎是 [2,10]，这个范围内的 abouts 可能是由过滤器的误报概率决定的 - 我卡在了这一点上。
最佳答案
这个问题让我有点担心，因为有 better algorithms用于近似计算具有少量存储空间的不同元素的数量。
尽管如此，如果我们必须使用布隆过滤器，让我们假设散列函数是随机预言(所有值都是独立选择的，或者“非常完美”，不要与完美散列相混淆)。现在我们有一个球和垃圾箱问题:鉴于 M的 N垃圾箱里有球，我们扔了多少个球？让B是 throw 的球数；项目数是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 bins，所以我们需要乘以 N .
关于c++ - 计算布隆过滤器的近似种群，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9103315/