Bloom Filters: Fast Set Membership in Almost No Space
A Bloom filter answers \"have I seen this before?\" using a tiny bit array and a handful of hash functions. It can be wrong — but only in one direction. Here's the mechanism, the math, and an interactive filter you can poke at.