One-Sided

A Bloom filter is m bits and k hash functions. Insert a word: flip the k bits its hashes point at. Query a word: look at those same k bits. That is all of it, and it buys an asymmetry that no amount of tuning ever removes.

A zero anywhere is a proof. Every word that was inserted set all of its bits, and nothing here ever clears one, so a zero rules the word out — not probably, provably.

All ones is circumstantial. The bits are there; the filter has no idea who put them there.

So a false positive isn’t a bug in the arithmetic. It is a collage: k bits, each of them honestly set by somebody else. This piece is built to make that literal — every set bit wears the colour of the word that set it first, and when a word that was never inserted comes back “maybe”, its three swatches are three other words’ colours, named underneath.

The default run is 512 bits and 3 hashes, which is a filter shaped for 118 words. It is handed 180. At 95 words in, kemezes — never inserted — comes back “maybe” off bits belonging to beefozul, faplegrir and gitruta. By the end the wall is 66% full and 31.7% of never-inserted words get a “maybe”, against 27.7% predicted.

What’s on screen

• The wall. Every cell is one bit. A set bit is its owner’s colour, drawn brighter the more words have piled onto it — the wall is a record of who is responsible for what, which is exactly the record a real bit array does not keep and the reason the false positives here are legible instead of mysterious.
• The hashes, as arrows. k arcs fly from the word to the k cells it lands on, the same k cells on insert and on query. Watching the same arrows do both jobs is the part that makes the query feel like evidence-gathering rather than a lookup.
• The verdict card. NO in green with the zero bit called out, or MAYBE in amber (a word that really is in the set) or red (one that never was). The k swatches under it are the receipts: a bordered 0, or a block in the colour of whoever owns that bit, with the owners named.
• The rate, as the wall fills. Measured against the textbook (1 − e^(−kn/m))^k, with two markers: the load the filter was sized for (m·ln2/k, the point where the wall is half full) and the insert count at which it first told a lie.
• The k sweep. The same wall, the same words, every k from 1 to 12, measured end to end. The minimum is the point.
• A counter that never moves, top right: inserted words asked, inserted words answered “maybe”. It reads n/n forever. There is no false negative to find, so the piece keeps score to show you it isn’t hiding one.

The reading nobody believes until they see it

k has an optimum, and going past it makes the filter worse. At 512 bits and 180 words the sweep measures 31.5% at k=1, 25.3% at k=2, 27.7% at k=3, then 34.7, 38.6, 52.5 … and 90.3% at k=12. More hash functions means more evidence demanded per query, which should help — but it also means more bits set per insert, and past (m/n)·ln2 the wall fills faster than the extra demand discriminates. The “nine hashes, same wall” preset is the same 512 bits holding the same 180 words at 97% full, wrong three quarters of the time.

The other thing worth sitting with is how close the measurement runs to the formula. (1 − e^(−kn/m))^k assumes independent uniform hashing, which FNV-1a with four salts is not, and the two lines still track each other point for point for the whole run.

The fail state to build toward

Not a crash. The “sized for last quarter’s traffic” preset is a filter with 256 bits and 3 hashes — right for 59 keys — being handed 400. It is 99% full, answers 95.8% of never-inserted words with “maybe”, is still O(k) per query, still never returns a false negative, still honours every promise on the tin, and is now a data structure that says “maybe” to everything. Nothing alerts. The service behind it just quietly stops being protected by its cache filter and starts serving every lookup, because the filter is technically correct and practically an unconditional yes.

Things it turned up

• The proof answer gets rarer, and it is the only one worth anything. Early in the run most queries die on a zero and the card is green. By the end the wall is two-thirds ones and a green card is unusual. The filter’s value is entirely in the answers it can be certain about, and that supply shrinks monotonically with every insert.
• A member query is indistinguishable from a false positive, and the card says so in the same word. The only difference is who owns the bits — which the drawing can see because it kept the ownership record, and the filter cannot because it did not.
• 202 of the 540 bit-writes in the default run land on bits that were already set — evidence paid for and not received. A word that arrives late in a run may not flip a single new bit; it is in the filter without having changed it at all.
• Two hashes of one word can collide on one bit. The positions are not deduplicated here — that would hide a real event that costs the filter a whole hash function’s worth of discrimination for that word.

Reuse

src/one-sided.js is framework-free with no rendering in it. positionsFor() is FNV-1a with an avalanche tail and one salt per hash function — independent salts rather than the usual h1 + i·h2 double-hashing trick, which is cheaper and provably good enough but visibly correlates a word’s k positions when you draw them. simulate() returns a frame per operation carrying the k positions, which of them were fresh, who owned them at that moment and the running measured rate, so a different renderer can pick it up unchanged; stateAt() replays the inserts to reconstruct the wall at any frame rather than snapshotting the bit array per frame. sweepK() re-runs the whole stream for every k and probes with a larger held-out set, because the differences between adjacent k are a few points wide and 400 probes cannot resolve them.

node scripts/screenshot-demo.mjs regenerates thumb.png from the run’s first false positive, and fails if that frame stops being the first one.