GenerateRandomSearch

Bloom Filter Generator

A Bloom filter answers \u201cis this present?\u201d with either \u201cno\u201d or \u201cprobably\u201d, in a fraction of the space a real set would take. The \u201cno\u201d is never wrong, which is the guarantee worth checking, and the \u201cprobably\u201d is wrong at a rate you can predict from the size and the number of hash functions. This builds one, measures the rate against thousands of absent items, and compares it with the theory.

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 compares it against the standard formula. Before display every inserted item is looked up again, and a single false negative would be reported as a failure.

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 assumes independent uniform hashing, so the measured figure will not match it exactly.
  • 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.

Related generators