Command Palette

Search for a command to run...

Hectal
Phase 0Beginner1 of 12 in Bloom Filters

Probabilistic Foundations

Why trade a little certainty for a lot of memory, the family of probabilistic data structures, and exactly what a Bloom filter promises (and doesn't).

A Bloom filter answers one question, "could this item be in the set?", using a small bit array instead of storing the items themselves. It can say "definitely not" with certainty and "maybe" with a small, calculable chance of being wrong.

This phase builds the intuition and the vocabulary: exact vs probabilistic structures, false positives vs false negatives, and where Bloom filters sit among HyperLogLog, Count-Min Sketch, Cuckoo filters and friends.

0/3 · 0%
3 topics ~24 min 6 code blocks & diagrams
Start with the first topic
1
0.1

Why Probabilistic Data Structures?

Exact structures like hash sets store every item, which becomes expensive at billions of items. Probabilistic structures store a compact summary and answer with a controlled error rate, cutting memory by 10–100× when an occasional wrong "maybe" is acceptable.

8 min 1 diagram 1 code practice

2
0.2

The Probabilistic Data Structure Family

Bloom, Counting Bloom, Cuckoo, Quotient and Xor filters answer membership; HyperLogLog estimates distinct counts; Count-Min Sketch estimates frequencies; Top-K finds heavy hitters. Choose by the question you need answered, then by deletion needs and memory.

7 min 1 code practice

3
0.3

What a Bloom Filter Is: Bits, Hashes, Insert, Lookup

A Bloom filter is an array of m bits and k hash functions. Insert sets the k bits an item hashes to; lookup checks them. Any zero bit means "definitely absent"; all ones means "possibly present". Both operations take O(k) time and the filter takes m bits of space.

9 min 1 diagram 2 code practice