Bloom Filter False-Positive & Optimal Hash Formula

Tune LSM-tree and CDN Bloom filters without wasting RAM or over-hashing!

Invented by Burton Bloom (1970) and embedded in RocksDB, Cassandra, Postgres, and CDNs to skip pointless disk reads for absent keys, a Bloom filter maps n inserted keys into an m-bit array using k independent hash functions (zero false negatives; tunable false-positive probability FPR). More hashes are NOT always better: too few hashes leave collisions, while too many hashes fill the bit array toward all 1s! Minimizing (1 - EXP(-k * n / m))^k sets exact 50% bit-fill density via Optimal Integer Hash Count k* = MAX(1, ROUND((m / n) * LN(2), 0)), achieving Required Bits per Key m / n = -LN(p_target) / (LN(2)^2)!

Check by hand with Bit_Array_Size_m = 10,000 bits (B2 = 10 bits/key), Inserted_Keys_n = 1,000 (B3), and Target_FPR_p = 0.01 (B4 = 1.0%): Optimal Hash Count is k* = ROUND(10 * 0.693147, 0) = 7 hashes, False-Positive Probability is (1 - EXP(-7 * 1,000 / 10,000))^7 = 0.008194 (0.82% < 1.00%!), and theoretical minimum bits/key for 1% FPR is -LN(0.01) / (LN(2)^2) = 9.5851 bits/key!

Optimal Hash Count k* & Evaluated False-Positive Probability Formula

Validate m >= 1, n >= 1, and 0 < p_target < 1.

=LET(m_bt, B2, n_ky, B3, IF(OR(m_bt < 1, n_ky < 1), "Invalid Bloom Input", LET(k_op, MAX(1, ROUND((m_bt / n_ky) * LN(2), 0)), ROUND((1 - EXP((-k_op * n_ky) / m_bt))^k_op, 6))))

Theoretical Minimum Bits per Key (-LN(p_target) / LN(2)^2) Formula

Notice that every 10x reduction in false-positive rate (1% -> 0.1% -> 0.01%) costs an exact constant LN(10) / (LN(2)^2) = +4.7925 extra bits per key!

=IF(OR(B4 <= 0, B4 >= 1), "Require 0 < p_target < 1", ROUND(-LN(B4) / (LN(2)^2), 4))

Further reading

• Arte Sheets Lesson — Tail-at-Scale Fan-Out Latency & Hedged Request Formula
• Microsoft Support — EXP function