Bloom Filter Generator

What this generator does

Inserts items by setting the bits their hashes point at, then tests two thousand items that were never inserted and counts how many the filter wrongly reports as present. Every inserted item is also looked up again to confirm no false negative.

How to use this tool

1. Choose how many items, how many bits and how many hash functions.
2. Run, and compare the observed rate against the predicted one.
3. Try ten bits per item with seven hashes — the classic setting.
4. Overfill the filter and watch the rate climb.

Understanding the controls

How many items

What goes into the filter. The ratio of bits to items is what actually decides the error rate.

Filter size

In bits. About ten bits per item is the classic well-sized filter, giving roughly a one percent false-positive rate.

Hash functions

Too few leaves bits unused; too many fill the filter. The optimum is about 0.7 times the bits per item.

Seed

Reproduces the same set of inserted items, so two parameter choices can be compared fairly.

Common use cases

• Sizing a Bloom filter before implementing one
• Teaching probabilistic data structures with measured rates
• Showing that false negatives are impossible while false positives are not
• Comparing the theoretical rate against what actually happens
• Generating parameters for a cache or duplicate check

How this generator works

Each item is hashed several times and the bits at those positions are set. Looking an item up checks whether all its bits are set: if any is clear it was definitely never inserted, which is why a false negative is impossible. If all are set it was probably inserted, or its bits happen to have been set by others — a false positive. The tool tests two thousand absent items to measure that rate, and gives it beside two other figures. The predicted rate is the standard formula, which is an average over every filter of that size and number of hashes. The third is what this filter's own fill implies: the share of its bits that are set, raised to the number of hashes. On a large table the three sit close together. On a small one a single filter can be far from the average — five items in 17 bits with eight hashes is predicted at 0.45, and a filter that happens to fill every bit passes everything — so the page says how many bits this one has set. Before display every inserted item is looked up again, and a single false negative would be reported as a failure; the observed rate is also held against the rate the fill implies, within the sampling error of two thousand lookups.

Randomness and fairness

Uses your browser's cryptographic random source to generate the inserted items by default. A seed switches to a reproducible sequence, which is deterministic and not cryptographically secure.

For how randomness is produced across the whole site, see how Generate Random works.

Limitations and good to know

• Items cannot be removed from a Bloom filter, since clearing a bit could break another item — counting filters exist for that.
• The predicted rate is an average over every filter of the chosen size and assumes independent uniform hashing, so one filter's measured figure will not match it exactly, and on a table of a few dozen bits it can be far off.
• This uses a simple non-cryptographic hash, which is right for a filter but must not be used where an adversary picks the inputs.
• The false-positive rate is measured against two thousand samples, so it is an estimate rather than the exact rate.

Privacy and your data

The filter is built in your browser and nothing you set is transmitted, stored or included in analytics.