Bloom filters are
space-efficient probablistic data structures used to test whether an element
is a member of a set.

They're surprisingly simple: take an array of m
bits, and for up to n different elements, either test or set
k bits using positions chosen using hash functions. If all
bits are set, the element probably already exists, with a false positive
rate of p; if any of the bits are not set, the element
certainly does not exist.