Bloom filters: reject absent keys without claiming exact membership

Last updated: 5 Oct 20269 min read

tutorial

A Bloom filter maps each inserted key through several hash functions into a fixed bit array. A lookup returning a zero at any required bit proves the key was not inserted into that filter. A lookup finding all bits set means only that the key may have been inserted. With no deletions and correct hashing, ordinary insertion does not create false negatives; collisions can create false positives. As more keys arrive, the false-positive rate rises unless capacity was planned or the filter is rebuilt. The filter is an advisory precheck, not the authoritative record store.

Operational case

A warehouse keeps an authoritative shipment index and uses a small filter to avoid costly index reads for IDs definitely absent. IDs S-47 and S-61 are inserted. A lookup for S-47 returns possible and must still query the index. A lookup for a key whose required bit is zero can skip the index. The filter must be populated from the same accepted-write stream as the index; if a shipment reaches the index but its bit update is missed, the no-false-negative promise no longer holds for the system. Deleting a shipment cannot simply clear its bits because other IDs may share them.

Working Python program

from hashlib import sha256

bit_count = 128
filter_bits = 0

def positions(shipment_id):
    for salt in ("route-a", "route-b", "route-c"):
        digest = sha256(f"{salt}:{shipment_id}".encode()).digest()
        yield int.from_bytes(digest[:8], "big") % bit_count

def record(shipment_id):
    global filter_bits
    for position in positions(shipment_id):
        filter_bits |= 1 << position

def possibly_recorded(shipment_id):
    return all(filter_bits & (1 << position) for position in positions(shipment_id))

record("S-47")
record("S-61")
print(possibly_recorded("S-47"), possibly_recorded("S-52"))

Output

True False

Time, space, and tradeoff

With k hash positions, insertion and lookup each take O(k) hash work and the bit array uses O(m) bits for m positions. This Python integer is a teaching representation; its allocation is implementation-specific and digest computation dominates the tiny trace. A deployed filter needs capacity and acceptable false-positive targets, a stable hash scheme across rebuilds, and an atomic ordering between authoritative writes and filter updates. A false positive wastes a lookup. A false negative caused by an out-of-sync system can hide an existing record, so correctness depends on the integration path as well as the data structure.

Common Mistakes

Do not treat a positive filter response as proof that a record exists.
Do not clear shared bits on ordinary deletion.
Do not promise no false negatives after a missed filter update.

Connected lessons

Apply it: Project: design a versioned warehouse index and Advanced structure contracts.

Count-min sketches: bounded-memory event estimates handles a related query contract.

HyperLogLog: estimate unique IDs with fixed registers adds a bounded stream contract.

Counting Bloom filters: delete only a known insertion extends the membership design choices.

Scalable Bloom filters: grow without discarding old members extends the membership design choices.

Blocked Bloom filters: localize probes and watch skew extends the membership design choices.

Static XOR filters: peel a fingerprint membership index adds a distinct structure contract to compare.

data structures

range-query-structures