Bloom Filters and Membership Testing

Bloom Filters and Membership Testing

A Bloom filter is a compact probabilistic set-membership structure. It answers definitely absent or possibly present; a positive never proves membership. Use it when a cheap negative answer can avoid an expensive exact lookup, while false positives are safe.

Mechanism and guarantees

An m-bit array starts at zero. Insertion hashes an item to k positions and sets those bits. A query checks the same positions: any zero proves absence; all ones mean possibly present. With insertion-only use and correct hashing, an inserted member does not become a false negative. False positives occur when unrelated inserts set every queried bit.

Sizing and worked example

For n expected items and target false-positive probability p, choose m ≈ -n ln(p)/(ln 2)^2 bits and k ≈ (m/n) ln 2 hashes. One million items at 1% needs about 9.6 million bits (1.2 MB decimal) and seven hashes, excluding overhead. Monitor occupancy because overfilling increases false positives.

Variants and distributed use

Standard Bloom filters cannot safely delete: clearing a shared bit can create false negatives. Counting filters support deletion at extra memory and counter-overflow complexity. Scalable filters add capacity as cardinality grows, usually with multiple subfilters and a defined aggregate error budget. Distributed filters can be OR-merged only when bit layout, hash seeds and parameters match. Rebuilds must account for concurrent inserts.

Failure modes and operational boundary

The false-positive estimate assumes a stable expected cardinality and well-behaved hash distribution. Too many inserts raise the false-positive rate. A stale or partially rebuilt filter can produce unsafe negatives relative to the current source. A positive is not proof of membership.

Trade-offs and alternatives

Use a filter as a negative lookup accelerator, not as an authority for payments, authorization, unique constraints or irreversible deduplication. Alternatives include exact hash sets, Cuckoo filters, database uniqueness constraints and sorted filters. Cuckoo filters support deletion but have relocation/insertion-failure behavior; exact sets use more memory but provide exact answers.

Interview transfer exercise

Can a crawler use a Bloom filter to skip duplicate URL lookups? Only if the filter is complete for the relevant normalized URL keyspace. A positive should still verify the exact durable URL key. If the filter may be stale or incomplete, a negative cannot safely suppress an exact lookup.

Read the diagram

Insert A sets bits 1, 4 and 7 → Query B sees all bits set and may be a false positive → Query C includes a clear bit and is definitely absent

View full sizeOpen original

Bloom Filters and Membership Testing

Reset viewClose

A Bloom filter can prove absence, but a positive result only means possibly present.