Trait bloom_filter_simple::BloomFilter

pub trait BloomFilter {
    pub fn insert<T: Hash>(&mut self, data: &T);
    pub fn contains<T: Hash>(&self, data: &T) -> bool;
}

This trait defines the basic functionality supported by the bloom filters in this library.

Required methods

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

Insert data into the filter.

Intended Behavior

A type implementing BloomFilter should implement insert with respect to the following points:

• It should be possible to insert the same element multiple times.
• It should be possible to insert any type implementing Hash.

Examples

How insert of a type implementing BloomFilter might be used:

use bloom_filter_simple::{BloomFilter, DefaultBloomFilter};

fn bloom_filter_insert() {
    let mut bloom_filter = DefaultBloomFilter::new(5, 0.001);
    bloom_filter.insert(&"Hello!");
    bloom_filter.insert(&5);
    bloom_filter.insert(&"Hello!");

    assert_eq!(true, bloom_filter.contains(&"Hello!"));
}

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

Check whether data is contained in the bloom filter.

Intended Behavior

Checking whether data is contained in a bloom filter must never result in a false negative, i.e., if an element 'x' has been inserted into the filter, contains(&x) will always return true.

In contrast, contains can result in false positive, i.e., contains(&x) can return true, even if x has not been inserted yet. The chance of this happending depends on the number of elements in the bloom filter, and the number of hash functions that are used. When initializing one of the filters provided in this crate, you can specify the desired false positive probability.

A type implementing BloomFilter should implement contains with respect to the following points:

• contains(&x) must return true if x has been inserted into the filter
• contains(&x) can return true even if x has not been inserted into the filter
• It should be possible to check any type implementing Hash.

Examples

How contains of a type implementing BloomFilter might be used:

use bloom_filter_simple::{BloomFilter, DefaultBloomFilter};
fn bloom_filter_insert() {
    let mut bloom_filter = DefaultBloomFilter::new(5, 0.001);
    bloom_filter.insert(&"Hello!");
    // This assert will never fail
    assert_eq!(true, bloom_filter.contains(&"Hello!"));
    // This assert can fail with a probability of p(fp) < 0.001
    assert_eq!(false, bloom_filter.contains(&"Goodbye!"));
}

Loading content...

Implementors

impl BloomFilter for SeededBloomFilter

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

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

impl<H1, H2> BloomFilter for KMBloomFilter<H1, H2> where
    H1: Hasher + Default,
    H2: Hasher + Default, 

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

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

Loading content...