Struct selectors::bloom::BloomFilter

pub struct BloomFilter {
    // some fields omitted
}

A counting Bloom filter with 8-bit counters. For now we assume that having two hash functions is enough, but we may revisit that decision later.

The filter uses an array with 2**KeySize entries.

Assuming a well-distributed hash function, a Bloom filter with array size M containing N elements and using k hash function has expected false positive rate exactly

$ (1 - (1 - 1/M)^{kN})k $

because each array slot has a

$ (1 - 1/M)^{kN} $

chance of being 0, and the expected false positive rate is the probability that all of the k hash functions will hit a nonzero slot.

For reasonable assumptions (M large, kN large, which should both hold if we're worried about false positives) about M and kN this becomes approximately

$$ (1 - \exp(-kN/M))^k $$

For our special case of k == 2, that's $(1 - \exp(-2N/M))^2$, or in other words

$$ N/M = -0.5 * \ln(1 - \sqrt(r)) $$

where r is the false positive rate. This can be used to compute the desired KeySize for a given load N and false positive rate r.

If N/M is assumed small, then the false positive rate can further be approximated as 4*N^2/M2. So increasing KeySize by 1, which doubles M, reduces the false positive rate by about a factor of 4, and a false positive rate of 1% corresponds to about M/N == 20.

What this means in practice is that for a few hundred keys using a KeySize of 12 gives false positive rates on the order of 0.25-4%.

Similarly, using a KeySize of 10 would lead to a 4% false positive rate for N == 100 and to quite bad false positive rates for larger N.

Methods

impl BloomFilter

fn new() -> BloomFilter

Creates a new bloom filter.

fn clear(&mut self)

fn insert<T: BloomHash>(&mut self, elem: &T)

Inserts an item into the bloom filter.

fn remove<T: BloomHash>(&mut self, elem: &T)

Removes an item from the bloom filter.

fn might_contain<T: BloomHash>(&self, elem: &T) -> bool

Check whether the filter might contain an item. This can sometimes return true even if the item is not in the filter, but will never return false for items that are actually in the filter.

Trait Implementations

impl Clone for BloomFilter

fn clone(&self) -> BloomFilter

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.