Bloom Filter
A Bloom filter stores no copy of anything you put into it. It is a row of bits, and adding a word means setting a few of them at positions the word’s own hashes pick out. Asking whether a word is present means looking at those same positions: if any one of them is clear the word was certainly never added, and if all of them are set the word was probably added, or some other words happened to set exactly those bits between them. Everything on this page is computed as you read it — the bits, the answers, and the rate at which the answers are wrong.
Twelve words, a few dozen bits, and an answer that is wrong in one direction only
1 Twelve words go in. Each one sets k bits, at positions its own hashes choose
Twelve words go in. Each sets three bits, at positions its own hashes choose, in an array of 64.
64
3
- bits set
- 26 of 64
- words stored
- none — the array holds no words
2 Ask for a word that went in: every bit it claims is already set, so the answer is yes
Ask for a word that went in. Every bit it claims is already set, because it set them.
| word | positions | all set? | answer |
|---|---|---|---|
| orange | 1, 28, 42 | yes | yes, and it is right |
| lantern | 59, 9, 13 | yes | yes, and it is right |
| harbour | 16, 31, 38 | yes | yes, and it is right |
| gravel | 19, 7, 53 | yes | yes, and it is right |
All 12 words that went in come back yes. That is not a probability: each one set the bits it is now being asked about.
3 Ask for a word that did not: the first clear bit ends it, and a no cannot be wrong
Now words it has never seen. The first clear bit ends the question, and a no is never wrong. A yes sometimes is.
“saffron” was never added, and position 5 is clear, so the filter says no. A no cannot be wrong.
| word | positions | decided at | answer |
|---|---|---|---|
| saffron | 5, 58, 40 | position 5 | no, certainly |
| absent-0 | 28, 25, 44 | position 44 | no, certainly |
| absent-1 | 2, 35, 3 | position 2 | no, certainly |
| absent-2 | 59, 22, 44 | position 22 | no, certainly |
| absent-3 | 11, 52, 3 | position 11 | no, certainly |
| absent-4 | 45, 43, 49 | position 45 | no, certainly |
| absent-5 | 41, 40, 43 | position 43 | no, certainly |
4 Five thousand words it has never seen, against the closed form that predicts how often it will be wrong
Five thousand words it has never seen, at every setting, against the closed form that predicts how often it will be wrong. The uniform probe column is the same array asked by a uniform stream instead of by the hashes, which is how the hashes are checked separately from how full the array is. Naming the column rather than counting to it: an ordinal is a second copy of the table’s shape, and this one said “third” while the column was fourth.
| bits | hashes | measured | uniform probe | (1 - e^(-kn/m))^k |
|---|---|---|---|---|
| 32 | 1 | 29.44% | 28.78% | 31.27% |
| 32 | 2 | 22.62% | 22.30% | 27.84% |
| 32 | 3 | 20.50% | 20.58% | 30.80% |
| 32 | 4 | 25.92% | 26.96% | 36.42% |
| 64 | 1 | 18.08% | 16.76% | 17.10% |
| 64 | 2 | 9.14% | 8.72% | 9.78% |
| 64 | 3 | 7.16% | 7.02% | 7.96% |
| 64 | 4 | 6.90% | 7.14% | 7.75% |
| 128 | 1 | 9.74% | 9.36% | 8.95% |
| 128 | 2 | 2.58% | 2.66% | 2.92% |
| 128 | 3 | 1.26% | 1.14% | 1.47% |
| 128 | 4 | 0.90% | 0.98% | 0.96% |
| 256 | 1 | 4.54% | 5.02% | 4.58% |
| 256 | 2 | 0.92% | 1.00% | 0.80% |
| 256 | 3 | 0.32% | 0.16% | 0.23% |
| 256 | 4 | 0.14% | 0.10% | 0.09% |
At 64 bits and 3 hashes it was wrong on 358 of 5000 words it had never seen, which is 7.16% against a predicted 7.96%.
These ran in this browser when the page loaded. Each claim, whether it held, and the number behind it.
| claim | held | measured |
|---|---|---|
| no false negatives, across 192 asks | yes | every one came back yes |
| measured rate within 2 points of (1 - e^(-kn/m))^k, over 12 settings with more than 32 bits | yes | the array and the arithmetic agree everywhere |
| hashed and uniform probes of the same array stay within 2 points at all 16 settings, and the widest gap here is 1.32 | yes | no setting separates the hashes from a uniform stream by more than that |
| and the number of set bits matches m(1 - e^(-kn/m)) | yes | every setting fills as predicted |
| and doubling the bits never makes it worse | yes | monotone at every k |
What is real here, and what is not
The hashes are four FNV-1a variants, not four independent random functions
The closed form on this page assumes the k bit positions are chosen independently and uniformly. These are one hash function run with four different offset bases, finished with murmur3’s fmix32, which is not the same thing and cannot be made the same thing. That is why the sweep prints a uniform-probe column: it asks the identical array the identical number of questions with positions drawn from a seeded uniform generator, so the fill is held fixed and the only difference is where the queries look. When that column and the measured column agree the hashes are behaving uniformly, and “agree” is a threshold rather than an identity: the check requires them within two percentage points, and the largest difference on this page is 1.32. When this page was first built they did not — at 32 bits and 4 hashes the hashed probes hit set bits 2.9 points less often, because taking a remainder modulo 32 keeps only FNV-1a’s weakest five bits. The finaliser was added for that reason and the column stayed.
The closed form is an approximation, and it is worst exactly where the array is fullest
At 32 bits for twelve words the measured rate and the formula part company by several points. That is not a defect in the filter. The formula uses the expected number of set bits, and the array in front of you has the number it actually has; at high load those differ enough to matter, and the k lookups are not independent because they index one array. The page’s own check is therefore scoped: it requires agreement within two points only above 32 bits, and says so rather than widening the tolerance until everything passes.
The corpus is five thousand generated words, not English
The absent words are the strings absent-0 to absent-4999. A list of five thousand real words typed into this page would be a fact written down that nothing could check, and it would not make the measurement more honest — the filter cannot tell what a word means. It is fixed rather than random so that a disagreement reproduces.
Nothing here is packed into real memory
The array is a JavaScript array of ones and zeros, one element per bit, which is roughly sixty-four times larger than the thing it is modelling. The whole point of a Bloom filter is the space it saves, and this page saves none of it. The counts are honest; the bytes are not.
Sources
- B. H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM 13(7), July 1970, pages 422-426.
- P. Bose, H. Guo, E. Kranakis, A. Maheshwari, P. Morin, J. Morrison, M. Smid and Y. Tang, On the false-positive rate of Bloom filters, Information Processing Letters 108(4), 2008, pages 210-213 (doi:10.1016/j.ipl.2008.05.018). Where the widely quoted closed form is shown to be an approximation rather than an identity. The authors’ copy is linked because the publisher’s is behind a challenge page that archives as nothing.
- Logical Art, the studio this belongs to.