O'Reilly logo

Getting Started with Google Guava by Bill Bejeck

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

BloomFilter

Bloomfilters are a unique data structure used to indicate whether an element is contained in a set. What makes BloomFilter interesting is that it will indicate whether an element is absolutely not contained or may be contained in a set. This property of never having a false negative makes BloomFilter a great candidate for use as a guard condition to help prevent performing unnecessary or expensive operations, such as disk retrievals.

BloomFilter in a nutshell

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

  1. Add an element to the filter.
  2. Hash it a few times and then set the bits to 1, where the index matches the results of the hash.

When testing whether an element is in the set, you follow ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required