Struct BloomFilter

pub struct BloomFilter<const BLOCK_SIZE_BITS: usize = 512, S = CloneBuildHasher<RandomDefaultHasher>> { /* 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, 256, 128, or 64 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, neither the bloom filter’s underlying memory usage nor number of bits per item change.

Examples

Basic usage:

use b100m_filter::BloomFilter;

let num_blocks = 4; // by default, each block is 512 bits

let filter = BloomFilter::builder(num_blocks).items(["42", "🦀"].iter());
assert!(filter.contains("42"));
assert!(filter.contains("🦀"));

Use any hasher:

use b100m_filter::BloomFilter;
use ahash::RandomState;

let num_blocks = 4; // by default, each block is 512 bits

let filter = BloomFilter::builder(num_blocks)
    .hasher(RandomState::default())
    .items(["42", "🦀"].iter());

Implementations

impl BloomFilter

pub fn builder(num_blocks: usize) -> Builder<512>

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.

Use builder256, builder128, or builder64 for more speed but slightly higher false positive rates.

Examples

use b100m_filter::BloomFilter;

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

pub fn builder512(num_blocks: usize) -> Builder<512>

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.

Use builder256, builder128, or builder64 for more speed but slightly higher false positive rates.

Examples

use b100m_filter::BloomFilter;

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

pub fn builder256(num_blocks: usize) -> Builder<256>

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

Builder<256> is faster but less accurate than Builder<512>.

Examples

use b100m_filter::BloomFilter;

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

pub fn builder128(num_blocks: usize) -> Builder<128>

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

Builder<128> is faster but less accurate than Builder<256>.

Examples

use b100m_filter::BloomFilter;

let bloom = BloomFilter::builder128(16).hashes(8);

pub fn builder64(num_blocks: usize) -> Builder<64>

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

Builder<64> is faster but less accurate than Builder<128>.

Examples

use b100m_filter::BloomFilter;

let bloom = BloomFilter::builder64(16).hashes(8);

impl<const BLOCK_SIZE_BITS: usize, S: BuildHasher> BloomFilter<BLOCK_SIZE_BITS, S>

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));

pub fn num_hashes(&self) -> u64

Returns the effective number of hashes per item. In other words, the number of bits derived per item.

For performance reasons, the number of bits is rounded to down to a power of 2, depending on BLOCK_SIZE_BITS.

Trait Implementations

impl<const BLOCK_SIZE_BITS: usize, S: Clone> Clone for BloomFilter<BLOCK_SIZE_BITS, S>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<const BLOCK_SIZE_BITS: usize, S: Debug> Debug for BloomFilter<BLOCK_SIZE_BITS, S>

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

Formats the value using the given formatter.

impl<T, const BLOCK_SIZE_BITS: usize, S: BuildHasher> Extend<T> for BloomFilter<BLOCK_SIZE_BITS, 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 PartialEq for BloomFilter

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