1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
use crate::buckets::Buckets;
use crate::{BloomFilter, BuildHashKernels, HashKernels, RemovableBloomFilter};
use std::hash::Hash;
pub struct Filter<BHK: BuildHashKernels> {
buckets: Buckets, hash_kernels: BHK::HK, }
impl<BHK: BuildHashKernels> Filter<BHK> {
pub fn new(items_count: usize, bucket_size: u8, fp_rate: f64, build_hash_kernels: BHK) -> Self {
let buckets = Buckets::with_fp_rate(items_count, fp_rate, bucket_size);
let hash_kernels = build_hash_kernels.with_fp_rate(fp_rate, buckets.len());
Self { buckets, hash_kernels }
}
}
impl<BHK: BuildHashKernels> BloomFilter for Filter<BHK> {
fn insert<T: Hash>(&mut self, item: &T) {
self.hash_kernels.hash_iter(item).for_each(|i| self.buckets.increment(i, 1))
}
fn contains<T: Hash>(&self, item: &T) -> bool {
self.hash_kernels.hash_iter(item).all(|i| self.buckets.get(i) > 0)
}
fn reset(&mut self) {
self.buckets.reset()
}
}
impl<BHK: BuildHashKernels> RemovableBloomFilter for Filter<BHK> {
fn remove<T: Hash>(&mut self, item: &T) {
self.hash_kernels.hash_iter(item).for_each(|i| self.buckets.increment(i, -1))
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::hash::DefaultBuildHashKernels;
use proptest::{collection::size_range, prelude::any, prelude::any_with, proptest, proptest_helper};
use rand::random;
use std::collections::hash_map::RandomState;
fn _contains(items: &[usize]) {
let mut filter = Filter::new(100, 4, 0.03, DefaultBuildHashKernels::new(random(), RandomState::new()));
assert!(items.iter().all(|i| !filter.contains(i)));
items.iter().for_each(|i| filter.insert(i));
assert!(items.iter().all(|i| filter.contains(i)));
}
proptest! {
#[test]
fn contains(ref items in any_with::<Vec<usize>>(size_range(16).lift())) {
_contains(items)
}
}
fn _remove(item: usize) {
let mut filter = Filter::new(100, 4, 0.03, DefaultBuildHashKernels::new(random(), RandomState::new()));
filter.insert(&item);
filter.remove(&item);
assert!(!filter.contains(&item));
}
proptest! {
#[test]
fn remove(items in any::<usize>()) {
_remove(items)
}
}
}