Skip to content
Omnikalc

Bloom filter calculator

Enter the number of items and the false positive rate you accept to get the size of the bit array, the number of hash functions and the memory needed.

Updated on
Your inputs

Value out of range

%

Value out of range

Results

Bit array size (millions of bits)

9.59

Memory
1.20 MB
Bits per item
9.59
Number of hash functions
7
False positive rate with the rounded number of hashes
1.004 %
Memory saved compared with 64-bit keys
85.0 %

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.

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.

Frequently asked questions

What is a Bloom filter?

A Bloom filter is a compact structure that tells whether an item is possibly in a set or definitely not. It sets k bits of a bit array for each item added. It never gives a false negative, but it can give a false positive, whose rate depends on the bits per item and on k.

How are the size and the hash count chosen?

For a target rate p, the optimal size is m = −n ln p / (ln 2)², about 9.6 bits per item for 1 %, and the optimal number of hashes is k = (m / n) ln 2. The calculator rounds k to a whole number and shows the real rate with it.

Where are Bloom filters used?

Databases and key-value stores use them to skip disk reads for missing keys, browsers and caches use them to avoid useless lookups, and network systems use them to test membership cheaply. They cannot delete items unless a counting variant is used.

Was this calculator helpful?

Thanks for your feedback!

Results are estimates provided for information purposes. They do not replace professional advice.