Skip to main content

data_structures_lib/
probabilistic.rs

1use std::collections::hash_map::DefaultHasher;
2use std::hash::{Hash, Hasher};
3
4use crate::Error;
5
6/// A Bloom filter for membership queries.
7#[derive(Debug)]
8pub struct BloomFilter {
9    size: usize,
10    hash_count: usize,
11    bits: Vec<u8>,
12    items_added: usize,
13}
14
15impl BloomFilter {
16    /// Creates a new BloomFilter.
17    pub fn new(expected_items: usize, false_positive_rate: f64) -> Result<Self, Error> {
18        if expected_items == 0 {
19            return Err(Error::InvalidArgument);
20        }
21        if false_positive_rate <= 0.0 || false_positive_rate >= 1.0 {
22            return Err(Error::InvalidArgument);
23        }
24        let m = (-(expected_items as f64) * false_positive_rate.ln() / (2.0_f64.ln().powi(2))).ceil()
25            as usize;
26        let k = ((m as f64 / expected_items as f64) * 2.0_f64.ln()).round() as usize;
27        let k = k.max(1);
28        Ok(Self {
29            size: m,
30            hash_count: k,
31            bits: vec![0; (m + 7) / 8],
32            items_added: 0,
33        })
34    }
35
36    /// Adds an item to the filter.
37    pub fn add(&mut self, item: &str) {
38        for i in 0..self.hash_count {
39            let position = self.hash(item, i);
40            self.bits[position / 8] |= 1 << (position % 8);
41        }
42        self.items_added += 1;
43    }
44
45    /// Returns true if the item might be in the filter.
46    pub fn has(&self, item: &str) -> bool {
47        for i in 0..self.hash_count {
48            let position = self.hash(item, i);
49            if self.bits[position / 8] & (1 << (position % 8)) == 0 {
50                return false;
51            }
52        }
53        true
54    }
55
56    /// Returns the number of items added.
57    pub fn count(&self) -> usize {
58        self.items_added
59    }
60
61    /// Returns the estimated false-positive probability.
62    pub fn expected_fpp(&self) -> f64 {
63        let exponent = -(self.hash_count as f64 * self.items_added as f64) / self.size as f64;
64        (1.0 - exponent.exp()).powi(self.hash_count as i32)
65    }
66
67    fn hash(&self, item: &str, seed: usize) -> usize {
68        let mut hasher = DefaultHasher::new();
69        item.hash(&mut hasher);
70        seed.hash(&mut hasher);
71        (hasher.finish() as usize) % self.size
72    }
73}