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 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§
source§impl BloomFilter
impl BloomFilter
sourcepub fn with_false_pos(fp: f64) -> BuilderWithFalsePositiveRate<512>
pub fn with_false_pos(fp: f64) -> BuilderWithFalsePositiveRate<512>
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);sourcepub fn with_num_bits(num_bits: usize) -> BuilderWithBits<512>
pub fn with_num_bits(num_bits: usize) -> BuilderWithBits<512>
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);sourcepub fn from_vec(bit_vec: Vec<u64>) -> BuilderWithBits<512>
pub fn from_vec(bit_vec: Vec<u64>) -> BuilderWithBits<512>
Creates a new instance of BuilderWithBits to construct a BloomFilter initialized with bit vector bit_vec.
To fit the bit block size, bit_vec will be padded with 0u64s and the end.
§Panics
Panics if the bit vector, bit_vec, is empty.
§Examples
use fastbloom::BloomFilter;
let bloom = BloomFilter::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
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));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)