Bloom filters

A Bloom filter is a compact way to test whether something is in a set, with one twist: it can say “definitely not here” or “probably here”, but never a certain yes. It’s an array of bits plus a few hash functions. Adding an item sets the bits its hashes point to; checking an item looks at those same bits, and if any is zero the item was never added. If all are one, it was probably added, though other items might have set those bits by coincidence. You trade a small, tunable false-positive rate for using far less memory than storing the items. Databases use them to skip disk reads for keys that aren’t there.