You're signing up for a new website. You type a username, hit enter, and get: “username already taken.” You try again with your birth year tacked on. Taken. You add your college roll number. Still taken. At some point you start wondering if literally every string of characters has already been claimed by someone else.
What's actually bugging me isn't the username, it's the check itself. Somewhere behind that form, the site is comparing what you typed against a list of everyone who has ever signed up. For a site with a few hundred million users, that's not a list you scan one by one and still respond in 40 milliseconds.
This is a set membership problem: given a set (all registered usernames) and an element (the one you typed), is the element in the set? And the data structure most systems reach for to answer it fast, without storing the whole set in memory, is a Bloom filter.
The trade nobody tells you about upfront
A Bloom filter is a space-efficient, probabilistic data structure for testing set membership. Both of those adjectives are doing real work, and the second one is the interesting part.
“Probabilistic” means it doesn't give you a guaranteed answer. It gives you one of two things:
- “Definitely not in the set.” This one you can trust completely.
- “Probably in the set.” This one might be wrong.
That second case, a false positive: is the price of admission. In exchange, you get a structure that can hold information about millions of items in a fraction of the memory a hash set would need, and answer in constant time. For checking whether a username is taken, an occasional false positive is a rounding error, the worst case, you fall back to a real database lookup.
How it actually works
Strip away the name and a Bloom filter is just an array of m bits, all starting at zero.
To add something, you don't store the item at all, you run it through k different hash functions, each of which spits out an index into the bit array, and you flip those bits to 1.
Say we're using 3 hash functions on a 10-bit array, and we want to insert “geeks”:
h2(“geeks”) % 10 = 4
h3(“geeks”) % 10 = 7
We set bits 1, 4, and 7:
Now insert a second word, “nerd”, which happens to hash to indices 3, 5, and 4:
Notice index 4 is now shared and both words happened to hash there. That overlap is exactly where things get interesting later.
To check membership, you run the same k hash functions on your query and look at those specific bits. If any of them is still 0, the item was definitely never added. If all of them are 1, the item is probably in the set.
That asymmetry is the whole trick. A single zero is proof. A row of ones is just... suspicious.
Why it only ever says “probably”
Let's check for a word we never inserted: “cat”.
h2(“cat”) % 10 = 3
h3(“cat”) % 10 = 7
Bits 1, 3, and 7 are all set, but not because of “cat.” Bit 1 and 7 were set by “geeks.” Bit 3 was set by “nerd.” Three unrelated insertions happened to leave a trail that “cat” walks right into, and the filter has no way to tell the difference. It confidently reports “probably present,” and it's wrong.
This is a false positive, and it's structural, not a bug. The filter never stores what it actually saw but only which bits got touched. Once two items share a bit, that bit forgets whose it was.
How do you control the false positive rate?
Two knobs: the size of the bit array (m) and the number of hash functions (k). A bigger array means bits collide less often, so fewer accidental overlaps. More hash functions helps up to an optimal point, then makes the filter crowded faster.
In practice, you pick a target false-positive rate and back intom and k from the number of expected insertions. More space always buys you a lower error rate.
One thing you can never do: delete an item from a Bloom filter. Clearing the bits for one item might silently unset a bit that another item also depends on. If you need deletion, use a variant such as a Counting Bloom filter instead.
The three properties worth remembering
- No false negatives, ever. If the filter says “not present,” that's a fact, not a guess. You can trust the no completely and treat the yes as a lead worth double-checking.
- You can't delete. Flipping a bit back to 0 might belong to more than one item. There's no way to know, so the operation just isn't offered.
- Adding never fails, but it isn't free. Every insertion nudges the false-positive rate up. Keep adding items past what the filter was sized for and eventually every query comes back “probably present.”
Where this actually shows up
This isn't a textbook curiosity, it's load-bearing infrastructure at companies you use daily, always solving the same shape of problem: “have I seen this before?” without wanting to store or query the full “this.”
Notice the pattern: none of these are the final source of truth. They're a cheap first pass, a way to say “definitely not, don't bother checking” most of the time, so the expensive real lookup only runs on the cases that need it.
That's really the whole idea. Trade certainty for space and speed, keep the trade-off honest by never lying about absence, and let the false positives get absorbed by a slower, more careful check downstream. It's a small piece of machinery, but once you notice the shape of the problem, “have I seen this before, and I can't afford to remember everything”, you start seeing it everywhere.