How to use the bloom filter calculator
- Choose what you know: the number of items and a target false positive rate, or the number of items and the bits you can spend.
- Enter the numbers. Percent is entered as a plain number, so 1 means 1%.
- Read the bits, size, hash functions and false positive rate. Leave the simulation on to compare with a seeded run that inserts the items and tests 20,000 keys that were never added.
- Copy the table or download the CSV. Change the seed to see how much a run varies.
Formula
m = -n ln(p) / (ln 2)^2 bits
k = (m / n) ln 2 hash functions, rounded to a whole number of at least 1
p = (1 - e^(-kn/m))^k as the usual approximation
p = (1 - (1 - 1/m)^(kn))^k exactly, for independent uniform positions
n is the number of items, m the bits, k the number of positions set for each item and p the false positive rate. A filter never gives a false negative, but it can say that an item is present when it is not.
1,000 items at 1 percent
For n = 1,000 and p = 1% the formula gives m = 9,586 bits, which is 1,198 bytes or 9.59 bits per item. The best number of hash functions is 9.586 x 0.693 = 6.64, which rounds to k = 7. With those whole numbers the exact false positive rate is 1.0037% and the usual approximation gives 1.0035%.
The seeded simulation inserts 1,000 keys with 7 random positions each, which sets 52.1% of the bits, and then tests 20,000 keys that were never inserted. It finds 189 false positives, 0.945%, which is within the spread to expect for one filter of that size. For 64 KiB (524,288 bits) and 40,000 items, k = 9 and the rate falls to 0.184%.
Why bits per item matters
The error rate depends on the ratio of bits to items, not on the items themselves. About 9.6 bits per item gives 1%, and about 14.4 bits per item gives 0.1%. Each tenfold cut in the error rate costs about 4.8 more bits per item.
The best k sets half of the bits. If k is much higher or lower than the best value, the filter wastes space. A filter filled beyond the planned number of items sets more bits and the real error rate rises above the table.
What the simulation does
Real hash functions are not perfectly random, so the simulation uses an idealized one: every position is drawn uniformly from a seeded generator. It shows how close the formulas are to a run, and how much a single filter varies around its expected rate. The same seed gives the same answer every time.
The simulation is skipped for filters beyond about 8 million bits or 30 million insertions, because it would take too long in a page. For the hash functions themselves see the Hash Generator and File Checksum and the SHA-3 and Keccak Hash Calculator.
Assumptions and limits
- The formulas assume independent, uniformly random hash positions.
- Items are counted as distinct keys. Adding the same key twice sets the same bits and does not raise the count.
- The simulation tests 20,000 keys that were never inserted, so its rate has a spread of a few tenths of a point at 1%.
- Sizes use 8 bits per byte and 1,024 bytes per KiB.
- Nothing typed here leaves your browser.
Frequently asked questions
Can a Bloom filter give a false negative?
No. An inserted item always finds all its bits set. The only mistake it can make is a false positive, when the bits of an item that was never added all happen to be set by other items.
Why is k rounded?
You cannot set a fraction of a position. After rounding to a whole number the page recalculates the false positive rate, so the rate shown is for the k you would actually use.
Why do the approximation and the exact rate differ?
The approximation replaces (1 - 1/m) with an exponential, which is very close for large m. For small filters the two drift apart, and the exact formula is the better one for independent positions.
Can I remove items from a Bloom filter?
A plain filter cannot remove an item without risking false negatives for others, because bits are shared. Variants that count instead of using single bits allow removal at the cost of more space.