Struct selectors::bloom::CountingBloomFilter[][src]

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.


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

pub fn new() -> Self[src]

Creates a new bloom filter.

pub fn clear(&mut self)[src]

pub fn is_zeroed(&self) -> bool[src]

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

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

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

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

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

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

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

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

Auto Trait Implementations

impl<S> RefUnwindSafe for CountingBloomFilter<S> where
    S: RefUnwindSafe

impl<S> Send for CountingBloomFilter<S> where
    S: Send

impl<S> Sync for CountingBloomFilter<S> where
    S: Sync

impl<S> Unpin for CountingBloomFilter<S> where
    S: Unpin

impl<S> UnwindSafe for CountingBloomFilter<S> where
    S: UnwindSafe

Blanket Implementations

impl<T> Any for T where
    T: 'static + ?Sized

impl<T> Borrow<T> for T where
    T: ?Sized

impl<T> BorrowMut<T> for T where
    T: ?Sized

impl<T> From<T> for T[src]

impl<T, U> Into<U> for T where
    U: From<T>, 

impl<T> ToOwned for T where
    T: Clone

type Owned = T

The resulting type after obtaining ownership.

impl<T, U> TryFrom<U> for T where
    U: Into<T>, 

type Error = Infallible

The type returned in the event of a conversion error.

impl<T, U> TryInto<U> for T where
    U: TryFrom<T>, 

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.