The set that forgets what it holds

First, the problem

Say you’re crawling the web and you need to answer one question, billions of times: have I seen this domain before? The obvious answer is a hash set. Store every domain, look it up, done. That costs you gigabytes.

A Bloom filter answers the same question in a fraction of the space. It never stores a single domain.

Step one

One hash, one bit

Start with an array of 32 bits, all off. Take a domain, run it through a hash function, and mod the result by 32. You get a number between 0 and 31. Flip that bit on, then throw the domain away. The bit is all you keep.

Step two

Three hashes, three bits

One bit isn’t enough: with only 32 of them, any two domains collide constantly. So use several independent hash functions. The same domain now flips three bits, and a later lookup has to find all three on. Three collisions at once are far rarer than one.

Step three

Now do it four times

Every insert flips three more bits into the same array. Nothing is ever separated out again; bits overlap, and the filter has no idea which domain lit which bit. Watch the array fill.

Step four

Asking the question

A lookup runs the same three hashes and checks those three bits. If even one of them is off, the domain cannot have been inserted: flipping is one-way, so a bit that would have been set is still zero. That’s a no you can bet on. If all three are on, all you know is that something set them.

Your turn

Break it yourself

An empty array, the same three hash functions. Insert whatever you like, then ask about something you never inserted. Keep going until the filter lies to you.

The catch

When the filter lies

Back to the four domains from before. The domain below has never been inserted into this filter. Ask anyway. The filter says yes. Between them, the four already inserted have lit all three bits the new one hashes to.

This is why the trade is usually fine. A Bloom filter stands in front of an expensive check and takes the easy half of the work; the real lookup still runs whenever the answer comes back probably, and when it’s wrong you’ve spent one round-trip you were going to spend anyway. When the answer is no, you skip the lookup, and that one is never wrong. You pay only for the false yeses, at a rate you set yourself.

The tradeoff

The rate is a setting

Two things set the false positive rate, and both are yours to choose. The first is size: cram more domains into the same 32 bits and the array saturates; once nearly every bit is on, the filter says yes to everything. Give it more bits and the rate collapses.

The number of hashes is the second dial, and it cuts both ways. One hash is weak evidence: the whole test is a single matching bit. Four hashes demand four matching bits, which is harder to hit by accident, but each insert now burns four bits, so the array fills that much faster. Push it far enough and more hashes make the filter worse.

Scale

Thirty-two bits was a toy

Here is the same structure at a size you’d actually deploy: 70,400 bits, one pixel each. Every domain still flips exactly three of them. At this density you stop reading individual bits and start reading texture. The texture is the false positive rate.

Then change the array size without touching anything else. Same domains, same three hashes, four times the room. The texture thins out and the rate goes with it. That is the claim from the previous section, give it more bits and the rate collapses, with nothing hidden behind it.

You’ve been using them all along

Databases check one before touching disk. Browsers used to check one before asking whether a URL was malicious. CDNs use one to decide whether an object is worth caching. Registrars answer is this name taken without waiting on a registry; name.com’s zone check is a preliminary answer by design. All of them spend a cheap maybe to avoid an expensive lookup.

We used one to cache domain availability, so most requests never reached the registry. A filter pays off when the check behind it is expensive and most of what you ask about isn’t there. If most of your lookups find something, it has little to rule out.

A Bloom filter is precise about absence and vague about presence, and only one of those halves can ever be wrong. If you need the vague half to be reliable, you have the wrong structure.