Archprimer
ConceptIntermediate 7 min read

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.

probabilisticdata-structuresperformancedatabases

By Ratish Jain · Updated

Diagram with 3 components: App, Bloom Filter, Disk / DB. Connections: App → Bloom Filter (1 check); Bloom Filter → Disk / DB (2 maybe); Bloom Filter → App (definitely no).
ServiceCacheDatabase
The filter rejects definite misses cheaply; possible hits fall through to disk.

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

Diagram with 5 components: insert x, query y, k hash fns, bit array, absent. Connections: insert x → k hash fns (1 · hash x); k hash fns → bit array (set k bits); query y → k hash fns (probe); bit array → absent (0 bit = no).
ClientServiceStorageExternal
k hashes set k bits on insert; on query, any 0 bit means definitely absent.

Tradeoffs

Pros
  • 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.
Cons
  • 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

Why does a Bloom filter have false positives but never false negatives?

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.

How do you reduce the false-positive rate?

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.

60-Second Revision
  • →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.