Bloom Filter Explained | Backend Study Lab

Quick answer

A Bloom filter is a space-efficient probabilistic data structure for testing set membership. It stores a bit array and uses multiple hash-derived positions per item. In the standard insert-only model:

“definitely not present” is reliable;
“possibly present” may be a false positive;
inserted items do not produce false negatives.

Bloom filters help avoid expensive negative lookups, but they cannot prove authorization, uniqueness, or existence. Capacity and target false-positive probability must be chosen before sizing the bit array and hash count.

How it works

Start with m zero bits and k hash positions.

To insert an item:

derive k positions from the item;
set every corresponding bit to one.

To query an item:

derive the same positions;
if any bit is zero, the item was definitely not inserted;
if all bits are one, the item may have been inserted.

Example with a 12-bit array and three positions:

add "cat" -> positions 1,4,9 -> 010010000100
add "dog" -> positions 3,4,8 -> 010110001100

query "owl" -> positions 1,6,9
bit 6 is zero -> definitely absent

Another absent item might map only to bits set by cat and dog, producing a false positive.

Why false positives happen

Bits do not record which item set them. As the filter fills, unrelated items increasingly share positions. A query can find all its positions set by a combination of other insertions.

This is a deliberate space trade-off. The filter does not store original keys and cannot return matching items. It answers only “definitely not” or “possibly.”

The false-positive probability after inserting approximately n items is:

p ≈ (1 - e^(-kn/m))^k

where:

m is bit count;
n is inserted-item count;
k is hash count.

The formula assumes sufficiently uniform, independent-looking hash positions. Real implementation quality and workload distribution matter.

Why the standard model has no false negatives

Insertion sets every queried position for an item, and standard Bloom filters never clear bits. Therefore a later query of the same bytes finds all those positions set.

The guarantee has assumptions. False negatives can appear if:

bits are cleared to delete an item;
insertion and query serialize the value differently;
hash seeds or algorithms change;
state is partially lost or corrupted;
concurrent updates are not safely published;
a sharded filter routes insertion and query differently;
the filter is rebuilt from incomplete source data.

Say “no false negatives under the standard insert-only model with stable hashing,” not “false negatives are impossible under every implementation.”

Capacity planning

Given expected capacity n and target probability p, choose:

m = -n ln(p) / (ln 2)^2
k = (m/n) ln 2

Round m up and k to a positive integer. For one million items and p = 0.01, the filter needs about 9.6 million bits—roughly 1.2 MB—and around seven hash positions per item.

This is much smaller than storing one million full keys, but it is not free. Every query computes k positions. A tighter probability uses more bits and possibly more hashing.

Capacity is a correctness-of-cost parameter. If actual insertions greatly exceed n, the false-positive rate rises. Track insert count or set-bit density and rebuild or scale before saturation.

Java sizing helper

record BloomShape(int bitCount, int hashCount) {
    static BloomShape forTarget(long capacity, double probability) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("capacity must be positive");
        }
        if (!(probability > 0.0 && probability < 1.0)) {
            throw new IllegalArgumentException(
                "probability must be between 0 and 1"
            );
        }

        double bits = -capacity * Math.log(probability)
            / (Math.log(2.0) * Math.log(2.0));
        if (bits > Integer.MAX_VALUE) {
            throw new IllegalArgumentException("filter is too large");
        }
        int bitCount = Math.max(1, (int) Math.ceil(bits));
        int hashCount = Math.max(
            1,
            (int) Math.round((double) bitCount / capacity * Math.log(2.0))
        );
        return new BloomShape(bitCount, hashCount);
    }
}

Java BitSet indexes with int, so this example rejects shapes beyond its chosen single-instance limit. Large production filters may partition storage or use an implementation designed for off-heap/distributed state.

A bounded Java BitSet example

Cryptographic hashing is not always required, but positions should be stable and well distributed. This educational implementation derives two 64-bit values from SHA-256 and uses double hashing:

import java.nio.ByteBuffer;
import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.BitSet;

final class StringBloomFilter {
    private final BitSet bits;
    private final int bitCount;
    private final int hashCount;

    StringBloomFilter(long capacity, double probability) {
        BloomShape shape = BloomShape.forTarget(capacity, probability);
        this.bitCount = shape.bitCount();
        this.hashCount = shape.hashCount();
        this.bits = new BitSet(bitCount);
    }

    void add(String value) {
        requireValue(value);
        long[] hashes = hashPair(value);
        for (int i = 0; i < hashCount; i++) {
            bits.set(position(hashes[0], hashes[1], i));
        }
    }

    boolean mightContain(String value) {
        requireValue(value);
        long[] hashes = hashPair(value);
        for (int i = 0; i < hashCount; i++) {
            if (!bits.get(position(hashes[0], hashes[1], i))) {
                return false;
            }
        }
        return true;
    }

    private int position(long first, long second, int index) {
        long combined = first + index * second;
        return (int) Math.floorMod(combined, bitCount);
    }

    private static long[] hashPair(String value) {
        try {
            byte[] digest = MessageDigest.getInstance("SHA-256")
                .digest(value.getBytes(StandardCharsets.UTF_8));
            ByteBuffer buffer = ByteBuffer.wrap(digest);
            return new long[] {buffer.getLong(), buffer.getLong()};
        } catch (NoSuchAlgorithmException impossible) {
            throw new IllegalStateException("SHA-256 unavailable", impossible);
        }
    }

    private static void requireValue(String value) {
        if (value == null) {
            throw new IllegalArgumentException("value must not be null");
        }
    }
}

Production implementations should specify serialization, version, hash algorithm, seeds, concurrency, persistence, and rebuild procedures. Reuse a tested library when possible.

Double hashing

Computing k unrelated cryptographic digests is expensive. Double hashing derives positions from two base hashes:

position(i) = h1 + i*h2 mod m

This gives multiple deterministic positions without rerunning a full digest for each. The exact statistical properties depend on the hash sources and modulus. Monitor real false-positive behavior rather than treating the formula as a substitute for testing.

Backend use cases

Avoiding database misses

A service can check a filter containing known entity IDs:

filter says definitely absent -> return not found without database query
filter says possibly present  -> query authoritative database

False positives only cause an unnecessary database query. The database remains the source of truth.

Cache penetration protection

Attackers or buggy clients may request many nonexistent keys, bypassing a cache and hitting storage. A filter can reject definitely absent keys before the database. Updates must keep the filter current enough to avoid implementation-caused false negatives.

Storage systems

Sorted-string tables and similar storage layers use filters to avoid reading files that definitely cannot contain a key. A false positive causes extra I/O, not an incorrect result.

Duplicate prechecks

A filter can identify a request as “worth checking for a duplicate,” but it cannot enforce uniqueness. A false positive would reject a valid new value if used as final authority. Follow with a unique database constraint or exact set lookup.

What Bloom filters must not decide

Do not use a Bloom filter as the final decision for:

authorization or access control;
whether a payment was processed;
username or idempotency-key uniqueness;
legal deletion confirmation;
inventory availability;
existence of security credentials.

A “possibly present” response is uncertain. Even “definitely absent” relies on filter completeness and version alignment, so high-stakes systems need a failure policy when the filter is unavailable or stale.

Deletion problem

Clearing a bit for one item may erase evidence shared by other items, creating false negatives. A standard Bloom filter therefore does not support arbitrary deletion.

A counting Bloom filter stores small counters instead of bits: increment positions on insert and decrement on delete. It uses more space and can still fail if deletes are unmatched, counters overflow, or concurrency is incorrect.

Other variants include scalable Bloom filters that add layers as capacity grows and stable filters that forget old data for streaming workloads. Each changes guarantees. Name the variant rather than assuming “Bloom filter” semantics.

Rotation and rebuilding

When capacity approaches the design limit, build a new filter from the authoritative dataset. A safe rollout can:

record the source snapshot or version;
build the new filter;
capture concurrent changes;
apply the change stream;
validate sample membership and density;
atomically switch readers;
keep rollback metadata until confidence is established.

Embed a version header with bit count, hash count, serialization, hash algorithm, seed, source checkpoint, and creation time. Without this metadata, persisted bits may be uninterpretable after deployment changes.

Distributed placement

A local filter per service instance offers low latency but requires distribution and refresh. A remote shared filter simplifies consistency but adds a network call that can erase the performance benefit.

Partitioned filters must route a key identically on add and query. During resharding, query old and new partitions or use a version-aware transition. If the filter is only an optimization, fail open to the authoritative store when filter state is missing; failing closed can create false “not found” responses.

Observability

Measure:

inserted-item estimate;
set-bit cardinality or density;
filter version and age;
definitely-absent decisions;
possibly-present decisions;
downstream misses after a positive filter result;
observed false-positive rate;
rebuild duration and errors;
fallback queries when the filter is unavailable.

To measure false positives, sample “possibly present” results and compare with the source of truth. Never log sensitive full keys merely to inspect the filter.

Complexity

For k hash positions:

insert time: O(k);
query time: O(k);
bit storage: O(m);
original-key storage: none.

When sizing keeps k near a small constant, operations are commonly described as constant time relative to the number of stored items. Hashing a long input still costs time proportional to its bytes, and remote/persistent filters add I/O.

Testing the Java filter

@Test
void insertedValuesNeverReturnNegativeInStandardModel() {
    StringBloomFilter filter = new StringBloomFilter(1_000, 0.01);
    List<String> values = List.of("alpha", "beta", "gamma");
    values.forEach(filter::add);
    assertTrue(values.stream().allMatch(filter::mightContain));
}

@Test
void freshFilterRejectsOrdinaryValues() {
    StringBloomFilter filter = new StringBloomFilter(100, 0.01);
    assertFalse(filter.mightContain("not-added"));
}

@Test
void hashingIsDeterministicAcrossInstancesWithSameShape() {
    StringBloomFilter first = new StringBloomFilter(100, 0.01);
    StringBloomFilter second = new StringBloomFilter(100, 0.01);
    first.add("stable");
    second.add("stable");
    assertEquals(
        first.mightContain("stable"),
        second.mightContain("stable")
    );
}

@Test
void rejectsInvalidShape() {
    assertThrows(
        IllegalArgumentException.class,
        () -> new StringBloomFilter(0, 0.01)
    );
}

Do not assert that every uninserted item returns false; false positives are allowed. Statistical tests should use a fixed seed/dataset, tolerance, and enough samples without becoming flaky.

Common mistakes

The first mistake is treating “possibly present” as proof.

The second is deleting by clearing bits.

The third is ignoring capacity growth until the filter is saturated.

The fourth is changing serialization, hash seeds, or filter shape without versioning.

The fifth is using the filter as a uniqueness or authorization authority.

The sixth is advertising no false negatives without stating insert-only and stable-state assumptions.

The seventh is choosing a target probability without measuring the cost of a false positive versus memory and CPU.

Practical checklist

Define the expensive negative lookup to avoid.
Ensure false positives affect performance, not correctness.
Choose expected capacity and target probability.
Calculate and record bit count and hash count.
Version serialization, hashing, seeds, and source checkpoint.
Keep the exact source of truth behind positive results.
Never clear standard-filter bits for deletion.
Plan rebuild and atomic rotation before saturation.
Define fail-open behavior when the filter is missing.
Track density and observed false-positive rate.
Test inserted values, validation, deterministic hashing, and rebuilds.
Protect sensitive keys in metrics and logs.
Continue through the Algorithms learning path and topic clusters.

Frequently asked questions

Can a Bloom filter return false?

Yes. false means definitely absent under the filter’s stated construction and consistency assumptions. true means possibly present.

Why are there no false negatives?

In the standard insert-only model, insertion sets all positions and nothing clears them. Operational bugs, incompatible versions, deletion, or missing updates can violate that assumption.

How many hash functions should I use?

The approximate optimum is (m/n) ln 2. More is not always better: excessive hashes add CPU and eventually increase collisions for a fixed bit array.

Can I list items from a Bloom filter?

No. It does not store recoverable keys. Keep an authoritative dataset elsewhere.

Should I implement one myself?

Use a mature library for production unless you have unusual requirements. A correct lifecycle—versioning, concurrency, persistence, and rebuilding—is harder than the basic bit operations.

Sources and further reading

Burton H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors.
Oracle, BitSet in Java SE 25.
Andrei Broder and Michael Mitzenmacher, Network Applications of Bloom Filters.

Read HashMap Collision Handling Explained for exact hash-table lookup, Caching Strategies Explained for cache penetration and freshness, and Big-O Notation Explained for complexity language. Continue through the Algorithms learning path and topic clusters.