-
Notifications
You must be signed in to change notification settings - Fork 0
/
BloomFilter.java
executable file
·58 lines (41 loc) · 1.17 KB
/
BloomFilter.java
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
import java.lang.Math;
class BloomFilter {
private byte[] bits;
private int m;
private int k;
public BloomFilter(int n, double p){
this.m = calculateM(n, p);
bits = new byte[m];
int kx = calculateK(m, n);
// only have defined 4 hash functions, therefore only use 4 even if more required
this.k = kx > 4 ? 4 : kx;
}
private int calculateM(int n, double p){
// calculates M
double m = (-n*Math.log(p)) / Math.pow(Math.log(2),2);
return (int)Math.ceil(m);
}
private int calculateK(int m, int n){
// calculates K
double k = (m/n)*Math.log(2);
return (int)Math.ceil(k);
}
public boolean contains(String x){
for (int n = 0 ; n < k; n++){
long h = HashFunctions.hN(n, x);
int index = (int) (h % m);
index = index < 0 ? -index : index;
if ((bits[index] & 1 ) == 0)
return false;
}
return true;
}
public void add(String x){
for (int n = 0 ; n< k; n++){
long h = HashFunctions.hN(n, x);
int index = (int) (h % m);
index = index < 0 ? -index : index;
bits[index] = 1;
}
}
}