Bill Bejeck is a software developer and enjoys the challenges that software development brings. Bill also loves exploring new languages, technologies and learning and educating by blogging. Bill is a DZone MVB and is not an employee of DZone and has posted 29 posts at DZone. You can read more from them at their website. View Full User Profile

Using Guava BloomFilter for Guard Conditions

03.23.2012
| 5720 views |
  • submit to reddit
When the Guava project released version 11.0, one of the new additions was the BloomFilter class. A BloomFilter is a unique data-structure used to indicate if an element is contained in a set. What makes a BloomFilter interesting is it will indicate if an element is absolutely not contained, or may be contained in a set. This property of never having a false negative makes the BloomFilter a great candidate for use as a guard condition to help prevent performing unnecessary and expensive operations. While BloomFilters have received good exposure lately, using one meant rolling your own, or doing a Google search for code. The trouble with rolling your own BloomFilter is getting the correct hash function to make the filter effective. Considering Guava uses the Murmur Hash for its’ implementation, we now have the usefulness of an effective BloomFilter just a library away. BloomFilter Crash Course

BloomFilters are essentially bit vectors. At a high level BloomFilters work in the following manner:

  1. Add the element to the filter.
  2. 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());
Considerations

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.

Conclusion

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.

References

 

Published at DZone with permission of Bill Bejeck, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)