Struct CountingBloomFilter

pub struct CountingBloomFilter<R = RandomState, S = RandomState> { /* private fields */ }

A standard counting bloom filter that uses a fixed number of bits per counter, supports remove, and estimating the count of the number of items inserted.

Implementations

impl CountingBloomFilter<RandomState, RandomState>

pub fn with_size( num_entries: usize, bits_per_entry: usize, num_hashes: u32, ) -> CountingBloomFilter<RandomState, RandomState>

Create a new CountingBloomFilter that will hold num_entries items, uses bits_per_entry per item, and num_hashes hashes

pub fn with_rate( bits_per_entry: usize, rate: f32, expected_num_items: u32, ) -> CountingBloomFilter<RandomState, RandomState>

create a CountingBloomFilter that uses bits_per_entry entries and expects to hold expected_num_items. The filter will be sized to have a false positive rate of the value specified in rate.

pub fn bits_for_max(max: u32) -> usize

Return the number of bits needed to hold values up to and including max

Example

use bloom::CountingBloomFilter;
// Create a CountingBloomFilter that can count up to 10 on each entry, and with 1000
// items will have a false positive rate of 0.01
let cfb = CountingBloomFilter::with_rate(CountingBloomFilter::bits_for_max(10),
                                         0.01,
                                         1000);

impl<R, S> CountingBloomFilter<R, S>

where R: BuildHasher, S: BuildHasher,

pub fn with_size_and_hashers( num_entries: usize, bits_per_entry: usize, num_hashes: u32, hash_builder_one: R, hash_builder_two: S, ) -> CountingBloomFilter<R, S>

Create a new CountingBloomFilter 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 CountingBloomFilter.

pub fn with_rate_and_hashers( bits_per_entry: usize, rate: f32, expected_num_items: u32, hash_builder_one: R, hash_builder_two: S, ) -> CountingBloomFilter<R, S>

Create a CountingBloomFilter 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 CountingBloomFilter.

pub fn remove<T: Hash>(&mut self, item: &T) -> u32

Remove an item. Returns an upper bound of the number of times this item had been inserted previously (i.e. the count before this remove). Returns 0 if item was never inserted.

pub fn estimate_count<T: Hash>(&self, item: &T) -> u32

Return an estimate of the number of times item has been inserted into the filter. Esitimate is a upper bound on the count, meaning the item has been inserted at most this many times, but possibly fewer.

pub fn insert_get_count<T: Hash>(&mut self, item: &T) -> u32

Inserts an item, returns the estimated count of the number of times this item had previously been inserted (not counting this insertion)

Trait Implementations

impl<R, S> ASMS for CountingBloomFilter<R, S>

where R: BuildHasher, S: BuildHasher,

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

Inserts an item, returns true if this item was already in the filter any number of times

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

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

fn clear(&mut self)

Remove all values from this CountingBloomFilter