How small can a set get?

A Bloom filterA compact probabilistic set: hash each element to k bit positions and set them. To test membership, check those bits — all set means ‘probably present’, any clear means ‘definitely absent’. answers "have I seen this before?" in a few bits per item — far less than storing the items. The price is the odd false positive: it never misses a real member, but sometimes says yes to a stranger. Spend more bits per element and that rate falls off a cliff. Pick your end of the trade.

The budget you have
Holdelements atbits eachm/n: the filter's total bits divided by the number of elements. The single knob on the false-positive rate — about 10 bits per element buys ~1%..
0.819%false-positive rate

At 10 bits each with 7 hash functions, about 1 in 122 lookups for a missing key comes back a false hit — for 1.2 MiB of memory.

0.819%false positives
7optimal hashesThe number of hash functions that minimises the false-positive rate for this many bits per element: k* = (m/n)·ln2, rounded.
1.2 MiBtotal memory
False positives vs. hashes, at 10 bits each
9.52%0.819%
1 hashoptimal k = 716

Too few hashes and you barely use the bits you bought; too many and every lookup trips over a set bit. The sweet spot is k = (bits per element) × ln 2 — here 7. The curve is shallow near the bottom, so rounding k to a whole number costs almost nothing.

Each extra bit per element
Bits / elementFalse-positive rate
4 bitsk=3
14.7%
6 bitsk=4
5.61%
8 bitsk=6
2.16%
10 bitsk=7now
0.819%
12 bitsk=8
0.314%
16 bitsk=11
0.046%
20 bitsk=14
0.0067%

The rate falls geometrically: every extra bit per element multiplies the false-positive rate by about 0.62, so ~10 bits buys 1% and ~20 buys 0.01% — independent of how many elements you store. Memory, meanwhile, grows only linearly with the count.

Have a target rate in mind? Size it from the rate →

Bloom filter sizing · p ≈ (1 − e^(−k/b))^k