- Author
- Sam Rose
- Published
- 19 February 2024, updated 25 October 2026
- Kind
- Personal blog post, interactive visual explainer
- Original
- samwho.dev/bloom-filters
- Subject
- Databases and storage
- Themes
- Getting good, Close to the machine
What it is
Sam Rose writes a tutorial for programmers who know what a hash function is. The post aims to show when a Bloom filter is worth using.
What it says
- A Bloom filter can give definite no answers, but a yes only means maybe.
- A Bloom filter never gives a false negative, and the post stresses this.
- The post assumes 1,000,000 bad links totalling 20MB. A filter with a 1 in a million error rate could hold them in 3.59MB.
- Each item sets bits chosen by hash functions. A full filter claims everything is present.
- More hash functions lower errors but fill the filter faster and cost more.
- Formulas give the best bit and hash counts from item count and error rate.
- Standard filters cannot delete items. Counting variants can, but allow false negatives.
What evidence it gives
The post uses worked examples and short formulas in JavaScript. It gives two real uses, Akamai caching and Google BigTable. It also says Chrome used a Bloom filter until 2012. It offers no benchmarks of its own.
Interests and limits
This is a personal teaching post with no commercial stake apparent. It was read as text only, so the interactive demos were not run. The size figures are illustrations of one scenario. The post says the tool is niche.
Connections
These links are this wiki's own reading, not claims the sources make.
- A catalog of side effects. A Bloom filter may say maybe, but never a false no. An over-approximated effect may block a valid reorder, but never permits a wrong one. Both stay safe by erring in one chosen direction. What would a one-sided guarantee look like for agent memory?
- I accidentally turned LLM memory into program analysis. Commenters report models that keep using conclusions already disproved. A standard Bloom filter has a similar difficulty: items cannot be deleted. Counting variants allow it, but give up the promise of no false negatives. Forgetting may be the expensive operation in any memory.