← Back to the hash tables page
Bloom Filter & Sketches
Probabilistic cousins of the hash table: answer membership or frequency questions in tiny memory, accepting a small, tunable error.
What to know
- Bloom filter: k hash bits per key; "no" is certain, "yes" might be false.
- Cannot delete from a plain Bloom filter — counting variants fix that.
- Count-min sketch estimates frequencies; HyperLogLog counts distincts in ~1.5 KB.
In the wild: RocksDB/Cassandra SSTable filters, Chrome Safe Browsing, Redis PFCOUNT, ad dedup.
Algorithms to reach for
Bloom insert/query
O(k)Skip expensive lookups for absent keys
Count-min updates
O(k)Heavy-hitter detection on streams
HyperLogLog merge
O(1) per itemDistinct counts across shards