给定大小为N位和K个散列函数的布隆过滤器,其中设置了滤波器的M位(其中M <= N). 是否可以近似插入布隆过滤器的元素数量？ 简单的例子 我一直在考虑以下示例,假设一个100位的BF和5个散列函数,其中设置了10位… 最佳情况：假设散列函数非常完美并且为某些X个值唯一映射一个位,那么已经设置了10位,我们可以说在BF中只插入了2个元素 最糟糕的情况：假设哈希函数是坏的并且一致地映射到相同的位(但彼此之间是唯一的),那么我们可以说已经将10个元素插入到BF中 范围似乎是[2,10],其中这个范围内的大概可能是由滤波器的假阳性概率决定的 – 我在这一点上陷入困境.
解决方法
这个问题让我有点担心,因为有大约
better algorithms用于计算具有少量存储的不同元素的数量.
然而,如果我们必须使用Bloom过滤器,我们假设散列函数是随机的oracles(所有值独立选择,或“非常完美”,不要与完美散列混淆).现在我们有一个球和箱子的问题：考虑到N个箱子中有M个球,我们扔了多少个球？设B为抛出的球数;项目数是B / K,因为每个项目我们扔K球.
球和箱过程的标准近似是将每个箱建模为独立的泊松过程; bin被占用之前的时间是指数分布的.假设1是抛出所有球所花费的时间,该指数分布的速率的最大似然估计λ满足Pr(指数[λ] <1)= M / N,所以1-exp(-λ) = M / N且λ= -log(1-M / N).参数λ类似于球的数量,因此项目数的估计是B≈-N log(1-M / N)/ K. 编辑：有N个箱子,所以我们需要乘以N.
