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

Name: Bloom Filter Calculator
Availability: InStock
Author: Nham Vu

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

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.

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