Bloom filter

A Bloom filter hashes each inserted item into several bit positions. A lookup checks those positions without storing the original items.

For example, a database can avoid a disk read when a Bloom filter says a requested key is definitely absent. A “possibly present” result may be a false positive and needs a real lookup.