为什么在番石榴的BloomFilter中，实际的假阳性率远远低于期望的假阳性概率？

Question

我使用了一个具有较小的期望假阳性概率(fpp)的Bloom过滤器，得到的结果要少得多：

    BloomFilter<Long> bloomFilter = BloomFilter.create(Funnels.longFunnel(), 1_000_000, .001);
    int c = 0;
    for (int i = 0; i < 1_000_000; i ++) {
        // can replace with random.nextLong() because 1M random.nextLong() can hardly make collision
        if (!bloomFilter.put(Long.valueOf(i))) {
            // There is no duplicated elements so put returns false means false-positive
            c ++;
        }
    }
    System.out.println(c);

我期望1000 (1M * 0.001)假阳性，但结果是127 (如果我使用较大的随机数，结果也将接近120，而不是1000)。

===更新===

这是我的测试：

desired actual    a/d 
0.3     0.12      40%
0.1     0.03      30%
0.03    0.006     20%    (guava's default fpp)
0.01    0.0017    17%
0.003   0.0004    13%
0.001   0.00012   12%
0.0003  0.00003   10%
0.0001  0.000009   9%
0.00003 0.000002   7%
0.00001 0.0000005  5%

Answer 1

如果过滤器中的条目较少，则假阳性概率较低。在测试中，首先计算以空集开始的概率，然后在添加条目时计算概率。这不是正确的方法。

您需要首先向Bloom过滤器中添加100万个条目，然后计算假阳性概率，例如，检查条目是否在未添加的集合中。

for (int i = 0; i < 1_000_000; i ++) {
    bloomFilter.put(Long.valueOf(i));
}
for (int i = 0; i < 1_000_000; i ++) {
    // negative entries are not in the set
    if (!bloomFilter.mightContain(Long.valueOf(-(i + 1)))) {
        c++;
    }
}

Answer 2

BloomFilter提供的唯一保证是，真正的假阳性概率最多是您设置的值。在某些情况下，Bloom过滤器数据结构的性质可能不得不“绕过”实际的FPP。

这可能只是一种情况，BloomFilter必须比你要求的更准确，否则你就走运了。