Your browser wants to know whether a web address is on a list of a million dangerous sites. Storing the whole list on every device would be heavy, and asking a server every time would be slow. There is a trick that answers in a few memory lookups using a handful of bits per entry. The catch is that it is allowed to be wrong in exactly one direction.
A Bloom filter is just a row of bits, all starting at 0. To add a word, you run it through k different hash functions. Each one turns the word into a position in the row, and you flip those k bits to 1. To ask whether a word is in the set, you compute the same k positions and look. If any of them is still 0, the word was never added. If all are 1, the word is probably in.
Try it. Add a few words, then test one you did not add.
Changing k clears the filter, because the old words were stored with different hash functions. Red outlines show the positions checked by your last test.
A bit is only ever flipped from 0 to 1, never back. So a word that was really added always finds its k bits set. That means the filter never says "no" to something it holds: no false negatives. But other words may have flipped those same bits by accident. When a stranger's k positions all happen to be 1 already, you get a false positive.
Keep adding words in the demo above and watch the grid fill up. A fuller grid means more accidental matches. With n words, m bits and k hashes, the false positive rate is about (1 − e−kn/m)k.
More hashes make each test stricter, but every word also sets more bits, so the grid fills faster. The balance point is k ≈ (m/n) · ln 2, about 0.69 hash functions for every bit you budget per word. At that setting, about half the bits end up set.
That gives a handy rule: roughly 4.8 bits per word for a 10% false positive rate, and about 9.6 bits per word for 1%. Each extra 4.8 bits per word or so cuts the error rate by another factor of ten. Nothing else is stored: no words, no lengths, just bits. A million entries at 1% fit in about 1.2 megabytes.
Burton Bloom described the idea in 1970. Today it sits in front of slow things. A database can keep a small Bloom filter per file on disk. Asked for a key, it checks the filter first, and a "definitely not" skips the disk read entirely. A rare false positive just costs one wasted read. Browsers and caches have used the same trick to avoid checking a full list or asking a server.
The price: you cannot list what is inside, and you cannot remove a word, because clearing its bits could wipe out other words that share them. In exchange you get a tiny, very fast "definitely not".
Plan your own filter. Slide to set how many bits you spend per word, with the best k for that budget.