Suppose you want to answer one question, millions of times a second: have I seen this item before? A hash set answers it exactly, but it has to keep every item, so its memory grows with the data. A Bloom filter answers almost the same question in a fixed, tiny amount of space — by giving up the ability to say a definite “yes.”
It stores no elements at all. Just a bit array of length m and k hash functions. Try it: add a few words, then test for words you did and didn't add.
How it works
To add an item, hash it with each of the k functions to get k positions in the bit array, and set every one of those bits to 1. Bits are never cleared, and different items happily share bits.
To test an item, hash it the same way and look at those k bits. If any of them is 0, the item was definitely never added — setting a bit only ever turns it on, so a zero here is proof. If all of them are 1, the item is probably present: it might have been added, or those bits may just have been set by other items that happened to collide.
Tuning the trade-off
The false-positive rate depends on how full the array is. After inserting n items into m bits with k hashes, the probability that a given non-member tests positive is roughly:
p ≈ (1 − e^(−kn/m))^k
Two knobs fall out of this. Give the filter more bits per item and p drops. And for a fixed size, there's an optimal k — too few hashes and members are easy to fake; too many and the array saturates. The sweet spot is k = (m/n)·ln 2, which fills almost exactly half the bits.
Where it fits
Bloom filters shine as a cheap front-line filter in front of something expensive. Databases like Cassandra and Bigtable check one before touching disk: a negative means “the key isn't in this file, skip the read.” CDNs use them to avoid caching one-hit URLs; browsers have used them for malicious-URL checks; crawlers use them to skip already-visited pages. In each case a rare false positive only costs a redundant lookup — never a wrong answer.