Bloom Filter
A space-efficient probabilistic data structure that answers set-membership queries with no false negatives and a tunable false-positive rate, used to skip expensive lookups.
By Ratish Jain · Updated
Definition
A Bloom filter is a probabilistic data structure that tests whether an element is a member of a set. It answers one of two things: "definitely not in the set" or "possibly in the set."
It never produces a false negative (if it says no, the element is truly absent) but it can produce a false positive (it may say "possibly" for something not present). It stores no elements — just a bit array — so it is extremely compact.
Why It Exists
Many systems need to answer "have I seen this key?" before doing expensive work — a disk seek, a network call, a database read. Storing the full set in memory to check is often too large or too costly.
A Bloom filter trades a small, controllable error rate for a huge space saving: a few bits per element instead of the full key. Because it has no false negatives, a "no" answer is trustworthy and lets you skip the expensive lookup entirely.
How It Works
The filter is a bit array of m bits plus k independent hash functions. To add an element, hash it k ways and set those k bits to 1. To query, hash the element the same k ways: if any of those bits is 0, the element is definitely absent; if all are 1, it is possibly present (the bits may have been set by other elements — a false positive).
The false-positive rate is tunable via m and k for a given number of elements n; more bits and optimal k ≈ (m/n)·ln2 lower it. Standard Bloom filters don't support deletion (clearing a bit could break other keys); counting Bloom filters use small counters to allow removal.
What It's Used For
- LSM-tree databases (Cassandra, RocksDB, HBase) skip disk reads for absent keys.
- Cache layers avoid querying the DB for keys known to be missing.
- Web crawlers and dedup pipelines detect already-seen URLs cheaply.
- CDNs and proxies decide whether an object might be cached before a lookup.
- Preventing cache-penetration attacks that flood the DB with missing keys.
Bits & Hashes
Tradeoffs
- Tiny memory footprint — a few bits per element regardless of key size.
- No false negatives, so a negative answer safely skips expensive work.
- Constant-time add and query independent of set size.
- False positives cause occasional unnecessary lookups.
- Cannot enumerate members or retrieve stored values.
- Standard variant can't delete; needs a counting Bloom filter.
- False-positive rate degrades as the filter fills past its sized capacity.
When to Use / Avoid
- Use when
- A cheap 'definitely absent' check can save a costly lookup and you can tolerate rare false positives.
- Avoid when
- You need exact membership, must delete elements often (without counting variant), or must retrieve the stored data.
- Real-world
- Cassandra and RocksDB gate SSTable reads with Bloom filters; Chrome once used one for its malicious-URL check.
Interview Questions
Adding an element only sets bits to 1 and never clears them, so every bit for a stored element stays 1 — a query for it always finds all k bits set (no false negative). A query for an absent element can still find all k bits set if other elements happened to set them, producing a false positive.
Increase the bit array size m relative to the number of elements n, and use the optimal number of hash functions k ≈ (m/n)·ln2. Roughly, ~10 bits per element gives about a 1% false-positive rate. If the set grows unbounded, use a scalable Bloom filter that adds capacity over time.
- →Probabilistic membership: answers 'definitely no' or 'possibly yes'.
- →No false negatives; tunable false-positive rate via m bits and k hashes.
- →Add sets k bits; query fails fast if any of the k bits is 0.
- →Standard filters can't delete — use a counting Bloom filter.
- →Saves expensive disk/DB lookups in LSM stores, caches, and crawlers.
Related
Everything on Archprimer is connected — follow the graph.