Bloom filter
Applies to: general
A Bloom filter is a compact, probabilistic set: it answers "definitely not present" or "possibly present" using a bit array and several hash functions. It can give false positives but never false negatives, trading a little accuracy for very small memory.
add(x): set bits h1(x), h2(x), h3(x)
maybe(x): all those bits set? -> possibly present