Bloom Filter: Definitely Not, or Probably Yes

Every word sets k bits in a row of m. To look a word up, check its k bits: a single 0 proves it was never inserted, and all 1s only make it likely. Step the words in, then type a word of your own.

Worked example — Bloom Filter: Definitely Not, or Probably Yes

Bits set to 1	20 of 64 (31.3%)
Bits per word	8.00
Best k by the standard estimate	5.55
Standard estimate of the false-positive rate	3.06%
Estimate from the bits actually set	3.05%
Measured over 10,000 strings never inserted	335 of 10,000 (3.35%)
Inserted words answering “definitely not”	0 of 8

These are the values the calculator shows when the page opens. Change any input above to recompute them.

Loading interactive simulation...

Lesson

A Bloom filter answers whether an item belongs to a set, using a row of m bits and k hash functions. Inserting an item sets the k bits its hashes point to. A lookup checks the same k bits: if any is 0 the item is definitely not in the set; if all are 1 it is probably in it. A wrong “probably yes” is a false positive. With n items inserted, the standard estimate of the false-positive rate, an exponential approximation of Bloom's own 1970 formula, is (1 − e^−kn/m)^k, smallest at k = (m/n) ln 2.

What each symbol means

m: the number of bits in the filter
k: the number of hash functions, so the number of bits each word sets and each lookup tests
n: the number of words inserted
X: the number of bits set to 1 once all n words are in

Assumes: The k positions of a word come from two hashes by double hashing: position i is (h₁ + i·h₂) mod m, with h₁ the FNV-1a hash of the word, h₂ a stirred djb2 hash made odd, and m a power of two, so a word's k positions are always different. The standard estimate treats every one of the kn positions as an independent random choice; double hashing and a small m are where it parts company with a real filter. The false-positive rate is measured over the 10,000 strings 0 to 9999 and is exact for those strings, not for every possible word.

Sixteen hash functions do worse than one 🖖

Press Five hash functions and read the table under the results. At 128 bits and 16 words, one hash function lets 12.82% of the never-inserted strings through; five let 2.50%, the lowest in the column; sixteen let 32.01%, worse than one. Each extra function makes a lookup test one more bit, which helps, and makes every insert set one more bit, which hurts. From one to five the rate falls at every step, and from there it climbs, with one small dip at fifteen. Bloom saw the turning point in 1970: it comes when about half the bits are 1. At five hash functions 60 of these 128 are, and the standard estimate puts the best k at (m/n) ln 2 = 8 × 0.693 = 5.55.

Counting this filter's 1s beats the standard estimate 🖖

Press Sixteen hash functions. The standard estimate says 9.76%; the filter lets through 32.01%. The estimate assumes 128 × (1 − e⁻²) = 110.7 bits are set, and these sixteen words happen to set 119. Raise the fraction actually set to the sixteenth power, (119/128)¹⁶, and you get 31.15%, close to what was measured. With k this large a few extra 1s count heavily, because every one of the sixteen bits has to be a 1. Across every setting of this page that lets any false positive through, the estimate from the bits actually set is the closer of the two, by ratio to the measured rate, in 5,356 of 6,051. A real filter can count its own 1s, so it can estimate its own rate better than the formula can. These sixteen animals are also an unlucky draw: over 150 other sets of sixteen words, a filter of this size averages 14.4%, still above the estimate.

Delete one word and another goes missing 🖖

Press Delete owl and step to the end. Owl set bits 37, 58 and 15. Fox, inserted next, landed on 14, 15 and 16, and found bit 15 already 1. Clearing owl's bits clears fox's bit 15 too, and the lookup of fox comes back “definitely not” for a word that is in the filter. That is a false negative, the one mistake a Bloom filter promises never to make. A bit records only that some word set it, never which, so no single bit can be safely taken back. In this 64-bit filter, deleting six of the eight words would take another word down with it. The usual remedy keeps a small counter in each position instead of a single bit, adding one on insert and subtracting one on delete, and pays for it in memory.

How small could Bloom's 1970 hyphenation filter be? 4 steps
Burton Bloom's example in 1970 was a hyphenation program for 500,000 words. A few simple rules hyphenate 450,000 of them; the other 50,000 must be looked up in a dictionary on disk. He proposed keeping a filter of those 50,000 words in core memory and accepting that 1 in 16 of the easy words would send the program to the disk for nothing. How many bits does the filter need, with how many hash functions, and how many disk reads are left? Then set this page to the same number of bits per word and measure.

Open this problem in the tool
1. At the best k, the standard estimate needs log₂(1/p) / ln 2 bits per word. For p = 1/16 that is 4 / 0.6931 = 5.77 bits, so the filter is 50,000 × 5.77 = 288,539 bits: Bloom's own figure was “less than 300,000 bits”. The best k is 5.77 × ln 2 = 4, and with four hash functions half the bits are expected to be 1.
  
  $\frac{lo g _{2} 16}{ln 2} = \frac{4}{0.6931} = 5.77 bits per word, 50000 \times 5.77 = 288539 bits, k = 5.77 \times ln 2 = 4$
2. Every one of the 50,000 hard words still goes to the disk, and so does 1 easy word in 16, which is 450,000 / 16 = 28,125 more. That is 78,125 disk reads out of 500,000, or 15.6%. Bloom rounded it to 78,000, a saving of 84% against going to the disk for every word.
  
  $50000 + \frac{450 000}{16} = 78125 disk reads of 500000 (15.6%)$
3. The length of a word appears nowhere in this. The filter costs 5.77 bits per word whether the word is “cat” or “incomprehensibilities”, where Bloom reckoned that a conventional hash table needed at least 19 bits on average to represent each word. Each halving of p adds 1 / ln 2 = 1.44 bits per word: for 1 in 64 it would be 6 / 0.6931 = 8.66.
  
  $\frac{1}{l n 2} = 1.44 bits per halving of p, \frac{6}{0.6931} = 8.66 for p = \frac{1}{64}$
4. This page holds at most 64 words, but the estimate depends only on m/n and k. Set m = 256, n = 44 (5.82 bits per word) and k = 4. 122 of the 256 bits are 1, 47.7%, and 535 of the 10,000 never-inserted strings answer “probably yes”: 5.35%, under the 1/16 = 6.25% the filter was sized for. The standard estimate for this filter is 6.11%.
  
  $\frac{256}{44} = 5.82 : \frac{535}{10 000} = 5.35% < \frac{1}{16} = 6.25%$
Answer

288,539 bits and 4 hash functions, leaving 78,125 disk reads of 500,000. The page's 44 words in 256 bits measure 5.35%, inside the target. That is one filter of 44 words. Whether 50,000 words in 288,539 bits land as close to 1/16 the page cannot test: it stops at 64 words.

$288539 bits, k = 4, 78125 disk reads$

Learning path

References (1)

The method itself, the turning point at half the bits set in the first insight, and the hyphenation example the worked problem recomputes: Burton H. Bloom, "Space/time trade-offs in hash coding with allowable errors," Communications of the ACM 13(7), July 1970, pp. 422–426.

By the 42Math team · Reviewed against published sources. Corrections welcome.

Bloom Filter: Definitely Not, or Probably Yes

The theory — Bloom Filter: Definitely Not, or Probably Yes

What each symbol means

Sixteen hash functions do worse than one 🖖

Counting this filter's 1s beats the standard estimate 🖖

Delete one word and another goes missing 🖖

Problem solved in full

What a data structure makes cheap