Struct fastbloom::BloomFilter
source · pub struct BloomFilter<const BLOCK_SIZE_BITS: usize = 512, S = DefaultHasher> { /* private fields */ }Expand description
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 are set at positions based on the item’s hash in one of the underlying bit vector’s block.
To check membership, a number of bits are checked at positions based on the item’s hash in one of the underlying bit vector’s block.
Once constructed, neither the bloom filter’s underlying memory usage nor number of bits per item change.
§Examples
Basic usage:
use fastbloom::BloomFilter;
let num_bits = 1024;
let mut filter = BloomFilter::builder(num_bits).expected_items(2);
filter.insert("42");
filter.insert("🦀");Instantiate from a collection of items:
use fastbloom::BloomFilter;
let num_bits = 1024;
let filter = BloomFilter::builder(num_bits).items(["42", "🦀"]);
assert!(filter.contains("42"));
assert!(filter.contains("🦀"));Use any hasher:
use fastbloom::BloomFilter;
use ahash::RandomState;
let num_bits = 1024;
let filter = BloomFilter::builder(num_bits)
.hasher(RandomState::default())
.items(["42", "🦀"]);Implementations§
source§impl BloomFilter
impl BloomFilter
sourcepub fn builder(num_bits: usize) -> Builder<512>
pub fn builder(num_bits: usize) -> Builder<512>
Creates a new instance of Builder to construct a BloomFilter
with num_bits number of bits for tracking item membership.
The BloomFilter built from the returned builder will have a block size of 512 bits.
Use either
BloomFilter::<256>::builder_from_bitsBloomFilter::<128>::builder_from_bitsBloomFilter::<64>::builder_from_bits
for more speed but slightly higher false positive rates.
§Examples
use fastbloom::BloomFilter;
let bloom = BloomFilter::builder(1024).hashes(4);source§impl BloomFilter<64, DefaultHasher>
impl BloomFilter<64, DefaultHasher>
sourcepub fn builder_from_bits(num_bits: usize) -> Builder<64>
pub fn builder_from_bits(num_bits: usize) -> Builder<64>
Creates a new instance of Builder to construct a BloomFilter
with num_bits number of bits for tracking item membership.
The BloomFilter built from the returned builder will have a block size of 64 bits.
BloomFilter<64> is faster but less accurate than BloomFilter<128>
§Examples
use fastbloom::BloomFilter;
let bloom = BloomFilter::<64>::builder_from_bits(1024).hashes(4);sourcepub fn builder_from_vec(bit_vec: Vec<u64>) -> Builder<64>
pub fn builder_from_vec(bit_vec: Vec<u64>) -> Builder<64>
Creates a new instance of Builder to construct a BloomFilter initialized with bit vector bit_vec.
The BloomFilter built from the returned builder will have a block size of 64 bits.
§Examples
use fastbloom::BloomFilter;
let bloom = BloomFilter::<64>::builder_from_vec(vec![0x517cc1b727220a95]).hashes(4);source§impl BloomFilter<128, DefaultHasher>
impl BloomFilter<128, DefaultHasher>
sourcepub fn builder_from_bits(num_bits: usize) -> Builder<128>
pub fn builder_from_bits(num_bits: usize) -> Builder<128>
Creates a new instance of Builder to construct a BloomFilter
with num_bits number of bits for tracking item membership.
The BloomFilter built from the returned builder will have a block size of 128 bits.
BloomFilter<128> is faster but less accurate than BloomFilter<256>
§Examples
use fastbloom::BloomFilter;
let bloom = BloomFilter::<128>::builder_from_bits(1024).hashes(4);sourcepub fn builder_from_vec(bit_vec: Vec<u64>) -> Builder<128>
pub fn builder_from_vec(bit_vec: Vec<u64>) -> Builder<128>
Creates a new instance of Builder to construct a BloomFilter initialized with bit vector bit_vec.
The BloomFilter built from the returned builder will have a block size of 128 bits.
To fit a 128 bit block size, bit_vec will be padded with 0u64 to have a length multiple of 2.
§Examples
use fastbloom::BloomFilter;
let bloom = BloomFilter::<128>::builder_from_vec(vec![0x517cc1b727220a95; 2]).hashes(4);source§impl BloomFilter<256, DefaultHasher>
impl BloomFilter<256, DefaultHasher>
sourcepub fn builder_from_bits(num_bits: usize) -> Builder<256>
pub fn builder_from_bits(num_bits: usize) -> Builder<256>
Creates a new instance of Builder to construct a BloomFilter
with num_bits number of bits for tracking item membership.
The BloomFilter built from the returned builder will have a block size of 256 bits.
BloomFilter<256> is faster but less accurate than BloomFilter<512>
§Examples
use fastbloom::BloomFilter;
let bloom = BloomFilter::<256>::builder_from_bits(1024).hashes(4);sourcepub fn builder_from_vec(bit_vec: Vec<u64>) -> Builder<256>
pub fn builder_from_vec(bit_vec: Vec<u64>) -> Builder<256>
Creates a new instance of Builder to construct a BloomFilter initialized with bit vector bit_vec.
The BloomFilter built from the returned builder will have a block size of 256 bits.
To fit a 256 bit block size, bit_vec will be padded with 0u64 to have a length multiple of 4.
§Examples
use fastbloom::BloomFilter;
let bloom = BloomFilter::<256>::builder_from_vec(vec![0x517cc1b727220a95; 4]).hashes(4);source§impl BloomFilter<512, DefaultHasher>
impl BloomFilter<512, DefaultHasher>
sourcepub fn builder_from_bits(num_bits: usize) -> Builder<512>
pub fn builder_from_bits(num_bits: usize) -> Builder<512>
Creates a new instance of Builder to construct a BloomFilter
with num_bits number of bits for tracking item membership.
The returned BloomFilter has a block size of 512 bits.
Use either
BloomFilter::<256>::builder_from_bitsBloomFilter::<128>::builder_from_bitsBloomFilter::<64>::builder_from_bits
for more speed but slightly higher false positive rates.
§Examples
use fastbloom::BloomFilter;
let bloom = BloomFilter::<512>::builder_from_bits(1024).hashes(4);sourcepub fn builder_from_vec(bit_vec: Vec<u64>) -> Builder<512>
pub fn builder_from_vec(bit_vec: Vec<u64>) -> Builder<512>
Creates a new instance of Builder to construct a BloomFilter initialized with bit vector bit_vec.
The BloomFilter built from the returned builder will have a block size of 512 bits.
To fit a 512 bit block size, bit_vec will be padded with 0u64 to have a length multiple of 8.
§Examples
use fastbloom::BloomFilter;
let bloom = BloomFilter::<256>::builder_from_vec(vec![0x517cc1b727220a95; 8]).hashes(4);source§impl<const BLOCK_SIZE_BITS: usize, S: BuildHasher> BloomFilter<BLOCK_SIZE_BITS, S>
impl<const BLOCK_SIZE_BITS: usize, S: BuildHasher> BloomFilter<BLOCK_SIZE_BITS, S>
sourcepub fn insert(&mut self, val: &(impl Hash + ?Sized)) -> bool
pub fn insert(&mut self, val: &(impl Hash + ?Sized)) -> bool
Adds a value to the bloom filter. Returns true if the item may have already been a member.
§Examples
use fastbloom::BloomFilter;
let mut bloom = BloomFilter::builder(1024).hashes(4);
bloom.insert(&2);
assert!(bloom.contains(&2));sourcepub fn contains(&self, val: &(impl Hash + ?Sized)) -> bool
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 fastbloom::BloomFilter;
let bloom = BloomFilter::builder(1024).items([1, 2, 3]);
assert!(bloom.contains(&1));sourcepub fn num_hashes(&self) -> u32
pub fn num_hashes(&self) -> u32
Returns the number of hashes per item.
sourcepub fn num_bits(&self) -> usize
pub fn num_bits(&self) -> usize
Returns the total number of in-memory bits supporting the bloom filter.
sourcepub fn num_blocks(&self) -> usize
pub fn num_blocks(&self) -> usize
Returns the total number of in-memory blocks supporting the bloom filter.
Each block is BLOCK_SIZE_BITS bits.
Trait Implementations§
source§impl<const BLOCK_SIZE_BITS: usize, S: Clone> Clone for BloomFilter<BLOCK_SIZE_BITS, S>
impl<const BLOCK_SIZE_BITS: usize, S: Clone> Clone for BloomFilter<BLOCK_SIZE_BITS, S>
source§fn clone(&self) -> BloomFilter<BLOCK_SIZE_BITS, S>
fn clone(&self) -> BloomFilter<BLOCK_SIZE_BITS, S>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source. Read moresource§impl<T, const BLOCK_SIZE_BITS: usize, S: BuildHasher> Extend<T> for BloomFilter<BLOCK_SIZE_BITS, S>where
T: Hash,
impl<T, const BLOCK_SIZE_BITS: usize, S: BuildHasher> Extend<T> for BloomFilter<BLOCK_SIZE_BITS, S>where
T: Hash,
source§fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)
source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one)source§fn extend_reserve(&mut self, additional: usize)
fn extend_reserve(&mut self, additional: usize)
extend_one)