Struct BloomFilter

pub struct BloomFilter<S = DefaultHasher> { /* 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 to track item membership. To insert, a number of bits are set at positions based on the item’s hash in the underlying bit vector. To check membership, a number of bits are checked at positions based on the item’s hash in the underlying bit vector.

Once constructed, neither the Bloom filter’s underlying memory usage nor number of bits per item change.

Examples

Basic usage:

use fastbloom::BloomFilter;

let mut filter = BloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");
filter.insert("🦀");

Instantiate with a target false positive rate:

use fastbloom::BloomFilter;

let filter = BloomFilter::with_false_pos(0.001).items(["42", "🦀"]);
assert!(filter.contains("42"));
assert!(filter.contains("🦀"));

Use any hasher:

use fastbloom::BloomFilter;
use ahash::RandomState;

let filter = BloomFilter::with_num_bits(1024)
    .hasher(RandomState::default())
    .items(["42", "🦀"]);

Implementations

impl BloomFilter

pub fn with_false_pos(fp: f64) -> BuilderWithFalsePositiveRate

Creates a new instance of BuilderWithFalsePositiveRate to construct a BloomFilter with a target false positive rate of fp. The memory size of the underlying bit vector is dependent on the false positive rate and the expected number of items.

Panics

Panics if the false positive rate, fp, is 0.

Examples

use fastbloom::BloomFilter;
let bloom = BloomFilter::with_false_pos(0.001).expected_items(1000);

pub fn with_num_bits(num_bits: usize) -> BuilderWithBits

Creates a new instance of BuilderWithBits to construct a BloomFilter with num_bits number of bits for tracking item membership.

Panics

Panics if the number of bits, num_bits, is 0.

Examples

use fastbloom::BloomFilter;
let bloom = BloomFilter::with_num_bits(1024).hashes(4);

pub fn from_vec(bit_vec: Vec<u64>) -> BuilderWithBits

Creates a new instance of BuilderWithBits to construct a BloomFilter initialized with bit vector bit_vec.

Panics

Panics if the bit vector, bit_vec, is empty.

Examples

use fastbloom::BloomFilter;

let orig = BloomFilter::with_false_pos(0.001).seed(&42).items([1, 2]);
let num_hashes = orig.num_hashes();
let new = BloomFilter::from_vec(orig.as_slice().to_vec()).seed(&42).hashes(num_hashes);

assert!(new.contains(&1));
assert!(new.contains(&2));

impl<S: BuildHasher> BloomFilter<S>

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

Inserts an element into the Bloom filter.

Returns

true if the item may have been previously in the Bloom filter (indicating a potential false positive), false otherwise.

Examples

use fastbloom::BloomFilter;

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

pub fn insert_hash(&mut self, hash: u64) -> bool

Inserts the hash of an element into the Bloom filter. That is the element is pre-hashed and all subsequent hashes are derived from this “source” hash.

Returns

true if the item may have been previously in the Bloom filter (indicating a potential false positive), false otherwise.

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

Checks if an element is possibly in the Bloom filter.

Returns

true if the item is possibly in the Bloom filter, false otherwise.

Examples

use fastbloom::BloomFilter;

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

pub fn contains_hash(&self, source_hash: u64) -> bool

Checks if the hash of an element is possibly in the Bloom filter. That is the element is pre-hashed and all subsequent hashes are derived from this “source” hash.

Returns

true if the item is possibly in the Bloom filter, false otherwise.

pub fn num_hashes(&self) -> u32

Returns the number of hashes per item.

pub fn num_bits(&self) -> usize

Returns the total number of in-memory bits supporting the Bloom filter.

pub fn as_slice(&self) -> &[u64]

Returns a u64 slice of this BloomFilter’s contents.

Examples

use fastbloom::BloomFilter;

let data = vec![0x517cc1b727220a95; 8];
let bloom = BloomFilter::from_vec(data.clone()).hashes(4);
assert_eq!(bloom.as_slice().to_vec(), data);

pub fn clear(&mut self)

Clear all of the bits in the Bloom filter, removing all items.

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

Returns the hash of val using this Bloom filter’s hasher. The resulting value can be used in Self::contains_hash or Self::insert_hash. All subsequent hashes are derived from this source hash. This is useful for pre-computing hash values in order to store them or send them over the network.

Trait Implementations

impl<S: Clone> Clone for BloomFilter<S>

fn clone(&self) -> BloomFilter<S>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<S: Debug> Debug for BloomFilter<S>

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

Formats the value using the given formatter.

impl<T, S: BuildHasher> Extend<T> for BloomFilter<S>

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<S: BuildHasher> PartialEq for BloomFilter<S>

fn eq(&self, other: &Self) -> 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<S: BuildHasher> Eq for BloomFilter<S>