Bloom Filters
A bloom filter can say a key is present when it never was. Insert keys, watch their bits light up across k hash probes, and catch the false positive the moment it happens.
Bloom Filters
You have a membership check that is expensive: a database round trip, a disk seek, a call to another service to ask "have we seen this before?" A Bloom filter is a tiny in-memory thing you put in front of that check. You ask it first. If it says no, you can skip the expensive lookup entirely and trust that answer. If it says maybe, you fall through and do the real check. Being wrong only ever costs you one wasted lookup; it never gives you a wrong answer.
Under the hood it is one bit array shared by every key. Adding a key hashes it to k positions and flips those bits to 1. Checking a key tests the same k positions. Any 0 means it was definitely never added, because adding it would have set that bit. All 1s mean it was probably added: other keys may have flipped those same bits, and the filter cannot tell the difference. That is the whole trade, and the playground below lets you trigger it yourself.
Optimal k for the current load is 1 (from k = (m/n)·ln2). Below it you waste bits; above it you flood the array and collisions rise.
No false negatives, ever. Inserting a key sets every one of its k bits to 1, and bits are never cleared. So when you query a key that really was inserted, all k bits it checks are guaranteed to still be 1. A "definitely not present" answer is therefore always trustworthy.
Why false positives happen. Different keys share the same array, so one key's bits can be set by a mix of other keys. If every bit a never-inserted key probes was already flipped on by someone else, the filter cannot tell the difference and answers possibly present. The denser the array, the likelier this collision.
The m, k, n trade-off. More bits (m) spreads keys out and lowers collisions. More keys (n) fills the array and raises them. More hashes (k) sets more bits per key, which sharpens the test up to a point, then past that it just saturates the array. The sweet spot is k = (m/n)·ln2, which keeps the array about half full and minimizes the false-positive rate (1 − e^(−kn/m))^k.