DI Management Home > Mathematics > Algorithms > Bloom filter calculator

# 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.

number of items in set
number of bits in filter (optional form b^e, e.g. `2^16` = 65536)
number of hash functions
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, 216 bits) and use k=7 hash functions.

Q. I have 6550 items in my set and propose to use a bit filter of length 216 (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 216 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.