Bloom Filter False-Positive Rate

Build a small Bloom filter, insert a few keys, and compute the probability of a false positive from its parameters.

Problem

A Bloom filter is a compact probabilistic set that answers membership queries with no false negatives but a tunable false-positive rate. It stores no keys, only bits set by hash functions, so it is far smaller than a hash set at the cost of occasional false hits.

Parameters

With m bits, k hash functions, and n inserted keys, the false-positive probability is approximately (1 - e^{-k n / m})^k. Optimal k is about (m/n) ln 2. We use m=32 bits, k=3, n=5 keys.

import numpy as np
m,k,n=32,3,5
p=(1-np.exp(-k*n/m))**k
print('predicted false-positive rate',round(p,4))
# empirical check
rng=np.random.default_rng(9)
bits=np.zeros(m,int)
keys=[('key%d'%i) for i in range(n)]
hsh=lambda s,seed:(hash((s,seed))%m)
for s in keys:
    for j in range(k): bits[hsh(s,j)]=1
fp=0; T=20000
for i in range(T):
    q='q%d'%i
    if all(bits[hsh(q,j)] for j in range(k)): fp+=1
print('empirical',round(fp/T,4))

Result

The formula predicts a false-positive rate near a few percent for these parameters, and the empirical test over many random queries lands close to it. There are never false negatives: any inserted key always returns present, because its bits were set. Increasing m or tuning k lowers the false-positive rate; too many hash functions saturates the bit array and makes it worse.

• No false negatives ever, which is why Bloom filters guard expensive lookups (disk, network) cheaply.
• False-positive rate trades against memory; the optimal number of hashes balances the two.
• Bloom-style filters can pre-screen large key sets in Kronos data-catalog and deduplication tooling.