BloomFilter.rs

use std::hash::{Hash, Hasher, BuildHasher};
use std::collections::hash_map::RandomState;
use std::default::Default;
use std::marker::PhantomData;

struct BloomFilter<K: Hash + Eq, H = RandomState> {
    bits: Vec<bool>,
    hashes: u8,
    hasher: H,
    marker: PhantomData<K>
}

#[inline]
fn nth_hash(n: u8, hash: u64, f_size: usize) -> usize {
    let a = (hash >> 32) as u32;
    let b = (hash & 0xFFFFFFFF) as u32;
    let pb = b.wrapping_mul(n as u32);
    return a.wrapping_add(pb) as usize % f_size;
}

impl <K: Hash+Eq> BloomFilter<K, RandomState> {
    pub fn new(size: usize, hashes: u8) -> BloomFilter<K, RandomState> {
        BloomFilter::with_hasher(size, hashes, Default::default())
    }
}

impl <K: Hash+Eq, H: BuildHasher> BloomFilter<K, H> {
    pub fn with_hasher(size: usize, hashes: u8, hasher: H) -> BloomFilter<K, H> {
        let bits = vec![false; size];
        BloomFilter {
            bits: bits,
            hasher: hasher,
            hashes: hashes,
            marker: PhantomData,
        }
    }

    pub fn add(&mut self, key: K) {
        for i in 0..self.hashes {
            let mut s = self.hasher.build_hasher();
            key.hash(&mut s);
            let hash = s.finish();
            let cap = self.bits.capacity();
            self.bits[nth_hash(i, hash, cap)] = true;
        }
    }

    pub fn maybe_contains(&self, key: K) -> bool {
        for i in 0..self.hashes {
            let mut s = self.hasher.build_hasher();
            key.hash(&mut s);
            let hash = s.finish();
            let cap = self.bits.capacity();
            if !self.bits[nth_hash(i, hash, cap)] {
                return false;
            }
        }
        true
    }
}

#[cfg(test)]
mod tests {
    use super::BloomFilter;

    #[test]
    fn it_works() {
        let mut b = BloomFilter::new(8, 4);
        assert!(b.maybe_contains("hi") == false, "Empty filter does not contain value!");
        b.add("hi");
        assert!(b.maybe_contains("hi") == true, "Filter contains added value!");
    }
}