The Bloom filter calculator gives the size of the bit array, the number of hash functions and the memory needed for a number of items and a false positive rate that you accept.
How the calculation works
- Enter the number of items to store.
- Enter the false positive rate you accept, in percent.
- The calculator gives the bits, the memory, the bits per item, the hash functions, the real false positive rate and the saving against storing keys.
Example
For 1,000,000 items and a rate of 1 %, m = −10⁶ × ln 0.01 / (ln 2)² = 9.59 million bits, which is 1.20 MB, or 9.59 bits per item. The optimal number of hashes is 7, and the real false positive rate with it is 1.004 %.
Why it matters
The calculator helps developers, database engineers and students to size a Bloom filter before building it, and to weigh the memory against the number of useless lookups.
Good to know
The false positive rate rises quickly if you insert more items than planned, so size the filter for the maximum number of items. Each tenfold drop in the rate costs about 4.8 more bits per item. A rate of 0.1 % needs about 14.4 bits per item and 10 hashes. Use independent and fast hash functions, or two hashes combined to give more, a trick that keeps the quality. Cuckoo filters and quotient filters offer deletion and better space use at low rates. A filter in front of a slow store such as a disk or a remote service pays off when most lookups are for missing keys.
Related tools
The hash collision calculator covers the birthday effect, the binary search steps calculator counts comparisons, the Shannon entropy calculator measures information and the cache hit ratio calculator describes caches.