Struct selectors::bloom::CountingBloomFilter

pub struct CountingBloomFilter<S> where
    S: BloomStorage,  { /* fields omitted */ }

A counting Bloom filter with parameterized storage to handle counters of different sizes. 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/M^2. 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.

Implementations

impl<S> CountingBloomFilter<S> where
    S: BloomStorage, 

pub fn new() -> Self

Creates a new bloom filter.

pub fn clear(&mut self)

pub fn is_zeroed(&self) -> bool

pub fn insert_hash(&mut self, hash: u32)

Inserts an item with a particular hash into the bloom filter.

pub fn remove_hash(&mut self, hash: u32)

Removes an item with a particular hash from the bloom filter.

pub fn might_contain_hash(&self, hash: u32) -> bool

Check whether the filter might contain an item with the given hash. 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<S: Clone> Clone for CountingBloomFilter<S> where
    S: BloomStorage, 

fn clone(&self) -> CountingBloomFilter<S>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<S> Debug for CountingBloomFilter<S> where
    S: BloomStorage, 

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<S: Default> Default for CountingBloomFilter<S> where
    S: BloomStorage, 

fn default() -> CountingBloomFilter<S>

Returns the “default value” for a type.