Struct BloomFilter

pub struct BloomFilter<T, const M: usize, const K: usize, S = RandomState> { /* private fields */ }

A Bloom filter.

Note that the number of bits in the Bloom filter is 64 times M because bits are stored in an array of u64’s.

Example

use rust_dsa::BloomFilter;

// First, we create a new Bloom filter.
let mut filter: BloomFilter<_, 32, 2> = BloomFilter::new();

// We can insert some values.
filter.insert('a');
filter.insert('b');
filter.insert('c');

// We can check if the set probably contains values.
assert!(filter.maybe_contains(&'a'));
assert!(filter.maybe_contains(&'b'));
assert!(filter.maybe_contains(&'c'));

// For values not in the set, we may get false positives
// assert!(!filter.maybe_contains(&'z'));

// We can estimate the false positive rate
assert!(filter.false_positive_rate() < 1e-5);

Implementations

impl<T, const M: usize, const K: usize, S> BloomFilter<T, M, K, S>

pub fn new() -> Self

where S: Default,

Creates an empty Bloom filter.

Panics

Panics if M or K is zero.

pub fn with_hashers(hash_builders: [S; K]) -> Self

Creates an empty Bloom filter which will use the given hash builders.

Panics

Panics if M or K is zero.

pub fn is_empty(&self) -> bool

Checks if a Bloom filter is empty (i.e., if all the bits are zero).

Example

use rust_dsa::BloomFilter;

let mut filter: BloomFilter::<_, 4, 2> = BloomFilter::new();
assert!(filter.is_empty());

filter.insert(1);
assert!(!filter.is_empty());

pub fn clear(&mut self)

Sets all the bits to zero.

Example

use rust_dsa::BloomFilter;

let mut filter: BloomFilter::<_, 8, 4> = "hello".chars().collect();
assert!(!filter.is_empty());

filter.clear();
assert!(filter.is_empty());

pub fn count_ones(&self) -> usize

Counts the number of set bits in the Bloom filter.

Example

use rust_dsa::BloomFilter;

let mut filter: BloomFilter::<_, 8, 4> = BloomFilter::from([1, 2, 3]);
assert!(filter.count_ones() > 0);

filter.clear();
assert_eq!(filter.count_ones(), 0);

pub fn epsilon(&self, n: usize) -> f64

Estimates the false positive rate of this Bloom filter if it had n elements in it.

Example

use rust_dsa::BloomFilter;

let filter: BloomFilter<char, 8, 4> = BloomFilter::new();

let expected = 0.15966130015118526;
assert!((filter.epsilon(128) - expected).abs() < 1e-10);

pub fn false_positive_rate(&self) -> f64

Estimates the false positive rate of this Bloom filter based on how many bits are set.

Example

use rust_dsa::BloomFilter;

let filter: BloomFilter<_, 8, 2> = "abcdefgh".chars().collect();

let expected = 0.0009765625;
assert!((filter.false_positive_rate() - expected) < 1e-10);

pub fn approx_len(&self) -> f64

Estimates the number of items in this Bloom filter based on how many bits are set.

Example

use rust_dsa::BloomFilter;

let filter: BloomFilter<_, 16, 4> = BloomFilter::from(["foo", "bar", "baz"]);

assert_eq!(filter.approx_len().round(), 3.0);

impl<T, const M: usize, const K: usize, S> BloomFilter<T, M, K, S>

where T: Hash, S: BuildHasher,

pub fn insert(&mut self, value: T)

Inserts a value into the Bloom filter.

Example

use rust_dsa::BloomFilter;

let mut filter: BloomFilter<_, 10, 4> = BloomFilter::new();

assert!(!filter.maybe_contains(&1)); // guaranteed to return false

filter.insert(1);
filter.insert(2);
filter.insert(3);

// guaranteed to return true
assert!(filter.maybe_contains(&1));
assert!(filter.maybe_contains(&2));
assert!(filter.maybe_contains(&3));

// filter.maybe_contains(4); // may return true or false

pub fn maybe_contains(&mut self, value: &T) -> bool

Queries the Bloom filter for a given value.

If the Bloom filter contains the value, this function is guaranteed to return true, but it may return false positives.

Example

use rust_dsa::BloomFilter;

let mut filter: BloomFilter<_, 8, 2> = BloomFilter::new();
assert!(!filter.maybe_contains(&1));

filter.insert(1);
assert!(filter.maybe_contains(&1));

Trait Implementations

impl<T: Clone, const M: usize, const K: usize, S: Clone> Clone for BloomFilter<T, M, K, S>

fn clone(&self) -> BloomFilter<T, M, K, S>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T, const M: usize, const K: usize, S> Default for BloomFilter<T, M, K, S>

where S: Default,

fn default() -> Self

Returns the “default value” for a type.

impl<T, const M: usize, const K: usize, S> Extend<T> for BloomFilter<T, M, K, S>

where T: Hash, S: BuildHasher + Default,

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, const M: usize, const K: usize, S, const N: usize> From<[T; N]> for BloomFilter<T, M, K, S>

where T: Hash, S: BuildHasher + Default,

fn from(array: [T; N]) -> Self

Converts to this type from the input type.

impl<T, const M: usize, const K: usize, S> FromIterator<T> for BloomFilter<T, M, K, S>

where T: Hash, S: BuildHasher + Default,

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.