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.
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.
| Query result | Meaning | Action |
|---|---|---|
| At least one queried bit is zero | Definitely absent | May skip exact lookup only if filter completeness is guaranteed |
| All queried bits are one | Possibly present | Verify exact state when false positives matter |
| Filter is saturated | False-positive rate rises | Rebuild or scale |
| Deletion requested | Basic filter cannot clear safely | Use counting variant or rebuild |
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