Topic 11.2
Intermediate Questions
In one line
The maths and engineering follow-ups: sizing formulas, optimal k, double hashing, thread safety, serialisation, counting and scalable filters, and cache penetration.
Think of it like this
The practical part of a driving test. You now have to show that you can actually drive: size a filter, choose k, and explain the moving parts.
Key ideas
- 01
Memorise the key numbers: 9.6 bits per item at 1%, 14.4 at 0.1%, 19.2 at 0.01%; optimal k ≈ 0.693 × bits per item; each extra 4.8 bits per item cuts FPR by 10×.
- 02
Show the formula, then a worked number. Interviewers value both.
Code & diagrams
p ~ (1 - e^(-kn/m))^k
m = -n ln p / (ln 2)^2 (bits)
k = (m / n) ln 2 (optimal hash count)
bits per item ~ 1.44 log2(1/p)
Example: n = 10M, p = 1% -> m ~ 95.9M bits ~ 12 MB, k = 7Explain it without notes
What is the false positive formula?
How do you calculate m?
How do you calculate optimal k?
Why does using too many hash functions hurt?
Why does using too few hash functions hurt?
What is double hashing?
Why must hashes be deterministic?
How do you make a Bloom filter thread-safe?
How do you serialise a Bloom filter?
What is a counting Bloom filter?
What is a scalable Bloom filter?
How do Bloom filters help with cache penetration?
Why is Bloom-filter-only authorisation dangerous?
Practice
Size a filter for 50M items at 0.1% and state m, k and memory.
Trade-offs
- ↔
Tighter FPR costs linearly more memory (4.8 bits per item per decade) and more hashes.
Done when you can
I can answer all thirteen intermediate questions and do the sizing arithmetic live.