Struct BloomFilter 

pub struct BloomFilter<T, B = SipHasherBuilder> { /* private fields */ }

A space-efficient probabilistic data structure to test for membership in a set.

At its core, a bloom filter is a bit array, initially all set to zero. K hash functions map each element to K bits in the bit array. An element definitely does not exist in the bloom filter if any of the K bits are unset. An element is possibly in the set if all of the K bits are set. This particular implementation of a bloom filter uses two hash functions to simulate K hash functions. Additionally, it operates on only one “slice” in order to have predictable memory usage.

Examples

use probabilistic_collections::bloom::BloomFilter;

let mut filter = BloomFilter::<String>::new(10, 0.01);

assert!(!filter.contains("foo"));
filter.insert("foo");
assert!(filter.contains("foo"));

filter.clear();
assert!(!filter.contains("foo"));

assert_eq!(filter.len(), 96);
assert_eq!(filter.hasher_count(), 7);

Implementations

impl<T> BloomFilter<T>

pub fn new(item_count: usize, fpp: f64) -> Self

Constructs a new, empty BloomFilter with an estimated max capacity of item_count items, and a maximum false positive probability of fpp.

Examples

use probabilistic_collections::bloom::BloomFilter;

let filter = BloomFilter::<String>::new(10, 0.01);

pub fn from_item_count(bit_count: usize, item_count: usize) -> Self

Constructs a new, empty BloomFilter with bit_count bits, and an estimated max capacity of item_count items.

Examples

use probabilistic_collections::bloom::BloomFilter;

let filter = BloomFilter::<String>::from_item_count(100, 10);

pub fn from_fpp(bit_count: usize, fpp: f64) -> Self

Constructs a new, empty BloomFilter with bit_count bits, and a maximum false positive probability of fpp.

Examples

use probabilistic_collections::bloom::BloomFilter;

let filter = BloomFilter::<String>::from_fpp(100, 0.01);

impl<T, B> BloomFilter<T, B>

where B: BuildHasher,

pub fn with_hashers(item_count: usize, fpp: f64, hash_builders: [B; 2]) -> Self

Constructs a new, empty BloomFilter with an estimated max capacity of item_count items, a maximum false positive probability of fpp, and two hasher builders for double hashing.

Examples

use probabilistic_collections::bloom::BloomFilter;
use probabilistic_collections::SipHasherBuilder;

let filter = BloomFilter::<String>::with_hashers(
    10,
    0.01,
    [SipHasherBuilder::from_seed(0, 0), SipHasherBuilder::from_seed(1, 1)],
);

pub fn from_item_count_with_hashers( bit_count: usize, item_count: usize, hash_builders: [B; 2], ) -> Self

Constructs a new, empty BloomFilter with bit_count bits, an estimated max capacity of item_count items, and two hasher builders for double hashing.

Examples

use probabilistic_collections::bloom::BloomFilter;
use probabilistic_collections::SipHasherBuilder;

let filter = BloomFilter::<String>::from_item_count_with_hashers(
    100,
    10,
    [SipHasherBuilder::from_seed(0, 0), SipHasherBuilder::from_seed(1, 1)],
);

pub fn from_fpp_with_hashers( bit_count: usize, fpp: f64, hash_builders: [B; 2], ) -> Self

Constructs a new, empty BloomFilter with bit_count bits, a maximum false positive probability of fpp, and two hasher builders for double hashing.

Examples

use probabilistic_collections::bloom::BloomFilter;
use probabilistic_collections::SipHasherBuilder;

let filter = BloomFilter::<String>::from_fpp_with_hashers(
    100,
    0.01,
    [SipHasherBuilder::from_seed(0, 0), SipHasherBuilder::from_seed(1, 1)],
);

pub fn insert<U>(&mut self, item: &U)

where T: Borrow<U>, U: Hash + ?Sized,

Inserts an element into the bloom filter.

Examples

use probabilistic_collections::bloom::BloomFilter;

let mut filter = BloomFilter::<String>::new(10, 0.01);

filter.insert("foo");

pub fn contains<U>(&self, item: &U) -> bool

where T: Borrow<U>, U: Hash + ?Sized,

Checks if an element is possibly in the bloom filter.

Examples

use probabilistic_collections::bloom::BloomFilter;

let mut filter = BloomFilter::<String>::new(10, 0.01);

assert!(!filter.contains("foo"));
filter.insert("foo");
assert!(filter.contains("foo"));

pub fn len(&self) -> usize

Returns the number of bits in the bloom filter.

Examples

use probabilistic_collections::bloom::BloomFilter;

let filter = BloomFilter::<String>::from_fpp(100, 0.01);

assert_eq!(filter.len(), 100);

pub fn is_empty(&self) -> bool

Returns true if the bloom filter is empty.

Examples

use probabilistic_collections::bloom::BloomFilter;

let filter = BloomFilter::<String>::from_fpp(100, 0.01);

assert!(!filter.is_empty());

pub fn hasher_count(&self) -> usize

Returns the number of hash functions used by the bloom filter.

Examples

use probabilistic_collections::bloom::BloomFilter;

let filter = BloomFilter::<String>::new(10, 0.01);

assert_eq!(filter.hasher_count(), 7);

pub fn clear(&mut self)

Clears the bloom filter, removing all elements.

Examples

use probabilistic_collections::bloom::BloomFilter;

let mut filter = BloomFilter::<String>::new(10, 0.01);

filter.insert("foo");
filter.clear();

assert!(!filter.contains("foo"));

pub fn count_ones(&self) -> usize

Returns the number of set bits in the bloom filter.

Examples

use probabilistic_collections::bloom::BloomFilter;
use probabilistic_collections::SipHasherBuilder;

let mut filter = BloomFilter::<String>::from_fpp_with_hashers(
    100,
    0.01,
    [SipHasherBuilder::from_seed(0, 0), SipHasherBuilder::from_seed(1, 1)],
);
filter.insert("foo");

assert_eq!(filter.count_ones(), 7);

pub fn count_zeros(&self) -> usize

Returns the number of unset bits in the bloom filter.

Examples

use probabilistic_collections::bloom::BloomFilter;
use probabilistic_collections::SipHasherBuilder;

let mut filter = BloomFilter::<String>::from_fpp_with_hashers(
    100,
    0.01,
    [SipHasherBuilder::from_seed(0, 0), SipHasherBuilder::from_seed(1, 1)],
);
filter.insert("foo");

assert_eq!(filter.count_zeros(), 93);

pub fn estimated_fpp(&self) -> f64

Returns the estimated false positive probability of the bloom filter. This value will increase as more items are added.

Examples

use probabilistic_collections::bloom::BloomFilter;

let mut filter = BloomFilter::<String>::new(100, 0.01);
assert!(filter.estimated_fpp() < std::f64::EPSILON);

filter.insert("foo");
assert!(filter.estimated_fpp() > std::f64::EPSILON);
assert!(filter.estimated_fpp() < 0.01);

pub fn hashers(&self) -> &[B; 2]

Returns a reference to the bloom filter’s hasher builders.

Examples

use probabilistic_collections::bloom::BloomFilter;

let filter = BloomFilter::<String>::new(10, 0.01);
let hashers = filter.hashers();

Trait Implementations

impl<T: Debug, B: Debug> Debug for BloomFilter<T, B>

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

Formats the value using the given formatter.

impl<T: PartialEq, B: PartialEq> PartialEq for BloomFilter<T, B>

fn eq(&self, other: &BloomFilter<T, B>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, B> StructuralPartialEq for BloomFilter<T, B>