math in bloom filter

A Bloom filter answers a narrow question: could this item be in a set? It trades occasional false positives for a compact representation. Here is how that tradeoff depends on the number of bits, items, and hashes.

Insertion and lookup

Start with an array of $m$ zero bits and $k$ hash functions, each mapping an item to an index from 0 to $m-1$. To insert an item, set all its hashed positions to 1. To look it up, check those same positions:

• If any position is 0, the item is definitely absent.
• If every position is 1, the item may be present. Other inserted items could have set those bits.

The second answer is not a probability that the item belongs to the set; that would also depend on how likely our queries are to name members. A false-positive rate instead conditions on querying an item that was not inserted.

There are no false negatives as long as inserted bits remain set and insertion and lookup use the same hashes. Clearing a bit to delete one item can break this guarantee because another item may share that bit.

For the calculations below, assume $n$ distinct inserted items, positive integers $m,k$, and ideal hashes whose outputs are uniform and independent across functions and distinct items. Repeated insertion of the same item does not add new independent hash placements.

How likely is a bit to be set?

One hash misses a particular bit with probability $1-1/m$. After $kn$ independent placements, that bit remains zero with probability

$$P_0={(1-\frac{1}{m})}^{kn}.$$

Consequently, its probability of being 1 is

$$p_1=1-{(1-\frac{1}{m})}^{kn}.$$

Let $X$ be the number of set bits. Summing the individual bit probabilities gives $\mathbb{E}[X]=m{p}_1$; this step does not require independent bit states.

False positives: exact expression and approximation

If a particular filter has $x$ set bits, each independent hash of an absent query hits a set bit with probability $x/m$. All $k$ must hit, so

$$P(\text{false positive}\mid X=x)={\left(\frac{x}{m}\right)}^k,f=\mathbb{E}\left[{\left(\frac{X}{m}\right)}^k\right].$$

Replacing the random occupancy by its mean gives the familiar approximation

$$f\approx p_1^k={[1-{(1-\frac{1}{m})}^{kn}]}^k\approx {(1-e^{-kn/m})}^k.$$

The first replacement is not exact: different bit states are dependent. Since $z^k$ is convex for $k\ge 1$, Jensen’s inequality actually gives $f\ge p_1^k$. Thus the classic formula is a lower bound, not the promised upper bound. Christensen, Roginsky, and Jimeno explain this distinction and give an exact occupancy calculation in A New Analysis of the False-Positive Rate of a Bloom Filter.

For a small example, take $m=2,n=1,k=2$. The two insert hashes coincide with probability $1/2$, leaving one bit set; otherwise both bits are set. Therefore

$$f=\frac{1}{2}{\left(\frac{1}{2}\right)}^2+\frac{1}{2}(1{)}^2=\frac{5}{8}=0.625.$$

The mean-occupancy formula instead gives $p_1^k=(3/4{)}^2=0.5625$. Small filters make the difference easy to see.

A valid upper bound

A simple bound follows directly from occupancy. At most $kn$ bits can be set, and never more than $m$, so

$$f\le {\left(\frac{min(m,kn)}{m}\right)}^k.$$

Also, $z^k\le z$ on $[0,1]$, giving $f\le \mathbb{E}[X/m]=p_1$. Combining them,

$$\text{Missing or unrecognized delimiter for left}$$

These bounds are rigorous under the stated hash model, but can be loose. In the two-bit example they give $0.5625\le f\le 0.75$, which contains the exact value $0.625$. Use the approximation for an initial capacity estimate, not as a strict error guarantee.

Choosing the number of hashes and bits

Write $a=n/m$. To minimize the exponential approximation, treat $k$ as continuous and differentiate its logarithm:

$$\frac{d}{dk}[k\ln (1-e^{-ak})]=\ln (1-e^{-ak})+\frac{ak{e}^{-ak}}{1-e^{-ak}}.$$

This vanishes at $ak=\ln 2$, the minimum, yielding

$$k_{\ast }\approx \frac{m}{n}\ln 2.$$

At this setting, about half the bits are set. Too few hashes leave useful space unused; too many fill the filter and make absent queries pass more often. Compare the positive integers on either side of $k_{\ast }$, accounting for hashing cost as well as the estimated error rate.

Substituting the optimum gives

$$f\approx \exp [-\frac{m}{n}(\ln 2{)}^2].$$

For a target rate $\epsilon$, solve for capacity:

$$m\approx -\frac{n\ln \epsilon }{(\ln 2{)}^2},k\approx -\frac{\ln \epsilon }{\ln 2}.$$

For one million items and a 1% target, this suggests about 9.59 million bits, or 1.20 MB in decimal units, and 7 hashes. Using 9,585,059 bits and 7 hashes in the exponential formula gives about 1.004%; rounding the hash count means the sizing formula alone does not enforce the target. Ten million bits with 7 hashes gives an estimated 0.819% and some capacity margin.

The filter cannot grow its capacity merely by accepting more items. With ten million bits and 7 hashes, doubling the population to two million raises the same estimate to 13.8%. Plan for the expected distinct-item count, track occupancy, and verify positive answers against the underlying set when correctness requires an exact answer.