Probabilistic Data Structures

Overview

Probabilistic data structures answer set-membership and cardinality questions using far less memory than exact structures, in exchange for a bounded, tunable error rate. The Bloom filter is the canonical example: it can report that an item is possibly present or definitely absent, meaning it may return false positives but never false negatives.

🧠 Mental model: A Bloom filter is like a bouncer with a guest list written in smudgy ink. He can definitely tell you "you are NOT on the list," but sometimes says "I think you might be on the list" when you're not (false positive).

Key Concepts

A Bloom filter is a bit array of size m paired with k independent hash functions. To insert an item, hash it with all k functions and set the bits at those positions. To query an item, hash it the same way and check those bits: if any bit is 0 the item is definitely absent; if all are 1 the item is probably present.

False positives arise because different items can set overlapping bits, so a query may find all its bits set by chance. False negatives are impossible: once an item's bits are set, they are never cleared, so a stored item always tests positive. The false-positive rate rises as the filter fills and is tuned by choosing m and k for the expected item count. Standard Bloom filters do not support deletion; counting Bloom filters trade extra space to allow it. Related structures include HyperLogLog for cardinality estimation and Count-Min Sketch for frequency estimation.

Structure	Question answered	Error profile
Bloom filter	Is this item in the set?	False positives possible, never false negatives
HyperLogLog	How many distinct items?	Bounded estimate error
Count-Min Sketch	How frequent is this item?	Overestimates only

Trade-offs

A Bloom filter can shrink membership state by an order of magnitude, which lets it live in memory as a fast guard in front of slow storage. The price is occasional false positives that trigger an unnecessary check, so it suits workloads where a wrong "maybe" is cheap but a missed "no" is expensive. It also cannot list its contents or, in the basic form, delete entries, so it complements rather than replaces an exact index.

Interview Tips

Lead with the asymmetry: "possibly present" versus "definitely absent" is the whole value.
Give a use case where a false positive is harmless, such as a pre-check before a disk read.
Note the tuning knobs m (bits) and k (hashes) and that the error rate grows as the filter fills.
Mention counting Bloom filters if the interviewer asks about deletion.

Summary

Probabilistic data structures save memory by allowing a small, bounded error.
A Bloom filter tests set membership with a bit array and multiple hash functions.
It may return false positives but never false negatives, so a negative answer is always correct.
The false-positive rate is tuned via the bit-array size and number of hash functions.
Bloom filters excel as cheap in-memory guards in front of expensive storage lookups.