Bloom Filter

A bit array and k hash functions that answer is this item in the set with a certain no or a probable yes, in a fraction of the memory a real set needs.

Overview

A Bloom filter is a set that can say no with certainty and yes only with high probability. It stores no items, only a bit array of m bits, all 0 at the start. To add an item you hash it k ways and set those k bits to 1. To test an item you hash it the same k ways: if any of the bits is still 0, the item was never added; if all are 1, it was probably added, but other items may have set those bits between them.

Burton Bloom published the idea in 1970 to keep a hyphenation dictionary in memory when the whole dictionary would not fit. That is still the job: stand in front of something expensive (a disk read, a network call, a database query) and answer most of the misses without touching it. The price is a false positive rate you choose when you size the filter, and the fact that a plain filter cannot delete.

No — The item is not in the set, always — Skip the expensive lookup
Yes — The item is probably in the set; wrong with probability about p — Do the lookup; it occasionally finds nothing

A trace on 16 bits

Take m = 16 and k = 3. The positions below are the real ones the implementation further down computes; they come from SHA-256, so they are the same on every machine.

1 — add("cat") — 3, 0, 13 — 1001 0000 0000 0100
2 — add("cow") — 4, 7, 10 — 1001 1001 0010 0100
3 — might_contain("cat") — 3, 0, 13 — unchanged — all 1: yes
4 — might_contain("ant") — 14, 7, 0 — unchanged — bit 14 is 0: no, certain
5 — might_contain("hen") — 13, 10, 7 — unchanged — all 1: yes, a false positive

Step 5 is the whole trade-off. Two items set six bits; a third item that happens to hash onto three of those six looks like a member. With 6 of 16 bits set and 3 probes, the chance of that is roughly (6/16)^3, about 5%.

An implementation that runs

The k positions come from two hashes, not k. Adam Kirsch and Michael Mitzenmacher showed in 2008 that positions of the form h1(x) + i·h2(x) mod m give the same asymptotic false positive rate as k independent hash functions, so every real implementation splits one wide digest into h1 and h2 and combines them.

Both operations do k hash computations and k bit accesses, so they are O(k) and independent of how many items were added. Memory is m bits, full stop.

The math, from Bloom's 1970 paper

Bloom's method 2 is the filter above. He showed that the fraction of bits still 0 after n items is (1 − k/m)^n, which is about e^(−kn/m); that the false positive rate is that fraction subtracted from one and raised to the k; and that the hash area is smallest when half the bits are 1 and half are 0. In today's notation:

False positive rate — p ≈ (1 − e^(−kn/m))^k — n items in m bits with k hashes
Best k — k = (m/n) · ln 2 — Leaves about half the bits set
Bits needed — m = −n · ln p / (ln 2)^2 — For n items at rate p
Bits per item — −ln p / (ln 2)^2, about 1.44 · log2(1/p) — Depends only on p, not on item size

1% — 9.59 — 7
0.1% — 14.38 — 10
0.01% — 19.17 — 14

The code recomputes the table, sizes a filter for a million items, and then measures the rate on a real filter to show the formula holds.

Bloom's worked example was hyphenation: 500,000 words, of which 450,000 follow simple rules and 50,000 need a dictionary on disk. With an allowed error of 1 in 16, the filter in memory sends only the 50,000 hard words plus one sixteenth of the easy ones to disk, and the paper's Table I lists the saving for each error rate. The code checks that table.

What you will be able to do

Explain the two guarantees (never a false negative, sometimes a false positive) and why the structure gives them.
Implement add and might_contain with double hashing in a few lines.
Size a filter from n and p, and say what happens when more than n items arrive.
Add deletion with a counting filter, and say what it costs.
Place a filter in a read path and name systems that do it.

Interview questions

Size a Bloom filter for a million items at 1% false positives, and say what happens if two million arrive.
Why can a Bloom filter not delete, and how does a counting filter fix it?
Where do Bloom filters sit in real systems?
Bloom filter, hash set or cuckoo filter: how do you choose?
Where do the k hash functions come from?