Hang when expected number of items is zero

[blp]

When the expected number of items is zero, the number of hashes becomes u32::MAX.

To see the behavior, try this program:

use fastbloom::BloomFilter;

fn main() {
    for expected in std::iter::once(0).chain((0..10).map(|exponent| 1 << exponent)) {
        let bloom_filter = BloomFilter::with_false_pos(0.001).expected_items(expected);
        println!(
            "expected={expected} num_hashes={}",
            bloom_filter.num_hashes()
        );
    }
}

The output with fastbloom 0.14.0:

expected=0 num_hashes=4294967295
expected=1 num_hashes=354
expected=2 num_hashes=177
expected=4 num_hashes=88
expected=8 num_hashes=44
expected=16 num_hashes=22
expected=32 num_hashes=11
expected=64 num_hashes=10
expected=128 num_hashes=10
expected=256 num_hashes=10
expected=512 num_hashes=10

Computing u32::MAX hashes effectively hangs the program.

The number of hashes for small numbers of expected items also seems very large (354 for 1 item?), but doesn't hang the program at least.

[tomtomwombat]

Due to the way bloom filters optimize false positives, this is expected behavior. As the number of expected items decreases, the number of hashes increases to reduce false positives. This is why the hashes is very large for just 1 item, since it minimizes the possibility of a false positive. For 0 items, the number of hashes is infinite (rounded to u32 MAX), which is just the outcome of the formula.

You can to tune the number of hashes or false positive rate explicitly to avoid large number of hashes.

As for specifying expected items = 0, you could use .expected_items(std::max(1, expected)) (I also do not know of a use case for a bloom filter with 0 items haha). There's no reasonable upper bound on the number of hashes. Some users may want an extremely low false pos rate at the cost of long execution time (millions of hashes).

[blp]

@tomtomwombat I think that, specifically, BloomFilter::with_false_pos(0.001).expected_items(0) yielding u32::MAX hashes is unreasonable behavior, but it sounds like you disagree?

[tomtomwombat]

Yes, I would say fastbloom’s behavior is reasonable since in theory the number of hashes depends on a formula with the expected items variable in the denominator.