Struct b100m_filter::BloomFilter

pub struct BloomFilter { /* private fields */ }

A space efficient approximate membership set data structure. False positives from contains are possible, but false negatives are not, i.e. contains for all items in the set is guaranteed to return true, while contains for all items not in the set probably return false.

BloomFilter is supported by an underlying bit vector, chunked into 512 bit “blocks”, to track item membership. To insert, a number of bits, based on the item’s hash, are set in the underlying bit vector. To check membership, a number of bits, based on the item’s hash, are checked in the underlying bit vector.

Once constructed, a bloom filter’s underlying memory usage or number of bits per item does not change.

Examples

use b100m_filter::BloomFilter;

let num_blocks = 4; // each block is 64 bytes, 512 bits
let values = vec!["42", "bloom"];

let mut filter = BloomFilter::builder(num_blocks).items(values.iter());
filter.insert("qwerty");
assert!(filter.contains("42"));
assert!(filter.contains("bloom"));
assert!(filter.contains("qwerty"));

Implementations

impl BloomFilter

pub fn builder(num_blocks: usize) -> Builder

Creates a new instance of Builder to construct a BloomFilter with num_blocks number of blocks for tracking item membership. Each block is 512 bits of memory.

Examples

use b100m_filter::{BloomFilter, Builder};

let builder: Builder = BloomFilter::builder(16);
let bloom: BloomFilter = builder.hashes(4);

pub fn num_hashes(&self) -> u64

Returns the number of bits derived per item for the bloom filter. This number is effectivly the number of hashes per item, but all hashes are not actually performed.

The returned value is always a multiple of 4 due to internal optimizations.

pub fn insert(&mut self, val: &(impl Hash + ?Sized))

Adds a value to the bloom filter.

Examples

use b100m_filter::BloomFilter;

let mut bloom = BloomFilter::builder(4).hashes(4);
bloom.insert(&2);
assert!(bloom.contains(&2));

pub fn contains(&self, val: &(impl Hash + ?Sized)) -> bool

Returns false if the bloom filter definitely does not contain a value. Returns true if the bloom filter may contain a value, with a degree of certainty.

Examples

use b100m_filter::BloomFilter;

let bloom = BloomFilter::builder(4).items([1, 2, 3].iter());
assert!(bloom.contains(&1));

Trait Implementations

impl Clone for BloomFilter

fn clone(&self) -> BloomFilter

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for BloomFilter

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

Formats the value using the given formatter.

impl<T> Extend<T> for BloomFilter

where T: Hash,

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 PartialEq for BloomFilter

fn eq(&self, other: &Self) -> bool

This method tests for self and other values to be equal, and is used by ==.

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

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

impl Eq for BloomFilter