Skip to content
Newer
Older
100644 87 lines (60 sloc) 4.28 KB
9726aab @MagnusS new title
authored
1 java-bloomfilter
2 ================
2f87826 @MagnusS added new README
authored
3 java-bloomfilter is a stand-alone Bloom filter implementation written in Java. It is intended to be easy to include in existing projects without the overhead of additional libraries. The first version was inspired by a blog entry by [Ian Clarke](http://blog.locut.us/2008/01/12/a-decent-stand-alone-java-bloom-filter-implementation/).
4
1e898f1 @MagnusS minor changes
authored
5 The latest version can be downloaded from [GitHub](https://github.com/magnuss/java-bloomfilter).
2f87826 @MagnusS added new README
authored
6
7 Bloom filters
8 -------------
7c65a7b @MagnusS minor changes
authored
9 Bloom filters are used for set membership tests. They are fast and space-efficient at the cost of accuracy. Although there is a certain probability of error, Bloom filters never produce false negatives.
2f87826 @MagnusS added new README
authored
10
11 If you are new to Bloom filters, you can learn more about them in [this tutorial](http://llimllib.github.com/bloomfilter-tutorial/). A more comprehensive overview is available from [Wikipedia](http://en.wikipedia.org/wiki/Bloom_filter).
12
13 Examples
14 --------
15
16 To create an empty Bloom filter, just call the constructor with the required false positive probability and the number of elements you expect to add to the Bloom filter.
17
18 ```java
19 double falsePositiveProbability = 0.1;
20 int expectedNumberOfElements = 100;
21
22 BloomFilter<String> bloomFilter = new BloomFilter<String>(falsePositiveProbability, expectedNumberOfElements);
23 ```
24 The constructor chooses a length and number of hash functions which will provide the given false positive probability (approximately). Note that if you insert more elements than the number of expected elements you specify, the actual false positive probability will rapidly increase.
25
26 There are several other constructors available which provide different levels of control of how the Bloom filter is initialized. You can also specify the Bloom filter parameters directly (bits per element, number of hash functions and number of elements).
27
28 After the Bloom filter has been created, new elements may be added using the add()-method.
29
30 ```java
31 bloomFilter.add("foo");
32 ```
33
34 To check whether an element has been stored in the Bloom filter, use the contains()-method.
35
36 ```java
37 bloomFilter.contains("foo"); // returns true
38 ```
39
40 Keep in mind that the accuracy of this method depends on the false positive probability. It will always return true for elements which have been added to the Bloom filter, but it may also return true for elements which have not been added. The accuracy can be estimated using the expectedFalsePositiveProbability()-method.
41
42 Put together, here is the full example.
43
44 ```java
45 double falsePositiveProbability = 0.1;
46 int expectedSize = 100;
47
48 BloomFilter<String> bloomFilter = new BloomFilter<String>(falsePositiveProbability, expectedSize);
49
50 bloomFilter.add("foo");
51
52 if (bloomFilter.contains("foo")) { // Always returns true
53 System.out.println("BloomFilter contains foo!");
54 System.out.println("Probability of a false positive: " + bloomFilter.expectedFalsePositiveProbability());
55 }
56
57 if (bloomFilter.contains("bar")) { // Should return false, but could return true
58 System.out.println("There was a false positive.");
59 }
60 ```
61
e7469c8 @MagnusS added compile section
authored
62 Compiling
63 ---------
1e898f1 @MagnusS minor changes
authored
64 To compile, run ant from the base directory.
e7469c8 @MagnusS added compile section
authored
65
d99ce9d @MagnusS more minor changes...
authored
66 ant
e7469c8 @MagnusS added compile section
authored
67
68 When ant is done, include dist/java-bloomfilter.jar in your project.
69
1e898f1 @MagnusS minor changes
authored
70 Alternatively, java-bloomfilter could be loaded in Netbeans and compiled using the IDE.
e7469c8 @MagnusS added compile section
authored
71
830e807 @MagnusS Added direct link to BloomFilter.java
authored
72 If you want to avoid adding another library to your project, all the Bloom filter code is in [BloomFilter.java](https://github.com/MagnusS/Java-BloomFilter/blob/master/src/com/skjegstad/utils/BloomFilter.java). You may copy this code directly into your project if you leave the LGPL-comment in place and reference the java-bloomfilter web page.
e7469c8 @MagnusS added compile section
authored
73
2f87826 @MagnusS added new README
authored
74 Changes
75 -------
76 ### 1.0
d99ce9d @MagnusS more minor changes...
authored
77 * Improved the speed of the add() and contains()-methods. The speed increase is around 4-5 times on my computer, but the actual increase may vary from system to system.
2f87826 @MagnusS added new README
authored
78 * Added benchmark code to test future code optimizations.
79 * Fixed a bug in add() where numberOfAddedElements was incorrectly increased twice when adding other elements than byte-arrays. Updated test.
80 * Moved project to Github
f6d71c8 @MagnusS README update
authored
81 * Added javadoc and source jar to build script.
2f87826 @MagnusS added new README
authored
82
83 ### 0.9.3
84 * New constructor for estimating bitSetSize from a given false positive probability.
85 * New constructor for specifying bits per element, elements and hash functions (c, n, k) directly.
86 * Added getExpectedBitsPerElement() and getBitsPerElement()
Something went wrong with that request. Please try again.