How to use it
- In Size for a target rate mode, enter the number of items and the false positive rate in percent (1 means one wrong yes per hundred lookups of absent items).
- Read the number of bits, the memory in bytes, KiB or MiB, and the number of hash functions.
- In Rate of a filter mode, enter n, m in bits and k to get the false positive rate and the best k for that size.
How it works
A Bloom filter is an array of m bits. Each item sets k bits chosen by k hash functions; a lookup checks those k bits. The formulas:
- m = ⌈−n × ln p ÷ (ln 2)²⌉
- k = round(m ÷ n × ln 2), at least 1
- p = (1 − e^(−k × n ÷ m))^k
Because m is rounded up and k to a whole number, the real rate differs slightly from the target; the calculator shows it as Rate with these m and k.
Worked example
One million items at 1 %:
- m = 1,000,000 × 4.6052 ÷ 0.48045 = 9,585,058.4, rounded up to 9,585,059 bits;
- memory: 9,585,059 ÷ 8 = 1,198,133 bytes, or 1.14 MiB;
- k = 9.585 × 0.6931 = 6.64, rounded to 7 hash functions;
- the real rate with 7 hashes is 1.0039 %, about one false positive in 100 lookups.
Tips
- Doubling the filter size does not halve the rate, it squares it (roughly): 1 % becomes about 0.01 %.
- In code, two hash functions are enough to simulate k: h1 + i × h2 for i = 0 … k − 1.
- If items must be removed, look at counting Bloom filters or cuckoo filters.