-
Notifications
You must be signed in to change notification settings - Fork 368
/
BloomFilter.java
105 lines (89 loc) · 3.35 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
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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
import java.util.BitSet;
public class BloomFilter {
private BitSet bitArray;
private int size;
private int hashFunctions;
public BloomFilter(int size, int hashFunctions) {
this.size = size;
this.hashFunctions = hashFunctions;
this.bitArray = new BitSet(size);
}
public void add(Object element) {
for (int i = 0; i < hashFunctions; i++) {
int index = hash(element, i) % size;
bitArray.set(index);
}
}
public boolean query(Object element) {
for (int i = 0; i < hashFunctions; i++) {
int index = hash(element, i) % size;
if (!bitArray.get(index)) {
return false; // Definitely not in the set
}
}
return true; // Probably in the set
}
private int hash(Object element, int seed) {
int hashValue = seed;
byte[] bytes = elementToBytes(element);
for (byte b : bytes) {
hashValue = (hashValue * 65599) ^ (b & 0xFF);
}
return Math.abs(hashValue);
}
private byte[] elementToBytes(Object element) {
if (element instanceof String) {
return ((String) element).getBytes();
} else if (element instanceof Integer) {
return intToBytes((Integer) element);
} else if (element instanceof Float) {
return floatToBytes((Float) element);
} else if (element instanceof Byte) {
return new byte[]{(Byte) element};
} else if (element instanceof Double) {
return doubleToBytes((Double) element);
} else if (element instanceof Long) {
return longToBytes((Long) element);
} else {
throw new IllegalArgumentException("Unsupported element type");
}
}
private byte[] intToBytes(int value) {
return new byte[]{
(byte) (value >>> 24),
(byte) (value >>> 16),
(byte) (value >>> 8),
(byte) value
};
}
private byte[] floatToBytes(float value) {
return intToBytes(Float.floatToIntBits(value));
}
private byte[] doubleToBytes(double value) {
return longToBytes(Double.doubleToLongBits(value));
}
private byte[] longToBytes(long value) {
return new byte[]{
(byte) (value >>> 56),
(byte) (value >>> 48),
(byte) (value >>> 40),
(byte) (value >>> 32),
(byte) (value >>> 24),
(byte) (value >>> 16),
(byte) (value >>> 8),
(byte) value
};
}
public static void main(String[] args) {
BloomFilter filter = new BloomFilter(100, 2);
int intValue = 42;
filter.add(intValue);
String stringValue = "example";
filter.add(stringValue);
// Querying for membership
System.out.println("Querying 42: " + filter.query(intValue)); // Output: true (probably in the set)
System.out.println("Querying 'example': " + filter.query(stringValue)); // Output: true (probably in the set)
System.out.println("Querying 'world': " + filter.query("world")); // Output: false (definitely not in the set)
System.out.println("Querying 'worldd': " + filter.query("worldd")); // Output: false (definitely not in the set -> false positive)
}
}