Struct AtomicBloomFilter

pub struct AtomicBloomFilter<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.

Self 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::AtomicBloomFilter;

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

Instantiate with a target false positive rate:

use fastbloom::AtomicBloomFilter;

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

Use any hasher:

use fastbloom::AtomicBloomFilter;
use ahash::RandomState;

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

Implementations

impl AtomicBloomFilter

pub fn with_false_pos(fp: f64) -> AtomicBuilderWithFalsePositiveRate

Creates a new builder instance to construct a Self 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::AtomicBloomFilter;
let filter = AtomicBloomFilter::with_false_pos(0.001).expected_items(1000);

pub fn with_num_bits(num_bits: usize) -> AtomicBuilderWithBits

Creates a builder instance to construct a Self with num_bits number of bits for tracking item membership.

Panics

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

Examples

use fastbloom::AtomicBloomFilter;
let filter = AtomicBloomFilter::with_num_bits(1024).hashes(4);

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

Creates a builder instance to construct a Self initialized with bit vector bit_vec.

Panics

Panics if the bit vector, bit_vec, is empty.

Examples

use fastbloom::AtomicBloomFilter;

let orig = AtomicBloomFilter::with_false_pos(0.001).seed(&42).items([1, 2]);
let num_hashes = orig.num_hashes();
let new = AtomicBloomFilter::from_vec(orig.iter().collect()).seed(&42).hashes(num_hashes);

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

impl<S: BuildHasher> AtomicBloomFilter<S>

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::AtomicBloomFilter;

let bloom = AtomicBloomFilter::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 iter(&self) -> impl Iterator<Item = u64> + '_

Returns an iterator over the raw bit values of this Bloom filter.

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

Returns the underlying slice of this Bloom filter’s bit contents.

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.

impl<S: BuildHasher> AtomicBloomFilter<S>

pub fn insert(&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::AtomicBloomFilter;

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

pub fn insert_hash(&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 insert_all<T: Hash, I: IntoIterator<Item = T>>(&self, iter: I)

Inserts all the items in iter into the self. Immutable version of Self::extend.

pub fn clear(&self)

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

pub fn union(&self, other: &AtomicBloomFilter<S>)

Unions other into self. The hashers of both Bloomfilters must be identical (this is not enforced!).

Panics

Panics if the other Bloomfilter has a different number of bits or hashes than self.

Example

use fastbloom::AtomicBloomFilter;

let bloom = AtomicBloomFilter::with_num_bits(4096).seed(&1).hashes(4);
let other = AtomicBloomFilter::with_num_bits(4096).seed(&1).hashes(4);
bloom.insert_all(0..=1000);
other.insert_all(500..=1500);
bloom.union(&other);

for x in 0..=2000 {
    assert_eq!(bloom.contains(&x), bloom.contains(&x) || other.contains(&x));
}

pub fn intersect(&self, other: &AtomicBloomFilter<S>)

Intersects other onto self. The hashers of both Bloomfilters must be identical (this is not enforced!).

Panics

Panics if the other Bloomfilter has a different number of bits or hashes than self.

Example

use fastbloom::AtomicBloomFilter;

let bloom = AtomicBloomFilter::with_num_bits(4096).seed(&1).hashes(4);
let other = AtomicBloomFilter::with_num_bits(4096).seed(&1).hashes(4);
bloom.insert_all(0..=1000);
other.insert_all(500..=1500);
bloom.intersect(&other);

for x in 0..=2000 {
    assert_eq!(bloom.contains(&x), bloom.contains(&x) && other.contains(&x));
}

Trait Implementations

impl<S: Clone> Clone for AtomicBloomFilter<S>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<S: Debug> Debug for AtomicBloomFilter<S>

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

Formats the value using the given formatter.

impl<T, S: BuildHasher> Extend<T> for AtomicBloomFilter<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 AtomicBloomFilter<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 AtomicBloomFilter<S>