Struct BloomFilter 

pub struct BloomFilter { /* private fields */ }

Bloom filter over arbitrary byte keys.

Implementations

impl BloomFilter

pub fn with_size_and_fp_rate(n: usize, fp: f64) -> Self

Construct a filter sized for n expected inserts at a target false positive rate of fp.

fp must be strictly between 0 and 1; values outside that range are clamped. n of zero produces the minimum usable filter (64 bits, 1 hash) so callers do not need to special-case empty corpora.

Examples

use dyntext::bloom::BloomFilter;
let mut bf = BloomFilter::with_size_and_fp_rate(1000, 0.01);
bf.insert(b"hello");
assert!(bf.contains(b"hello"));

pub fn n_bits(&self) -> u64

Total bit count (multiple of 64).

pub fn hash_count(&self) -> u8

Number of hash functions per insert / lookup.

pub fn insert(&mut self, key: &[u8])

Insert key into the filter.

After this call, Self::contains returns true for key. Repeated inserts of the same key are idempotent.

pub fn contains(&self, key: &[u8]) -> bool

Test whether key MAY be present.

Returns false only if key has provably never been inserted (no false negatives). Returns true if every hash bit is set, which can happen either because key was inserted or because the bits were collectively set by other keys (false positive).

pub fn false_positive_rate(&self, n_inserted: usize) -> f64

Theoretical false positive rate after n_inserted distinct insertions.

Formula: (1 - exp(-k * n / m))^k, where k is the hash count and m is the bit count. Returns 0 for an empty filter (no inserts) and approaches 1 for a fully saturated filter.

Trait Implementations

impl Clone for BloomFilter

fn clone(&self) -> BloomFilter

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for BloomFilter

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

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for BloomFilter

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Serialize for BloomFilter

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.