Topic 4.6
Choosing: Bloom vs HashSet vs HyperLogLog vs Count-Min
In one line
Use a HashSet when you need exact answers, the values themselves, or the data fits in memory; a Bloom-family filter when the set is huge, memory is tight and false positives are acceptable; HyperLogLog for distinct counts; Count-Min Sketch for frequencies. Never confuse membership, cardinality and frequency.
Think of it like this
Three different questions at an event: "is Priya on the guest list?" (membership), "how many different people came?" (cardinality), "how many times did Priya come back to the bar?" (frequency). Each needs a different tool.
Key ideas
- 01
HashSet: exact membership, supports delete, returns the actual values, but memory grows with item size and count. Right for small-to-medium sets or when false positives are unacceptable.
- 02
Bloom filter: approximate membership with no false negatives, fixed bits per item regardless of item size, no delete (standard), no values, no counts.
- 03
HyperLogLog: approximate count of distinct items (~0.81% error in 12 KB), no membership. Don't use Bloom for counting uniques or HLL for membership.
- 04
Count-Min Sketch: approximate frequency of each item, over-counts but never under-counts; answers "how many times", not "is it there" (though frequency > 0 implies seen, with over-count errors).
- 05
Decision chain: exact required? → HashSet or database. Deletes frequent? → Cuckoo or Counting. Static set? → Xor or Ribbon. Unknown growth? → Scalable Bloom. Otherwise → Bloom sized for the target p.
Code & diagrams
Requirement Bloom Counting Bloom Cuckoo HashSet HyperLogLog
Membership yes yes yes yes no
False positives yes yes yes no n/a
False negatives no* no* no* no n/a
Deletion no yes yes yes no
Exact answer no no no yes no
Cardinality no (est.) no no yes approximate
Values stored no no no yes no
Memory ~10 b/item ~40 b/item ~10 b/item item-size huge-scale 12 KB
* when maintained correctly (no missed inserts, no unsafe deletes)Interview problem
The problem
Compare Bloom, Cuckoo, Counting Bloom and HashSet
An interviewer asks you to compare Bloom, Cuckoo, Counting Bloom and a HashSet for a 50-million-item membership check. Give memory, operations and when to choose each.
Explain it without notes
When is a HashSet the better choice than a Bloom filter?
Practice
For your own system, list three membership checks and choose a structure for each with the decision chain.
Trade-offs
- ↔
Picking a structure for a different question (membership vs counting) can't be fixed by tuning parameters.
Done when you can
I can choose between Bloom variants, HashSet, HyperLogLog and Count-Min Sketch with reasons.