bloom_filter.rs

use std::hash::{DefaultHasher, Hash, Hasher};

//T = element type, M = num bits
struct BloomFilter<const M: usize> {
    bit_array: [bool; M],
    num_hashes: usize,
}

impl<T, const M: usize> BloomFilter<M>
where
    T: Hash,
{

    fn new(num_hashes: usize) -> Self {
        BloomFilter::<M> {
            bit_array: [false; M],
            num_hashes: num_hashes,
        }
    }

    fn insert(&mut self, elem: &T) {
        for i in 0..self.num_hashes {
            let mut hasher = DefaultHasher::new();
            elem.hash(&mut hasher);
            hasher.write_usize(i);

            self.bit_array[hasher.finish() as usize % M] = true;
        }
    }

    fn must_contain(&self, elem: &T) -> bool {
        for i in 0..self.num_hashes {
            let mut hasher = DefaultHasher::new();
            elem.hash(&mut hasher);
            hasher.write_usize(i);

            if !self.bit_array[hasher.finish() as usize % M] { return false; }
        }

        true
    }

}