Struct PartitionedBloomFilter 

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

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

This particular implementation of a bloom filter uses K partitions and K hash functions. Each hash function maps to a bit in its respective partition. A partitioned bloom filter is more robust than its traditional counterpart, but the memory usage is varies based on how many hash functions you are using.

Examples

use probabilistic_collections::bloom::PartitionedBloomFilter;

let mut filter = PartitionedBloomFilter::<String>::from_item_count(10, 0.01);

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

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

assert_eq!(filter.len(), 98);
assert_eq!(filter.bit_count(), 14);
assert_eq!(filter.hasher_count(), 7);

Implementations

impl<T> PartitionedBloomFilter<T>

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

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

Examples

use probabilistic_collections::bloom::PartitionedBloomFilter;

let filter = PartitionedBloomFilter::<String>::from_item_count(10, 0.01);

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

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

Examples

use probabilistic_collections::bloom::PartitionedBloomFilter;

let filter = PartitionedBloomFilter::<String>::from_bit_count(10, 0.01);

impl<T, B> PartitionedBloomFilter<T, B>

where B: BuildHasher,

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

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

Examples

use probabilistic_collections::bloom::PartitionedBloomFilter;
use probabilistic_collections::SipHasherBuilder;

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

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

Constructs a new, empty PartitionedBloomFilter with bit_count bits per partition, a maximum false positive probability of fpp, and two hash builders for double hashing.

Examples

use probabilistic_collections::bloom::PartitionedBloomFilter;
use probabilistic_collections::SipHasherBuilder;

let filter = PartitionedBloomFilter::<String>::from_bit_count_with_hashers(
    10,
    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::PartitionedBloomFilter;

let mut filter = PartitionedBloomFilter::<String>::from_item_count(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::PartitionedBloomFilter;

let mut filter = PartitionedBloomFilter::<String>::from_item_count(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::PartitionedBloomFilter;

let filter = PartitionedBloomFilter::<String>::from_item_count(10, 0.01);

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

pub fn is_empty(&self) -> bool

Returns true if the bloom filter is empty.

Examples

use probabilistic_collections::bloom::PartitionedBloomFilter;

let filter = PartitionedBloomFilter::<String>::from_item_count(10, 0.01);

assert!(!filter.is_empty());

pub fn bit_count(&self) -> usize

Returns the number of bits in each partition in the bloom filter.

Examples

use probabilistic_collections::bloom::PartitionedBloomFilter;

let filter = PartitionedBloomFilter::<String>::from_item_count(10, 0.01);

assert_eq!(filter.bit_count(), 14);

pub fn hasher_count(&self) -> usize

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

Examples

use probabilistic_collections::bloom::PartitionedBloomFilter;

let filter = PartitionedBloomFilter::<String>::from_item_count(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::PartitionedBloomFilter;

let mut filter = PartitionedBloomFilter::<String>::from_item_count(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::PartitionedBloomFilter;
use probabilistic_collections::SipHasherBuilder;

let mut filter = PartitionedBloomFilter::<String>::from_item_count_with_hashers(
    10,
    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::PartitionedBloomFilter;
use probabilistic_collections::SipHasherBuilder;

let mut filter = PartitionedBloomFilter::<String>::from_item_count_with_hashers(
    10,
    0.01,
    [SipHasherBuilder::from_seed(0, 0), SipHasherBuilder::from_seed(1, 1)],
);
filter.insert("foo");

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

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.

This is a fairly rough estimate as it takes the overall fill ratio of all partitions instead of considering each partition individually.

Examples

use probabilistic_collections::bloom::PartitionedBloomFilter;

let mut filter = PartitionedBloomFilter::<String>::from_item_count(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::PartitionedBloomFilter;

let filter = PartitionedBloomFilter::<String>::from_item_count(100, 0.01);
let hashers = filter.hashers();