A Bloom Filter in Java, with Tests

In one line

Implement BloomFilter<T> sized from expected insertions and target FPR, backed by a long array, using MurmurHash3 double hashing, with add and mightContain. Test existing and missing items, duplicates, large inputs, saturation and the measured FPR.

0/4 · 0%

Think of it like this

Building a smoke detector. The circuit is simple, but you test it with real smoke, test the battery warning and test that it doesn't go off when someone makes toast, before trusting it in a house.

Key ideas

01
Constructor takes expectedInsertions and fpp, computes m and k (Phase 1), and allocates long[(m + 63) / 64] (a manual bit array is faster and larger-capable than java.util.BitSet, which is limited to Integer.MAX_VALUE bits).
02
Items become bytes through a funnel/encoder (for example UTF-8 for strings, big-endian for longs), so the same logical item always hashes identically.
03
add sets k bits and can return whether any bit changed (a cheap "probably new" signal); mightContain returns false on the first zero bit.
04
Tests: every inserted item is found (no false negatives, over millions of items); duplicates don't change the bit count; measured FPR on 1M non-members is within ~10–20% of the target; inserting 3× capacity raises FPR as predicted (saturation test); very large m (beyond 2^31 bits) works.
05
Expose expectedFpp() (fill^k) and approximateElementCount() for monitoring.

Code & diagrams

BloomFilter.javajava

public final class BloomFilter<T> {
    private final long[] words;
    private final long numBits;
    private final int numHashFunctions;
    private final Function<T, byte[]> encoder;

    public BloomFilter(long expectedInsertions, double fpp, Function<T, byte[]> encoder) {
        this.numBits = Math.max(64, (long) Math.ceil(-expectedInsertions * Math.log(fpp) / (Math.log(2) * Math.log(2))));
        this.numHashFunctions = Math.max(1, (int) Math.round((double) numBits / expectedInsertions * Math.log(2)));
        this.words = new long[(int) ((numBits + 63) >>> 6)];
        this.encoder = encoder;
    }

    public boolean add(T item) {
        boolean changed = false;
        for (long pos : positions(item)) {
            int w = (int) (pos >>> 6); long mask = 1L << pos;       // shift uses the low 6 bits
            if ((words[w] & mask) == 0) { words[w] |= mask; changed = true; }
        }
        return changed;                                             // false = probably seen before
    }

    public boolean mightContain(T item) {
        for (long pos : positions(item)) {
            if ((words[(int) (pos >>> 6)] & (1L << pos)) == 0) return false;   // definitely absent
        }
        return true;                                                // possibly present
    }

    private long[] positions(T item) {
        byte[] h = Hashing.murmur3_128().hashBytes(encoder.apply(item)).asBytes();
        long h1 = Longs.fromBytes(h[7], h[6], h[5], h[4], h[3], h[2], h[1], h[0]);
        long h2 = Longs.fromBytes(h[15], h[14], h[13], h[12], h[11], h[10], h[9], h[8]);
        long[] out = new long[numHashFunctions];
        long combined = h1;
        for (int i = 0; i < numHashFunctions; i++) { out[i] = (combined & Long.MAX_VALUE) % numBits; combined += h2; }
        return out;
    }

    public double expectedFpp() {
        long ones = 0; for (long w : words) ones += Long.bitCount(w);
        return Math.pow((double) ones / numBits, numHashFunctions);
    }
}

BloomFilterTest.javajava

@Test void noFalseNegatives() {
    var bf = new BloomFilter<String>(1_000_000, 0.01, s -> s.getBytes(UTF_8));
    for (int i = 0; i < 1_000_000; i++) bf.add("member-" + i);
    for (int i = 0; i < 1_000_000; i++) assertTrue(bf.mightContain("member-" + i));
}

@Test void falsePositiveRateNearTarget() {
    var bf = new BloomFilter<String>(1_000_000, 0.01, s -> s.getBytes(UTF_8));
    for (int i = 0; i < 1_000_000; i++) bf.add("member-" + i);
    int fp = 0, trials = 1_000_000;
    for (int i = 0; i < trials; i++) if (bf.mightContain("other-" + i)) fp++;
    assertEquals(0.01, (double) fp / trials, 0.002);            // ~1.0% measured
}

@Test void saturationRaisesFpr() {
    var bf = new BloomFilter<String>(100_000, 0.01, s -> s.getBytes(UTF_8));
    for (int i = 0; i < 300_000; i++) bf.add("member-" + i);    // 3x capacity
    assertTrue(bf.expectedFpp() > 0.35);                          // ~43.6% predicted
}

Interview problem

The problem

Implement BloomFilter<String> for 1M elements at 1%

Build BloomFilter<String> for 1 million elements with a 1% false-positive target. Test existing and non-existing elements, duplicate insertions, large input, saturation and the false-positive rate.

When it breaks

Index computed with Math.abs(hash) % m

What you see

Math.abs(Long.MIN_VALUE) is still negative; one input in 2^64 throws ArrayIndexOutOfBounds or writes nowhere, and some implementations use int overflow that clusters positions.

Fix & prevent

Mask the sign bit (hash & Long.MAX_VALUE) before the modulo, and test with extreme values.

Explain it without notes

Why use a long array instead of java.util.BitSet?

Practice

Implement the class and the three tests, then add a test that a filter serialized and deserialized answers identically.

Trade-offs

↔
A custom implementation gives full control; a library gives years of bug fixes. Write one to learn, use a proven library in production unless you need something special.

Done when you can

I can implement and test a correct Bloom filter with double hashing and monitoring methods.

Command Palette