data_structures_lib/
probabilistic.rs1use std::collections::hash_map::DefaultHasher;
2use std::hash::{Hash, Hasher};
3
4use crate::Error;
5
6#[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 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 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 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 pub fn count(&self) -> usize {
58 self.items_added
59 }
60
61 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}