Last updated: 2026-07-13

Bloom Filter Sizing

A Bloom filter is a compact way to answer one question: "have I probably seen this item before?" It stores no keys, only a bit array, and trades a small, tunable chance of a false positive for a large saving in memory. Two numbers decide its shape — how many items you expect to store and how often you can tolerate a false match — and from those the optimal bit-array size and hash count follow directly.

The formula

For $n$ expected items and a target false-positive rate $p$, the bit array that minimizes memory has length

The optimal number of hash functions is then

rounded to the nearest whole number. Here $m$ is the number of bits, $k$ is the number of independent hash functions applied to every item, and $\ln 2 \approx 0.693$. Since $p$ is a probability below 1, its natural logarithm is negative, so both formulas produce positive values.

Worked example. A filter for one million items ($n = 1{,}000{,}000$) at a 1% false-positive target ($p = 0.01$):

So one million items at 1% cost about 1.14 MiB of memory and seven hash functions — roughly 9.6 bits per item, a figure that holds for any item count at that accuracy.

Bits per item and the accuracy ladder

Because the size formula is linear in $n$, the storage cost per item, $m / n = -\ln p / (\ln 2)^2$, depends only on the target rate. That makes it a clean way to compare accuracy budgets.

Each tenfold drop in the false-positive rate adds about 4.8 bits per item and roughly three hash functions. The memory grows only linearly while the error rate falls geometrically, which is what makes Bloom filters attractive.

Why the hash count matters

With the array size fixed, too few hash functions leave the bits sparse and easy to match by accident, while too many fill the array so densely that almost every bit is set. The sweet spot sets about half the bits and lands at $k = (m/n)\ln 2$. Because $k$ must be an integer, the calculator rounds it, and the actual false-positive rate is recomputed from that rounded value:

For the example above the rounded $k = 7$ yields about 1.004%, a shade above the 1% target because the ideal $k$ was 6.64 rather than a whole number.

What a Bloom filter can and cannot do

A Bloom filter never produces a false negative: if it says an item is absent, it truly is. The only error is a false positive, whose rate this calculator sizes. Standard filters support insert and query but not deletion, because bits are shared across items — clearing one item's bits could corrupt others. When deletion is required, a counting Bloom filter swaps each bit for a small counter at several times the memory, and a cuckoo filter offers deletion with comparable sizing.

One caveat: a filter is sized for a fixed $n$. Insert many more items than planned and the array saturates, driving the false-positive rate above the target. If growth is likely, size for the larger count up front or use a scalable design that chains several filters together.

Rounding in practice

The bit count $m$ from the formula is rarely a round number. Real implementations allocate whole machine words or memory pages, so they round $m$ up, which nudges the achieved false-positive rate slightly below the target — a small bonus. The size shown here is the theoretical minimum before that rounding.

Related estimates

Bloom filters lean on hashing, so the odds of two items sharing a hash are governed by the same birthday mathematics — see the Hash Collision Probability Calculator. For fixed-length identifiers, the UUID Collision Probability Calculator applies the same reasoning to UUIDs, and the Shannon Entropy Calculator measures the information a data set carries.