System Design · Sensei Daily Card

Bloom Filters

The structure that can say “definitely not” but never “definitely yes”.
Probabilistic Membership test O(k) insert & query Sub-linear memory
Bloom filter blueprint: bit array, three hash functions, false positive illustration and formulas

Core Concept

A Bloom filter trades certainty for space. Instead of storing the items themselves, it stores a fingerprint of them in a fixed bit array — then answers one question only: is this item in the set?

Its answers are asymmetric, and that asymmetry is the whole design. “No” is always true. “Yes” means probably — there is a tunable chance it is lying. You accept that lie because the filter costs roughly 10 bits per item regardless of whether the item is a 12-byte ID or a 4 KB URL, and it never touches disk.

The mental shift: a Bloom filter is not a container. It is a cheap gatekeeper in front of an expensive lookup. Every “no” it returns is a disk read, a network call, or a database query you never had to make.

Key Components

01

Bit array of size m

All zeros at birth. The only storage there is. Larger m → fewer collisions → fewer false positives.

02

k independent hash functions

Each maps an item to one position in [0, m). Must be fast and well-distributed — MurmurHash, xxHash, not SHA-256.

03

Insert: set k bits to 1

Hash the item k times, set each bit. Bits are never cleared, so a bit may be shared by many items.

04

Query: test k bits

Any probed bit is 0 → certainly absent. All k bits are 1 → probably present. That is the entire API.

How It Works

  1. Allocate m bits, all zero, and fix k hash functions.
  2. Insert “apple”: compute h₁, h₂, h₃ → positions 2, 6, 11. Set those three bits to 1.
  3. Insert “bread”: positions 6, 9, 14. Bit 6 is already 1 — leave it. Bits are shared; that sharing is the source of both the space saving and the error.
  4. Query “grape”: positions 3, 6, 11. Bit 3 is 0 → if it had ever been inserted, that bit would be 1. Answer: definitely not present. No false negatives, ever.
  5. Query “mango”: positions 2, 9, 14 — all three happen to be 1, set by other items. The filter says “probably present” and it is wrong. This is a false positive, and it is not a bug: it is the price on the receipt.
m = 16, k = 3 — after inserting apple & bread
0
0
1
0
0
0
1
0
0
1
0
1
0
0
1
0
Purple = 1. Orange ring = bit 3, the zero that lets the filter reject “grape” with total confidence.

The Two Equations That Size It

False positive rate
p ≈ ( 1 − e−kn/m )k
Optimal hash count
k = (m / n) · ln 2 ≈ 0.693 · m/n
Bits needed for a target p
m = − ( n · ln p ) / (ln 2)2

Read these as a dial, not as theory. n is how many items you expect; p is the lie rate you can tolerate. Pick p, get m. A 1% false positive rate costs about 9.6 bits per item with k = 7 — roughly 1.2 MB for a million items, versus tens of megabytes to store the keys themselves.

Note what is absent from the formulas: the size of the items. A Bloom filter over a million 2 KB URLs costs the same as one over a million integers.

What It Guarantees — And What It Won't

False negativesImpossible. If it says no, it means no.
False positivesPossible, at a rate you choose in advance.
DeletionNot supported. Clearing a bit could erase another item's evidence. Use a counting Bloom filter (counters instead of bits) or rebuild.
EnumerationNo. You cannot list what's inside — the items were never stored.
ResizingNo. m and k are fixed at creation. Exceed n and p degrades fast. Use a scalable Bloom filter for unknown n.
Union of two filtersYes, bitwise OR — if m and k match.
Beginner mistake: treating “probably present” as an answer instead of a signal. A Bloom filter never replaces the authoritative store — it only lets you skip it. Every positive must still be confirmed by the real lookup. If your code acts on a positive directly, you have shipped a data-corruption bug with a tunable probability.

Real-World Applications

🗃
LSM-tree storage enginesCassandra, RocksDB and LevelDB keep a Bloom filter per SSTable. A read checks the filter first and skips whole files on disk — turning many random reads into one.
🌐
CDN & cache admissionDon't cache an object until it has been requested twice. The filter cheaply remembers “seen once” without storing a key per URL — keeping one-hit-wonders out of the cache.
🔒
Weak-password and breach screeningReject credentials that appear in a leaked set of hundreds of millions, using a few hundred megabytes instead of the full corpus. A false positive just asks the user for a different password.
✉
Deduplication in streamsCrawlers avoid re-fetching URLs; event pipelines drop probable duplicates. A false positive silently discards one item — acceptable only when the workload tolerates it.
₿
Lightweight blockchain clientsBitcoin's BIP-37 let thin clients ask peers for blocks matching a filter of their addresses — the false positives doubling as privacy cover.

Use It When

✓ The expensive path is a miss you'd like to avoid — disk, network, or a cold database.

✓ Most queries are for items that are absent (that's where the win compounds).

✓ A wrong “yes” costs you only one wasted lookup, not a wrong result.

✗ Skip it when you need deletions, exact answers, the ability to list members, or when n is unknown and unbounded.

Checkpoint — answer before you move on

  1. Why can a Bloom filter produce false positives but never false negatives? Trace what a probed 0 bit proves, and what a probed 1 bit fails to prove.
  2. You must support deletion. Explain precisely why clearing the k bits is unsafe, and what a counting Bloom filter changes to make it safe. Think about a bit that two different items both set.
  3. You expect n = 1,000,000 items and can tolerate p = 1%. Roughly how many bits and how many hash functions do you need — and what happens to p if 4 million items arrive instead? Use m = −n·ln p / (ln 2)² and k = (m/n)·ln 2, then re-evaluate p at the new n.