The false-positive rate
The chance that a Bloom filter answers "probably present" about something it has never seen is not luck — it follows from three numbers. With m bits, k hash functions and n items inserted, the standard result is (1 − e^(−kn/m))^k, minimised when k is (m/n) ln 2. This page does not assert that. It builds real filters out of real hash functions, inserts real items, asks each filter about thousands of items it has never seen, counts the ones that come back wrongly positive, and draws the measured rate against the predicted curve.
When it is the right choice
Before choosing the size of a filter. The three numbers trade off against each other: more bits buys accuracy with memory, more hash functions buys accuracy with time up to a point and then costs accuracy, and more items spends whatever accuracy is left. The formula turns "how big should this be" from a guess into arithmetic.
How it works
- Fix two of the three numbers (m, n, k) and step the third across a range.
- At each step, build several filters independently, each holding its own n items, so the measurement averages over item sets the way the formula does.
- Query every filter with thousands of items known not to be in it, and count how many come back positive.
- Divide by the number of queries, and draw that beside (1 − e^(−kn/m))^k.
Worth noticing
- More hash functions help, then stop helping, then actively hurt: past the optimum each extra hash sets more bits than it checks, and the array fills up faster than the extra check is worth.
- The measured curve sits slightly above the formula more often than below it. That is a known property of the formula rather than noise — its derivation assumes the k bits a query reads are independent, which they are not, so it predicts a touch low at small m.
- At the low-rate end of a sweep a measurement gets hard rather than easy: a rate of one in a thousand needs hundreds of thousands of queries to pin down at all, which is why this page refuses a configuration whose own best rate is below what it can resolve.
Cost
- Best
- O(k)
- Average
- O(k)
- Worst
- O(k)
- Space
- O(m) bits