Chapter 16 · Randomized, Amortized, Streaming
Bloom Filter
A few bits per item answer "have I seen this?" with no false negatives and a small, predictable rate of false positives (FP). Insert, query, catch a false positive in the act, then measure the rate against the formula.
Inserted (click to query):
bit = 1
bit = 0
bit set just now / false positive
probed, already 1
probed, 0 → definitely not
true "maybe" (really inserted)
Query history
No queries yet.
Measured false-positive rate vs the formula
For the current m, k and hash family: insert n random items (n = 0 … 1.5m), and after each step ask 2,000 items that were never inserted. Dots = measured fraction of false "maybe"s; line = (1 − e−kn/m)k.
Which k is best? (formula, at the current n)
How to read this
- The row of boxes is the bit array B[0..m−1]. Inserting an item computes k hash values and turns those k bits on (lines show which bits an item maps to).
- A query checks the same k bits. One 0 is proof the item was never inserted (bits never turn off). If all k are 1, the answer is only "maybe": other items might have switched those bits on. A red result is a false positive.
- After n inserts, a bit is still 0 with probability about e−kn/m, so a non-member passes all k probes with probability about (1 − e−kn/m)k. That's the "predicted FP" counter; "measured FP" is what your own queries of non-members produced.
- The k chart shows the tradeoff: more hash functions check more bits (good) but fill the array faster (bad). The minimum sits at k = (m/n) ln 2, where about half the bits are 1.
Try this
- Press Lesson example (m = 10, k = 2, toy hashes). 12 → bits 2, 7; 37 → bits 7, 2; 41 → bits 1, 4. Query 45 (bit 5 is 0: definitely not), 14 (bit 3 is 0), then 22: bits 2 and 7 are both on, so the filter says "maybe", a false positive.
- Insert a few items and query each one again: every inserted item always gets "maybe". There are no false negatives.
- Switch to double hashing, m = 64, k = 3, and press Insert 5 random twice (n = 10). The formula predicts about 5.2%. Press Measure: the dots should hug the line.
- Keep n = 10, m = 64 and press Set k = (m/n) ln 2 (6.4 × 0.693 ≈ 4.4 → k = 4, about 4.7%). In the k chart, k = 1 gives about 14% and k = 8 about 6.7%: too few hashes check too little, too many fill the array.
- Keep inserting past n = m. The rate climbs toward 100%: a Bloom filter must be sized for the number of items you expect (about 9.6 bits per item for a 1% rate).