How Bloom Filters Enable Lightning‑Fast Membership Checks for Massive Datasets

Preface

A common interview question asks how to efficiently determine whether a given integer exists in a very large data set.

Conventional Implementation

Using a HashSet works for a few hundred entries, but inserting ten million integers quickly triggers an OutOfMemoryError because the entire collection must reside in heap memory.

Bloom Filter

A Bloom Filter solves the membership‑test problem by storing only a compact bit array and using multiple hash functions, thus requiring far less memory while providing fast queries.

Principle

1. Initialise a binary array of length L (all bits = 0). 2. For each element, compute H hash values, map each to an index hash % L, and set the corresponding bits to 1. 3. To query an element, recompute the same H hashes; if any mapped bit is 0 the element is definitely absent, otherwise it is probably present.

"If any bit is 0 the element is definitely not in the set; if all bits are 1 the element may be in the set (false positives are possible)."

Custom Java Implementation

public class BloomFilters {
    private int arraySize;
    private int[] array;

    public BloomFilters(int arraySize) {
        this.arraySize = arraySize;
        array = new int[arraySize];
    }

    public void add(String key) {
        int first = hashcode_1(key);
        int second = hashcode_2(key);
        int third = hashcode_3(key);
        array[first % arraySize] = 1;
        array[second % arraySize] = 1;
        array[third % arraySize] = 1;
    }

    public boolean check(String key) {
        int first = hashcode_1(key);
        int second = hashcode_2(key);
        int third = hashcode_3(key);
        if (array[first % arraySize] == 0) return false;
        if (array[second % arraySize] == 0) return false;
        if (array[third % arraySize] == 0) return false;
        return true;
    }

    private int hashcode_1(String key) { /* simple polynomial hash */ }
    private int hashcode_2(String key) { /* FNV‑1a hash */ }
    private int hashcode_3(String key) { /* custom additive hash */ }
}

The three hashcode_* methods provide independent hash values; the add method sets the three bits, while check returns false as soon as any bit is 0.

Performance Test (Custom Implementation)

@Test
public void bloomFilterTest(){
    long start = System.currentTimeMillis();
    BloomFilters bf = new BloomFilters(10_000_000);
    for (int i = 0; i < 10_000_000; i++) {
        bf.add(i + "");
    }
    Assert.assertTrue(bf.check("1"));
    Assert.assertTrue(bf.check("2"));
    Assert.assertTrue(bf.check("3"));
    Assert.assertFalse(bf.check("400230340")); // false positive when array too small
    long end = System.currentTimeMillis();
    System.out.println("Execution time: " + (end - start));
}

Inserting ten million integers took about 3 seconds and correctly identified existing values. Reducing the bit array to one million caused a false positive, demonstrating the trade‑off between memory size and false‑positive rate.

Guava Implementation

Google Guava provides a production‑ready Bloom Filter implementation that handles hashing and bit‑array management internally.

BloomFilter<Integer> filter = BloomFilter.create(
        Funnels.integerFunnel(),
        10_000_000,
        0.01);
for (int i = 0; i < 10_000_000; i++) {
    filter.put(i);
}
Assert.assertTrue(filter.mightContain(1));
Assert.assertTrue(filter.mightContain(2));
Assert.assertTrue(filter.mightContain(3));
Assert.assertFalse(filter.mightContain(10_000_000));
long end = System.currentTimeMillis();
System.out.println("Execution time: " + (end - start));

The Guava version also finishes in a few seconds but, unlike the custom version, it does not trigger frequent Full GC pauses; the old generation usage stays low, allowing even larger data sets.

Source Code Analysis (Guava)

Guava computes a 128‑bit Murmur3 hash, splits it into two 64‑bit values, and applies the configured number of hash functions. The bits are stored in a BitArray (a long[]), where set and get perform bitwise operations.

Conclusion

Bloom Filters are widely used in databases, web crawlers, cache‑breakdown protection, and many other scenarios where a fast, memory‑efficient membership test is required. By adjusting the bit‑array size and the number of hash functions, developers can balance false‑positive probability against memory and CPU consumption.