Bloom Filter
A tiny probabilistic set that answers “maybe present” or “definitely absent” — no false negatives.
A Bloom filter is a bit array plus k hash functions that tests set membership in far less space than storing the items. It can return false positives but never false negatives, so it guards expensive lookups (databases, crawlers, caches) with a small, tunable error rate.
Worked example: a 1% false-positive rate needs about 9.6 bits per item and ~7 hash functions, so 1,000,000 items fit in roughly 1.2 MB — versus tens of MB to store the keys themselves. An LSM-tree database checks this filter before touching disk. Gotcha: “definitely absent” is trustworthy (skip the disk read), but “maybe present” must be verified — the false positives are the price of the space saving. Also, a standard Bloom filter cannot delete an item; if you need removals, use a counting Bloom filter.