Почему фактические ложные срабатывания намного меньше желаемой вероятности ложных срабатываний в BloomFilter Guava?

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

Вероятность ложного срабатывания ниже, если в фильтре меньше записей.В своем тесте вы вычисляете вероятность, начиная с пустого набора, а затем добавляя записи.Это не правильный путь.

Сначала необходимо добавить 1 миллион записей в фильтр Блума, а , а затем вычислить вероятность ложного положительного результата, например, проверяя, есть ли записи в наборе.что вы не добавили.

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 Filter может «округлять» фактический FPP вниз.

Это может быть просто тот случай, когда BloomFilter должен быть более точным, чем вы просили,или тебе повезло.