Bloom filter calculator

A calculator to find the optimum parameters for a Bloom filter, and to experiment to find the effects of changing them. For background and formulae see our page on Bloom filters.

Calculate parameters for Bloom filter

Given any 3 parameters out of (n, m, p, k), compute the 4th; or, given any two of (n, m, p), compute the 3rd plus the optimum k.

n= number of items in set

m= number of bits in filter (optional form b^e, e.g. 2^16 = 65536)

k= number of hash functions

p= probability of a false positive, a real number 0 < p < 1

Examples

Q. I have 6550 items in my set, how big should my filter be and how many hash functions (k) for a 1% probability of a false positive?

INPUT: n=6550, p=0.01

n=6550  m=62783 (7.7 kB)  m/n=9.6  k=7  p=0.010039 (1.00%)

A. Use a filter of 7.7 kB (OK, round up to 8.0 kB, 2¹⁶ bits) and use k=7 hash functions.

Q. I have 6550 items in my set and propose to use a bit filter of length 2¹⁶ (8.0 kB), what is the optimum k and subsequent probability p of a false positive?

INPUT: n=6550, m=2^16

n=6550  m=65536 (8.0 kB)  m/n=10.0  k=7  p=0.008172 (0.82%)

A. Use k=7 hash functions to get a 0.82% probability of a false positive.

Q. I have 6550 items in my set and propose to use a bit filter of length 2¹⁶ with k=5 hash functions, what is the probability of a false positive?

INPUT: n=6550, m=2^16, k=5

n=6550  m=65536 (8.0 kB)  m/n=10.0  k=5  p=0.009411 (0.94%)

A. The probability of a false positive is 0.94%

Q. I have 6550 items in my set, how big should my filter be and how many hash functions (k) for a 5% probability of a false positive?

INPUT: n=6550, p=0.05

n=6550  m=40841 (5.0 kB)  m/n=6.2  k=4  p=0.050268 (5.03%)

A. Use a filter of 5.0 kB and use k=4 hash functions.

Contact us

To comment or provide feedback on this page, please send us a message.

This page first published 4 January 2018. Last updated 17 April 2020.