Struct rust_algorithm_club::collections::BloomFilter

pub struct BloomFilter<T: ?Sized> { /* private fields */ }

A space efficient probablistic data structures offering an approximate containment test with only false positive error.

The false positive error probability ε of a Bloom filter is defined as the probability that a Bloom filter claims an element is contained in it but actually not.

The count of hash functions denoted by k indicates thant k different hash functions that map k position on the bit array. Typically k is a small constant depends on error probability ε.

The underlying container is a bit array of m bits, where the optimal m is proportional to count of hash functions k.

Cheat sheet:

• m: total bits (memory usage)
• n: expected number of input elements (cardinality)
• k: number of hash functions counted for each input
• ε: expected false positive error probability

References:

• Google Guava: BloomFilter
• Onat: Let’s implement a Bloom Filter

Implementations

impl<T: ?Sized> BloomFilter<T>

pub fn new(capacity: usize, err_rate: f64) -> Self

Creates an empty Bloom filter with desired capacity and error rate.

This constructor would give an optimal size for bit array based on provided capacity and err_rate.

Parameters

• capacity - Expected size of elements will put in.
• err_rate - False positive error probability.

pub fn insert(&mut self, elem: &T) where
    T: Hash, 

Inserts an element into the container.

This function simulates multiple hashers with only two hashers using the following formula:

g_i(x) = h1(x) + i * h2(x)

Parameters

• elem - Element to be inserted.

Complexity

Linear in the size of hash_fn_count k.

pub fn contains(&self, elem: &T) -> bool where
    T: Hash, 

Returns whether an element is present in the container.

Parameters

• elem - Element to be checked whether is in the container.

Complexity

Linear in the size of hash_fn_count k.