为什么在 Guava Bloom Filter 中实际的误报率远低于预期的误报率？

Question

我使用了所需误报概率 (fpp) 较小的布隆过滤器，得到的结果要少得多：

    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

BloomFilter 提供的唯一保证是真正的误报概率最多您设置的值。在某些情况下，Bloom Filter 数据结构的性质可能必须 "round" 实际 FPP 下降。

这可能只是 BloomFilter 必须比您要求的更准确的情况，否则您很幸运。

Answer 2

如果过滤器中的条目较少，则误报概率较低。在您的测试中，您从一个空的集合开始计算概率，然后添加条目。这不是正确的方法。

您需要先向 Bloom 过滤器添加 100 万个条目，然后然后计算误报概率，例如检查条目是否在您没有的集合中' t 添加。

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++;
    }
}

为什么在 Guava Bloom Filter 中实际的误报率远低于预期的误报率？

Why actual false positives are much less than desired false positive probability in Guava's BloomFilter?

bloom-filter

false-positive

guava