Bloom Filter

A query returns either "possibly in set" or "definitely not in set".

• Space-efficient structure to test whether an element is a member of a set.
• False positive matches are possible, but false negatives are not.
• Elements can be added to the set, but not removed