Bloom filters: probabilistic set membership with no false negatives

What it is

A Bloom filter is a bit array of m bits and k hash functions. Inserting an item sets the k bits its hashes select; querying checks them. If any bit is clear, the item was never inserted; if all are set, it was inserted or the bits were set by other items, a false positive. The PostgreSQL documentation for its bloom index describes the structure as space-efficient, prone to reporting false positives, and therefore requiring every index hit to be rechecked against the actual row. The Redis documentation exposes a filter created with a desired false-positive rate and an expected capacity. The basic filter cannot delete: clearing a bit could erase evidence of another item. Counting Bloom filters and cuckoo filters exist for that need.

Why it matters

The filter fits in memory where the full set does not, and it answers "no" cheaply, which saves a disk read, a network round trip or a database query for keys that certainly do not exist. Storage engines use one per data file to skip files, crawlers use one for "seen this URL", caches use one to avoid backend lookups for unknown keys.

How to apply

• Size the filter from the expected item count and the target false-positive rate; the rate rises as the filter fills beyond its design capacity, so plan for the maximum or use a scalable variant.
• Treat every positive as "check the real store"; only skip verification where a false positive is harmless, such as an extra cache miss.
• Store the filter together with the identifiers of its hash functions, seed and size; any change means a rebuild from the full set.
• Deploy it where negative lookups dominate (unknown usernames, deleted keys, cold objects) and measure the share of queries it filters before keeping it.
• Rebuild on a schedule when the underlying set shrinks; the filter only grows.

Pitfalls

Deriving the k hashes from correlated functions inflates false positives. A filter shared between processes or languages needs bit-identical hashing. Nothing can be listed, counted or removed. A filter whose seed or size differs from the one used to build it silently returns wrong answers rather than errors. Sizing for the average rather than the peak set size defeats the purpose.