Live model · Bloom filters
How Bloom Filters Actually Work
A Bloom filter remembers a set without storing it: just m bits, all 0 to start. Adding an item hashes it k ways and sets those k bits to 1. A lookup reads the same k bits. Any 0 means the item was never added. All 1s mean maybe, since other items may have set them.
A Bloom filter, one bit at a time
How to read the stage
Each cell is one bit, numbered from 0. Five fruit go in with 3 hashes each and set 13 of the 32 bits. Then three lookups. Cherry was added, so it reads three 1s. Peach reads two 1s, then a 0: it was never added. Papaya was never added either, but mango, banana and apple set its three bits, so the filter says maybe.
How the bits are picked
MurmurHash3 hashes each item twice, giving h1 and h2, and similar items get unrelated hashes. Bit i is (h1 + i·h2 + (i³ − i)/6) mod m, for i from 0 to k − 1, so two hashes stand in for k. That's enhanced double hashing. The plain form, (h1 + i·h2) mod m, can line two items up on most of their bits: with 200 items in 2,400 bits and 11 hashes, it measured 42% more false positives.
Measure it on your own list
Paste words or URLs, one a line. The model adds them, then looks up 10,000 strings it never added, probe-1 to probe-10000, and counts how many it says maybe to. That share is the false-positive rate, beside the formula (1 − e^(−kn/m))^k for n items. The curve shows the rate climbing as your list goes in. Try k = 1, then k = 30: the best k is about (m/n)·ln 2.
200 lines, up to 20,000 characters.
Break it
Table
| Items in | Measured | Formula |
|---|---|---|
| 0 | 0.00% (0) | 0.00% |
| 20 | 0.00% (0) | 0.00% |
| 40 | 0.00% (0) | 0.00% |
| 60 | 0.00% (0) | 0.00% |
| 80 | 0.01% (1) | 0.01% |
| 100 | 0.02% (2) | 0.02% |
| 120 | 0.03% (3) | 0.06% |
| 140 | 0.12% (12) | 0.13% |
| 160 | 0.22% (22) | 0.27% |
| 180 | 0.40% (40) | 0.49% |
| 200 | 0.73% (73) | 0.82% |
Added 200 items: 987 of 2,000 bits are 1 (49.4%).
Looked up 10,000 strings never added: 73 said maybe, 0.73%. The formula says 0.82%.
Never added, said maybe: probe-48, probe-190, probe-193, probe-214, probe-487, …
What the model leaves out
One filter, in memory, at a fixed size. Real ones hold millions of bits and size m and k from the n and the rate they expect. You can't remove an item: clearing its bits could erase other items. A counting Bloom filter keeps a small count in each slot for that. The filter also grows no larger as it fills, so past its planned n the rate just climbs.
Questions
- Can a Bloom filter give a false negative?
- No. Adding an item sets all k of its bits, and nothing sets a bit back to 0, so an item you added always reads k 1s. That's why a single 0 means definitely not. Filters that allow removing items, such as counting Bloom filters, can lose that promise if something is removed that was never added.
- How do you choose m and k?
- For n items and a target rate p, use m = −n·ln p / (ln 2)² bits and k = (m/n)·ln 2 hashes. About 9.6 bits an item gives 1%, and each 4.8 bits more divides the rate by 10. At the best k, about half the bits end up 1.
- Why doesn't the measured rate match the formula exactly?
- The formula is the average over every filter you could build. Yours is one of them, a little fuller or emptier than average, and the k-th power amplifies that. The 200 words below fill 49.4% of the bits, so the model measures 0.73% where the formula says 0.82%. Averaged over 100 lists, it lands within 6% of the formula.
- Where are Bloom filters used?
- Wherever a quick definitely-not saves a slow lookup. Google's Bigtable keeps one for each file on disk, so most lookups for rows that don't exist never touch the disk. Broder and Mitzenmacher's survey covers their use across networking, from web caches to routing.
- Why not use a hash set instead?
- A hash set stores every item and never errs, so when it fits, use it. A Bloom filter stores about 10 bits an item, whatever the item's length, for a rate near 1%. For a billion URLs, that's about 1.2 GB in place of the URLs themselves.
Drill the mechanism
A Bloom filter is a hash set that keeps only the bits. Contains Duplicate asks the same question, have I seen this before, with a set that stores every item and never says maybe. Two Sum and Longest Consecutive Sequence look items up in a set the same way.