Bloom filters

The one-sided guarantee

A bloom filter is a probabilistic set-membership structure. You add elements to it, and later ask “is X in the set?” It answers with one of two verdicts, and the asymmetry between them is the whole point:

• “Definitely not present.” This answer is always correct. A bloom filter never has false negatives — if it says an element was never added, it really wasn’t.
• “Possibly present.” This answer might be wrong. There is a tunable probability of a false positive: the filter says “maybe” for an element that was never added.

So a bloom filter is a fast, cheap, sometimes-wrong-in-the-safe-direction pre-check. It can’t store the elements themselves and can’t enumerate them — it only answers membership, approximately. The payoff is space: it represents a set in a tiny fraction of the memory the actual elements would take, which is why it’s used as a guard in front of an expensive exact lookup.

The mechanism: a bit-array and k hashes

A bloom filter is a bit-array of m bits, all starting at 0, plus k independent hash functions, each mapping an element to one of the m positions.

To add an element: hash it with all k functions to get k positions, and set those k bits to 1.

To query an element: hash it with the same k functions and check those k positions. If any of them is 0, the element was definitely never added → “definitely not present.” If all k are 1, the element is “possibly present” — but those bits might have been set to 1 by other elements that happen to share those positions. That coincidence is the false positive.

m-bit array (m = 16, k = 3 here)

add "alice"  → hashes to bits 2, 7, 13   → set them
add "bob"    → hashes to bits 4, 7, 11   → set them
                                            (bit 7 now shared)

index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
bit:   0 0 1 0 1 0 0 1 0 0 0  1  0  1  0  0

query "carol" → bits 2, 4, 13 → ALL are 1 → "possibly present"
                (but carol was never added — FALSE POSITIVE,
                 her three positions were each set by alice/bob)
query "dave"  → bits 3, 8, 15 → bit 3 is 0 → "definitely NOT present"

This is why there are no false negatives: adding an element only ever sets bits, never clears them, so a previously-added element always finds all its bits at 1. And it’s why false positives exist: as more elements are added, more bits flip to 1, and eventually an unrelated element’s k positions can all already be set.

The false-positive rate: size, count, and k

The false-positive probability is not a fixed property — you tune it. It depends on three numbers: m (bits in the array), n (elements inserted), and k (number of hash functions). The intuition: more bits per element (m/n) means fewer collisions and a lower false-positive rate; too few or too many hash functions both hurt (too few and each element discriminates poorly; too many and you fill the array too fast). For a target false-positive rate there is an optimal k, and the rough engineering rule is that you need on the order of ~10 bits per element for a ~1% false-positive rate — and adding ~5 bits per element cuts the rate by roughly another order of magnitude. The headline is the space win: ~1.2 bytes per element to guard a set, versus storing the full keys.

A hard constraint: you must size the filter for the number of elements you’ll insert. Keep adding past the planned n and the bit-array saturates (too many 1s), the false-positive rate climbs toward 100%, and the filter becomes useless — it says “maybe” to everything. There is no “just resize” for a plain bloom filter; you rebuild a larger one (or use a scalable variant).

Where they earn their keep

Bloom filters appear wherever a “definitely-not-here” answer lets you skip an expensive operation:

• LSM-tree databases (Cassandra, RocksDB, LevelDB, HBase) put a bloom filter on each on-disk table file so a read for a missing key skips the disk seeks for files that certainly don’t contain it — the storage-engine story from the hook.
• Caches use a filter to avoid querying the backing store for keys that were never cached (and to fight cache-penetration attacks that hammer the DB with known-missing keys).
• CDNs and “one-hit-wonder” detection: a CDN can use a filter to avoid caching content requested only once, saving cache space for items likely to be requested again.
• Web crawlers check “have I already seen this URL?” against a filter instead of a giant set, accepting that they’ll occasionally skip a new URL (here a false positive means a missed page — sometimes acceptable, sometimes not).

Together these use-cases share one shape: the filter lives in front of something expensive, and a “definitely absent” verdict skips that expense entirely; the occasional false positive just triggers one wasted lookup. The cuckoo filter is a newer alternative that supports deletion and can be more space-efficient at low false-positive rates, at the cost of a more complex insert that can fail when the structure is too full. Counting and cuckoo are the two variants to reach for when plain-bloom’s no-delete limitation bites.