Command Palette

Search for a command to run...

Hectal
Phase 1Beginner2 of 12 in Bloom Filters

The Mathematics

Derive the false-positive formula, compute memory and the optimal number of hashes for any target, predict saturation, and do the interview arithmetic in your head.

Every Bloom filter decision comes down to four numbers: n (items), m (bits), k (hash functions) and p (false-positive rate). If you can move between them fluently, you can size any filter in a design interview in under a minute.

This phase derives the formulas rather than just stating them, then drills the calculations interviewers ask for.

0/4 · 0%
4 topics ~32 min 7 code blocks & diagrams
Start with the first topic
1
1.1

Deriving the False-Positive Probability

After n insertions with k hashes into m bits, a given bit is still 0 with probability (1 − 1/m)^(kn) ≈ e^(−kn/m). A false positive needs all k probed bits to be 1, so p ≈ (1 − e^(−kn/m))^k. Understanding each step lets you reason about any variant.

8 min 2 code practice

2
1.2

Sizing: Memory, Optimal k, and Bits per Element

For a target error p, the filter needs m = −n ln(p) / (ln 2)² bits (about 1.44 × log2(1/p) bits per item) and k = (m/n) ln 2 hash functions. At 1% that's ~9.6 bits and 7 hashes per item; each 10× lower error costs ~4.8 more bits per item.

9 min 2 code practice

3
1.3

Saturation: What Happens Past Capacity

A Bloom filter sized for n items keeps working when you insert more, but its false-positive rate climbs fast: 1.5× capacity turns 1% into ~5.8%, 2× into ~15.7%, 10× into ~99.5%. At that point nearly every lookup says "maybe" and the filter is useless.

8 min 1 diagram 1 code practice

4
1.4

Interview Math Without a Calculator

Memorise a few anchors: ln 2 ≈ 0.693, (ln 2)² ≈ 0.48, 1% needs ~10 bits and 7 hashes per item, 0.1% ~14.4 bits, each 10× costs ~4.8 bits, and 10 bits/item gives just under 1%. With those you can size any filter in your head.

7 min 1 code practice