BloomFilter Crash Course
BloomFilters are essentially bit vectors. At a high level BloomFilters work in the following manner:
- Add the element to the filter.
- Hash it a few times, than set the bits to 1 where the index matches the results of the hash.
When testing if an element is in the set, you follow the same hashing procedure and check if the bits are set to 1 or 0. This process is how a BloomFilter can guarantee an element does not exist. If the bits aren’t set, it’s simply impossible for the element to be in the set. However, a positive answer means the element is in the set or a hashing collision occurred. A more detaild description of a BloomFilter can be found here and a good tutorial on BloomFilters here. According to wikipedia, Google uses BloomFilters in BigTable to avoid disk lookups for non-existent items. Another interesting usage is using a BloomFilter to optimize a sql querry.
Using the Guava BloomFilter
A Guava BloomFilter is created by calling the static method create on the BloomFilter class,
passing in a Funnel object and an int representing the expected number of insertions. A Funnel, also new in Guava 11, is an object that can send data into a Sink. The following example is the default implementation and has a percentage of false positives of 3%. Guava provides a Funnels class containing two static methods providing implementations of the Funnel interface for inserting a CharSequence or byte Array into a filter.
//Creating the BloomFilter BloomFilter bloomFilter = BloomFilter.create(Funnels.byteArrayFunnel(), 1000); //Putting elements into the filter //A BigInteger representing a key of some sort bloomFilter.put(bigInteger.toByteArray()); //Testing for element in set boolean mayBeContained = bloomFilter.mayContain(bitIntegerII.toByteArray());
It’s critical to estimate the number of expected insertions correctly. As insertions into the filter approach or exceeds the expected number, the BloomFilter begins to fill up and as a result will generate more false positives to the point of being useless. There is another version of the BloomFilter.create method taking an additional parameter, a double representing the desired level of false hit probability (must be greater than 0 and less than one). The level of false hit probability affects the number of hashes for storing or searching for elements. The lower the desired percentage, the higher number of hashes performed.
A BloomFilter is a useful item for a developer to have in his/her toolbox. The Guava project now makes it very simple to begin using a BloomFilter when the need arises. I hope you enjoyed this post. Helpful comments and suggestions are welcomed.
- Unit Test Demo of Guava BloomFilter.
- BloomFilter class
- All You Want to Know about BloomFilters.
- BloomFilter Tutorial.
- BloomFilter on Wikipedia.