Bloom Filter Calculator (Size, Hash Functions, False-Positive Rate)

What this tool does

A Bloom filter answers 'is this item in the set?' with either 'definitely not' or 'probably yes', using a small array of bits and several hash functions. For n items and a false-positive rate p, the optimal size is m = −n ln p ÷ (ln 2)² bits, and the best number of hashes is k = (m ÷ n) ln 2, which is just about 1.44 × log₂(1 ÷ p) bits per item. A 1 % rate costs about 9.6 bits per item and a tenth of a percent about 14.4, whatever the items are. The false-positive rate climbs quickly if you insert more items than planned, and a standard Bloom filter cannot delete.

Formula

m = −n ln p ÷ (ln 2)² · k = (m ÷ n) ln 2 · p = (1 − e^(−k n ÷ m))^k

Variables

Worked example

Limitations

• The result is an estimate based only on the values you type. Real situations often include factors this calculator does not know about.
• The formula assumes ideal conditions: no friction losses, no air resistance and no efficiency losses unless you enter them.