-
Notifications
You must be signed in to change notification settings - Fork 9
/
README
86 lines (67 loc) · 2.71 KB
/
README
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
Bloom Filter
This implementation of Bloom Filter is written in java, and uses a murmur hash. The class
is a java generic class that requires a ToBytes object for converting your keys into byte
arrays. However if you already have byte array keys that you wish to use them with the bloom
filter. There are methods that except and test byte arrays with offsets and lengths so
that you can reuse your byte array buffers.
Thread Safety
By default this bloom filter is thread safe through the use of AtomicLongArray.
However if your implementation does not require thread safety you may relax this feature in
the constructor. Note: In testing I haven't seen any performance difference with using the
AtomicLongArray over the standard long array implementation.
Below is a simple example of how to use this class.
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.util.ArrayList;
import java.util.List;
import java.util.UUID;
import com.nearinfinity.bloomfilter.BloomFilter;
import com.nearinfinity.bloomfilter.ToBytes;
public class Readme {
public static void main(String[] args) throws IOException, ClassNotFoundException {
BloomFilter<String> bloomFilter = new BloomFilter<String>(0.001, 100, new ToBytes<String>() {
private static final long serialVersionUID = -2257818636984044019L;
@Override
public byte[] toBytes(String key) {
return key.getBytes();
}
});
List<String> knownValues = new ArrayList<String>();
for (int i = 0; i < 100; i++) {
String key = UUID.randomUUID().toString();
knownValues.add(key);
bloomFilter.add(key);
}
for (String key : knownValues) {
if (!bloomFilter.test(key)) {
throw new RuntimeException("False Negative!");
}
}
ByteArrayOutputStream baos = new ByteArrayOutputStream();
ObjectOutputStream outputStream = new ObjectOutputStream(baos);
outputStream.writeObject(bloomFilter);
outputStream.close();
ObjectInputStream inputStream = new ObjectInputStream(new ByteArrayInputStream(baos.toByteArray()));
BloomFilter<String> newBloomFilter = (BloomFilter<String>) inputStream.readObject();
inputStream.close();
for (String key : knownValues) {
if (!newBloomFilter.test(key)) {
throw new RuntimeException("False Negative!");
}
}
int falsePositive = 0;
int sampleSize = 100000;
for (int i = 0; i < sampleSize; i++) {
if (newBloomFilter.test(UUID.randomUUID().toString())) {
falsePositive++;
}
}
System.out.println("[" +
falsePositive +"] false positives out of [" +
sampleSize + "] while using [" +
newBloomFilter.getMemorySize() + "] bytes of memory");
}
}