Struct bloom::bloom::BloomFilter

pub struct BloomFilter<R = RandomState, S = RandomState> { /* fields omitted */ }

A standard BloomFilter. If an item is instered then contains is guaranteed to return true for that item. For items not inserted contains will probably return false. The probability that contains returns true for an item that was not inserted is called the False Positive Rate.

False Positive Rate

The false positive rate is specified as a float in the range (0,1). If indicates that out of X probes, X * rate should return a false positive. Higher values will lead to smaller (but more inaccurate) filters.

Example Usage

use bloom::{ASMS,BloomFilter};

let expected_num_items = 1000;

// out of 100 items that are not inserted, expect 1 to return true for contain
let false_positive_rate = 0.01;

let mut filter = BloomFilter::with_rate(false_positive_rate,expected_num_items);
filter.insert(&1);
filter.contains(&1); /* true */
filter.contains(&2); /* false */

Methods

impl BloomFilter<RandomState, RandomState>

fn with_size(
    num_bits: usize,
    num_hashes: u32
) -> BloomFilter<RandomState, RandomState>

Create a new BloomFilter with the specified number of bits, and hashes

fn with_rate(
    rate: f32,
    expected_num_items: u32
) -> BloomFilter<RandomState, RandomState>

create a BloomFilter that expects to hold expected_num_items. The filter will be sized to have a false positive rate of the value specified in rate.

impl<R, S> BloomFilter<R, S> where
    R: BuildHasher,
    S: BuildHasher, 

fn with_size_and_hashers(
    num_bits: usize,
    num_hashes: u32,
    hash_builder_one: R,
    hash_builder_two: S
) -> BloomFilter<R, S>

Create a new BloomFilter with the specified number of bits, hashes, and the two specified HashBuilders. Note the the HashBuilders MUST provide independent hash values. Passing two HashBuilders that produce the same or correlated hash values will break the false positive guarantees of the BloomFilter.

fn with_rate_and_hashers(
    rate: f32,
    expected_num_items: u32,
    hash_builder_one: R,
    hash_builder_two: S
) -> BloomFilter<R, S>

Create a BloomFilter that expects to hold expected_num_items. The filter will be sized to have a false positive rate of the value specified in rate. Items will be hashed using the Hashers produced by hash_builder_one and hash_builder_two. Note the the HashBuilders MUST provide independent hash values. Passing two HashBuilders that produce the same or correlated hash values will break the false positive guarantees of the BloomFilter.

fn num_bits(&self) -> usize

Get the number of bits this BloomFilter is using

fn num_hashes(&self) -> u32

Get the number of hash functions this BloomFilter is using

Trait Implementations

impl<R, S> ASMS for BloomFilter<R, S> where
    R: BuildHasher,
    S: BuildHasher, 

fn insert<T: Hash>(&mut self, item: &T) -> bool

Insert item into this BloomFilter.

If the BloomFilter did not have this value present, true is returned.

If the BloomFilter did have this value present, false is returned.

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

Check if the item has been inserted into this bloom filter. This function can return false positives, but not false negatives.

fn clear(&mut self)

Remove all values from this BloomFilter

impl Intersectable for BloomFilter

fn intersect(&mut self, other: &BloomFilter) -> bool

Calculates the intersection of two BloomFilters. Only items inserted into both filters will still be present in self.

Both BloomFilters must be using the same number of bits. Returns true if self changed.

Panics

Panics if the BloomFilters are not using the same number of bits

impl Unionable for BloomFilter

fn union(&mut self, other: &BloomFilter) -> bool

Calculates the union of two BloomFilters. Items inserted into either filters will be present in self.

Both BloomFilters must be using the same number of bits. Returns true if self changed.

Panics

Panics if the BloomFilters are not using the same number of bits