Struct bloom_filter_simple::SeededBloomFilter

pub struct SeededBloomFilter { /* fields omitted */ }

A bloom filter that uses a single Hasher that can be seeded to simulate an arbitrary number of hash functions.

Internally, the implementation uses ahash::AHasher.

Implementations

impl SeededBloomFilter

pub fn new(
    desired_capacity: usize,
    desired_false_positive_probability: f64
) -> Self

Initialize a new instance of SeededBloomFilter that guarantees that the false positive rate is less than desired_false_positive_probability for up to desired_capacity elements.

SeededBloomFilter uses a single hash function that can be seeded to simulate an arbitrary number of hash functions.

Panics

Panics if desired_capacity == 0

Examples

use bloom_filter_simple::{BloomFilter,SeededBloomFilter};

fn main() {
    // We plan on storing at most 10 elements
    let desired_capacity = 10;
    // We want to assure that the chance of a false positive is less than 0.0001.
    let desired_fp_probability = 0.0001;

    // We initialize a new SeededBloomFilter by specifying the desired Hashers as type
    // parameters
    let mut filter = SeededBloomFilter::new(desired_capacity, desired_fp_probability);
}

pub fn approximate_element_count(&self) -> f64

Approximate number of elements stored. Approximation technique taken from Wikipedia:

Wikipedia, "Bloom filter" [Accessed: 02.12.2020]

pub fn approximate_current_false_positive_probability(&self) -> f64

Return the current approximate false positive probability which depends on the current number of elements in the filter.

The probability is given as a value in the interval [0,1] Approximation technique taken from Sagi Kedmi:

S. Kedmi, "Bloom Filters for the Perplexed", July 2017 [Accessed: 02.12.2020]

pub fn union(&self, other: &Self) -> Self

Creates a union of this bloom filter and 'other', which means 'contains' of the resulting bloom filter will always return true for elements inserted in either this bloom filter or in 'other' before creation.

Panics

Panics if the desired capacity or desired false positive probability of 'self' and 'other' differ.

Examples

Union of two bloom filters with the same configuration.

use bloom_filter_simple::{BloomFilter,SeededBloomFilter};

fn main() {
    // The configuration of both bloom filters has to be the same
    let desired_capacity = 10_000;
    let desired_fp_probability = 0.0001;

    // We initialize two new SeededBloomFilter 
    let mut filter_one = SeededBloomFilter::new(desired_capacity, desired_fp_probability);
    let mut filter_two = SeededBloomFilter::new(desired_capacity, desired_fp_probability);
 
    // Insert elements into the first filter
    filter_one.insert(&0);
    filter_one.insert(&1);
 
    // Insert elements into the second filter
    filter_two.insert(&2);
    filter_two.insert(&3);
     
    // Now we retrieve the union of both filters
    let filter_union = filter_one.union(&filter_two);

    // The union will return true for a 'contains' check for the elements inserted 
    // previously into at least one of the constituent filters.
    assert_eq!(true, filter_union.contains(&0));
    assert_eq!(true, filter_union.contains(&1));
    assert_eq!(true, filter_union.contains(&2));
    assert_eq!(true, filter_union.contains(&3));
}

pub fn intersect(&self, other: &Self) -> Self

Creates a intersection of this bloom filter and 'other', which means 'contains' of the resulting bloom filter will always return true for elements inserted both in this bloom filter and in 'other' before creation. The false positive probability of the resulting bloom filter is at most the false positive probability of 'other' or 'self'. The false positive probability of the resulting bloom filter may be bigger than the false positive probability of a new empty bloom filter with the intersecting elements inserted. The functions 'approximate_current_false_positive_probability' and 'approximate_element_count' called on the resulting bloom filter may return too big approximations.

Panics

Panics if the desired capacity or desired false positive probability of 'self' and 'other' differ.

Examples

Intersection of two bloom filters with the same configuration.

use bloom_filter_simple::{BloomFilter,SeededBloomFilter};

fn main() {
    // The configuration of both bloom filters has to be the same
    let desired_capacity = 10_000;
    let desired_fp_probability = 0.0001;

    // We initialize two new SeededBloomFilter 
    let mut filter_one = SeededBloomFilter::new(desired_capacity, desired_fp_probability);
    let mut filter_two = SeededBloomFilter::new(desired_capacity, desired_fp_probability);
 
    // Insert elements into the first filter
    filter_one.insert(&0);
    filter_one.insert(&1);
 
    // Insert elements into the second filter
    filter_two.insert(&1);
    filter_two.insert(&2);
     
    // Now we retrieve the intersection of both filters
    let filter_intersection = filter_one.intersect(&filter_two);

    // The intersection will return true for a 'contains' check for the elements inserted 
    // previously into both constituent filters.
    assert_eq!(false, filter_intersection.contains(&0));
    assert_eq!(true, filter_intersection.contains(&1));
    assert_eq!(false, filter_intersection.contains(&2));
}

pub fn eq_configuration(&self, other: &Self) -> bool

Checks whether two bloom filters were created with the same desired capacity and desired false positive probability.

Trait Implementations

impl BloomFilter for SeededBloomFilter

pub fn insert<T>(&mut self, data: &T) where
    T: Hash, 

Insert data into the filter.

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

Check whether data is contained in the bloom filter.

impl Debug for SeededBloomFilter

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

Formats the value using the given formatter.