-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathBloomFilter.java
More file actions
83 lines (46 loc) · 1.57 KB
/
Copy pathBloomFilter.java
File metadata and controls
83 lines (46 loc) · 1.57 KB
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
78
79
80
81
82
83
public class BloomFilter {
private interface BloomFilterDataStructure {
public void add(Object item);
public boolean mightContain(Object item);
}
private static class BloomFilter1 implements BloomFilterDataStructure {
boolean[] store;
public BloomFilter1(int size) {
store = new boolean[size];
}
public int[] getHashes(Object item) {
int[] hashes = new int[]{
item.hashCode(),
(item + " ").hashCode(),
(item + "!").hashCode()
};
return hashes;
}
public void add(Object item) {
for (int hash : getHashes(item)) {
int index = hash % store.length;
store[index] = true;
}
}
public boolean mightContain(Object item) {
for (int hash : getHashes(item)) {
int index = hash % store.length;
if (!store[index]) {
return false;
}
}
return true;
}
}
public static void main(String[] args) {
BloomFilterDataStructure[] bloomClasses = new BloomFilterDataStructure[]{new BloomFilter1(10)};
for (BloomFilterDataStructure bloom : bloomClasses) {
bloom.add("A");
bloom.add("B");
bloom.add("C");
System.out.println(bloom.mightContain("A"));
System.out.println(bloom.mightContain("Z"));
System.out.println("------");
}
}
}