Java Coding Problems

128. Bloom filter

The Bloom filter is a fast and memory-efficient data structure capable of providing a probabilistic answer to the question Is value X in the given set?

Commonly, this algorithm is useful when the set is huge and most searching algorithms are facing memory and speed issues.

The speed and memory efficiency of the Bloom filter come from the fact that this data structure relies on an array of bits (for example, java.util.BitSet). Initially, the bits of this array are set to 0 or false.

The array of bits is the first main ingredient of the Bloom filter. The second main ingredient consists of one or more hash functions. Ideally, these are pairwise independent and uniformly distributed hash functions. Also, it is very important ...