What is a Bloom filter?

A Bloom filter is a space-efficient probabilistic data structure that tests whether an element is a member of a set. It can return false positives (saying an element is present when it is not), but never false negatives. This makes it useful as a fast pre-filter before an expensive exact lookup.

What formulas does this tool use?

Given n expected elements and desired false positive rate p, the optimal bit array size is m = −n · ln(p) / (ln 2)², and the optimal number of hash functions is k = (m/n) · ln 2. After rounding m and k to integers, the actual false positive rate is recomputed as (1 − e^(−kn/m))^k.

Why does a smaller false positive rate require more memory?

Fewer false positives mean more bits per element, because the probability of a bit being set by chance decreases as the array grows. Halving the false positive rate (e.g. from 1% to 0.5%) adds roughly 1.44 bits per element, regardless of n.

What is the optimal number of hash functions?

At k = (m/n) · ln 2 each hash function independently sets a bit, minimizing the false positive rate for a given m and n. Using fewer functions under-fills the array; using more causes too many bits to be set, both increasing false positives.

Can I reduce memory by accepting a higher false positive rate?

Yes. For example, going from 1% to 10% false positives cuts memory roughly in half (from ~9.6 to ~4.8 bits per element). The trade-off is a higher rate of unnecessary exact lookups in your backing store.

How many bits per element does an optimal Bloom filter need?

The minimum bits per element is −log₂(p) / ln 2, which equals about 9.59 bits for p = 1%, 14.38 bits for p = 0.1%, and 19.17 bits for p = 0.01%. This is independent of n.

Bloom Filter Calculator

Enter the expected element count and false positive rate to get the optimal bit array size m and hash function count k for your Bloom filter.

Filter Parameters

Expected elements (n)

How many distinct items will be inserted

False positive rate (p %)

Enter as a percentage — e.g. 1 means 1 in 100 false positives

Optimal Parameters

Bit array size

—

bits (m)

Hash functions

—

functions (k)

m = −n · ln(p) / (ln 2)² | k = (m / n) · ln 2

Details

Memory (bytes) —

Memory (human) —

Bits per element (m / n) —

Actual false positive rate (after rounding) —

Exact m (before rounding) —

Exact k (before rounding) —

Expected Bit Fill Rate

Fraction of bits set to 1 after inserting n elements: 1 − e^(−kn/m) — optimal Bloom filters aim for ~50%.

0% — 100%

Summary

A Bloom filter uses a bit array of size m and k independent hash functions to provide fast, memory-efficient set membership tests with a tunable false positive rate. This calculator applies the standard optimal formulas — m = −n·ln(p)/(ln 2)² and k = (m/n)·ln 2 — to tell you exactly how large to make the array and how many hash functions to use for any combination of expected elements and target accuracy.

How it works

Enter the expected number of elements (n) you will insert into the filter.
Set the desired false positive rate (p) as a percentage, such as 1% or 0.1%.
The tool computes the optimal bit array size m = −n · ln(p) / (ln 2)² and rounds up to the nearest integer.
It also computes the optimal hash function count k = (m/n) · ln 2, rounded to the nearest integer.
Review memory usage, actual false positive rate after rounding, and bits per element.
Adjust either input to explore the size–accuracy trade-off interactively.

Use cases

Size a Bloom filter for a caching layer to reduce unnecessary database lookups.
Design a duplicate-URL filter for a web crawler within a fixed memory budget.
Choose hash function count and bit array size for a distributed key-value store.
Estimate memory cost before implementing a Bloom filter in an embedded system.
Verify that a published Bloom filter configuration is mathematically optimal.
Teach probabilistic data structures by exploring the n–m–k–p relationship.

Frequently Asked Questions

Last updated: 2026-06-11 · Reviewed by Nham Vu