Model
Bloom filter false positives
At the optimum exactly half the bits are set: the maximum-entropy state of the array.
- Bits
- bits in the filter
- Keys
- keys inserted
- Hash functions
- hash functions per key
How it behaves
One input on the horizontal axis, the others held fixed.
Data table
| Bits per key m/n | False-positive rate |
|---|---|
| 2 | 38.3% |
| 2.27 | 33.5% |
| 2.55 | 29.4% |
| 2.83 | 25.7% |
| 3.1 | 22.6% |
| 3.38 | 19.8% |
| 3.65 | 17.3% |
| 3.92 | 15.2% |
| 4.2 | 13.3% |
| 4.47 | 11.6% |
| 4.75 | 10.2% |
| 5.03 | 8.94% |
| 5.3 | 7.84% |
| 5.58 | 6.87% |
| 5.85 | 6.02% |
| 6.13 | 5.27% |
| 6.4 | 4.62% |
| 6.67 | 4.05% |
| 6.95 | 3.55% |
| 7.22 | 3.11% |
| 7.5 | 2.72% |
| 7.78 | 2.39% |
| 8.05 | 2.09% |
| 8.32 | 1.83% |
| 8.6 | 1.61% |
| 8.88 | 1.41% |
| 9.15 | 1.23% |
| 9.43 | 1.08% |
| 9.7 | 0.946% |
| 9.97 | 0.829% |
| 10.3 | 0.727% |
| 10.5 | 0.637% |
| 10.8 | 0.558% |
| 11.1 | 0.489% |
| 11.3 | 0.428% |
| 11.6 | 0.375% |
| 11.9 | 0.329% |
| 12.2 | 0.288% |
| 12.4 | 0.252% |
| 12.7 | 0.221% |
| 13 | 0.194% |
| 13.3 | 0.17% |
| 13.6 | 0.149% |
| 13.8 | 0.13% |
| 14.1 | 0.114% |
| 14.4 | 0.1% |
| 14.7 | 0.088% |
| 14.9 | 0.077% |
| 15.2 | 0.067% |
| 15.5 | 0.059% |
| 15.8 | 0.052% |
| 16 | 0.045% |
| 16.3 | 0.04% |
| 16.6 | 0.035% |
| 16.9 | 0.031% |
| 17.1 | 0.027% |
| 17.4 | 0.023% |
| 17.7 | 0.021% |
| 17.9 | 0.018% |
| 18.2 | 0.016% |
| 18.5 | 0.014% |
| 18.8 | 0.012% |
| 19.1 | 0.011% |
| 19.3 | 0.009% |
| 19.6 | 0.008% |
| 19.9 | 0.007% |
| 20.1 | 0.006% |
| 20.4 | 0.005% |
| 20.7 | 0.005% |
| 21 | 0.004% |
| 21.3 | 0.004% |
| 21.5 | 0.003% |
| 21.8 | 0.003% |
| 22.1 | 0.002% |
| 22.4 | 0.002% |
| 22.6 | 0.002% |
| 22.9 | 0.002% |
| 23.2 | 0.001% |
| 23.4 | 0.001% |
| 23.7 | 0.001% |
| 24 | 0.001% |
Worked examples, recomputed
Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.
- a 1% runtime filter ≈ 9.6 bits per key
- 10 bits per key → k* ≈ 7 hash functions
- 1% needs 9.58 bits per key
- 0.1% needs about 14.4 bits per key
- 10 bits × 10⁹ keys = 1.25 GB
- 10⁶ keys × 10 bits = 1.25 MB runtime filter
Where it appears
Each mechanism states it in its own names. The general symbol each name stands for is shown with it.
- Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
- Core Data Structures
How do we choose a data structure when the real cost is set by the hardware, not by Big-O?
b (bits per key) =