Build a Bloom Filter

k hashes over a bit array

Challenge 1 of Probabilistic StructuresIntermediate~50 minFree

Build a probabilistic set: k hash functions over a bit array give O(1) membership tests with zero false negatives and a tunable false-positive rate. Add fill metrics, unions, and the false-positive formula.

5 steps

1. 1Bit Array & Hashing
2. 2add and contains
3. 3Fill Metrics
4. 4Union of Filters
5. 5False-Positive Rate & Guarantees