Sizing: Memory, Optimal k, and Bits per Element

In one line

For a target error p, the filter needs m = −n ln(p) / (ln 2)² bits (about 1.44 × log2(1/p) bits per item) and k = (m/n) ln 2 hash functions. At 1% that's ~9.6 bits and 7 hashes per item; each 10× lower error costs ~4.8 more bits per item.

0/4 · 0%

Think of it like this

Buying a bigger notebook for fewer smudged entries. There's a fixed exchange rate: every extra five or so lines per entry makes mistakes ten times rarer.

Key ideas

01
Optimal k: for fixed m and n, p is minimised when k = (m/n) ln 2, which makes the fill ratio exactly 50%. Too few hashes give each lookup too few chances to find a zero; too many fill the array too quickly. Round to an integer (usually down slightly for CPU).
02
Memory for a target: substituting optimal k gives p = (1/2)^k = e^(−(m/n)(ln 2)²), so m = −n ln p / (ln 2)² ≈ 1.44 × n × log2(1/p). Bits per element depend only on p, not on item size.
03
Handy table: p = 10% → 4.8 bits, k = 3; 1% → 9.6 bits, k = 7; 0.1% → 14.4 bits, k = 10; 0.01% → 19.2 bits, k = 13.
04
Unit conversion: bits ÷ 8 = bytes; ÷ 10^6 = MB (or ÷ 2^20 = MiB); ÷ 10^9 = GB. Be explicit about MB vs MiB in interviews.
05
Rule of thumb: 1 billion items at 1% ≈ 1.2 GB; at 0.1% ≈ 1.8 GB. Scale linearly with n.

Code & diagrams

sizing-table.txttext

Target p   bits/item  optimal k   100M items    1B items     10B items
10%        4.79       3.3 -> 3    59.9 MB       599 MB       6.0 GB
1%         9.59       6.6 -> 7    119.8 MB      1.20 GB      12.0 GB
0.1%       14.38      10.0 -> 10  179.7 MB      1.80 GB      18.0 GB
0.01%      19.17      13.3 -> 13  239.6 MB      2.40 GB      24.0 GB

m = -n ln(p) / (ln 2)^2        k = (m / n) ln 2        bits/item ~ 1.44 * log2(1/p)

Sizing.javajava

static long optimalBits(long n, double p) {
    return (long) Math.ceil(-n * Math.log(p) / (Math.log(2) * Math.log(2)));
}
static int optimalHashes(long n, long m) {
    return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
}
// n = 100_000_000, p = 0.01 -> m = 958,505,838 bits (119.8 MB), k = 7

Interview problem

The problem

100 million items at 1%, then compare error targets

You need a filter for 100 million items with a 1% false-positive rate. Calculate m and k and convert bits to bytes, MB and GB. Then compare p = 10%, 1%, 0.1% and 0.01%, and do the same for 1 billion items at 0.1%, 1% and 0.01%.

You're given

n = 100,000,000
p = 1%
then n = 1,000,000,000

Explain it without notes

Why is the optimal fill ratio 50%?

Practice

Size a filter for 250 million items at 0.5%.

Trade-offs

↔
Tighter error rates cost memory logarithmically; the right p comes from the cost of a false positive, not from a habit of using 1%.

Done when you can

I can compute m, k and memory in bytes/MB/GB for any n and p.

Command Palette