20.7 How do you choose size vs error rate?

At the door: A bigger card means fewer boxes shared between guests, so fewer wrong "maybes". The bouncer has to decide how big a card to carry for how many guests, before the night starts. And if far more guests turn up than planned, the card fills with ticks and says "maybe" to almost everyone.

In the system: Every structure here has a size-vs-error dial. You set it before you start, from how many items you expect and how much error you can live with.

Bloom filter, for n items and false-positive rate p:

• Bits: m = −n × ln(p) ÷ (ln 2)², about 9.6 bits per item for 1%.
• Hashes: k = (m ÷ n) × ln 2, about 7 for 1%.
• Each 10× fewer false positives costs about 4.8 more bits per item.

Figure: each 10× reduction in false positives costs about 4.8 bits per item.

For 10 million usernames at 1%: about 95.9 million bits, about 12 MB, with 7 hashes.

Overfilling is the classic mistake. A filter sized for 10 million that ends up holding 30 million doesn't fail loudly; its false-positive rate climbs to about 44% (computed in the chapter's code), and it quietly stops saving you work. Plan for growth, monitor the fill, and rebuild larger when needed (or use a scalable Bloom filter that adds layers).

HyperLogLog: error ≈ 1.04 ÷ √(registers). Quadruple the registers to halve the error. Redis's fixed choice, 16,384 registers for 0.81%, is good enough for almost all counting.

Count-min sketch: width w ≈ e ÷ ε sets the size of the overcount (as a fraction of the total); depth d ≈ ln(1 ÷ δ) sets how sure you are. Halving ε doubles the width.

Memory code: "Decide the error first; the size follows. And never overfill."

---