Skip to content
Space/Time Trade-offs in Hash Coding with Allowable Errors 3 min

Burton H. Bloom · Communications of the ACM 1970

Space/Time Trade-offs in Hash Coding with Allowable Errors

The 1970 paper behind the Bloom filter: a few bits and hash functions that say 'definitely not' or 'probably yes'. Build one and hunt for a false positive.

Read the original paper

Algorithms · White Belt · Pro · 3 min read

Space/Time Trade-offs in Hash Coding with Allowable Errors

Imagine a spell checker that must decide, thousands of times a second, whether a word is in a huge dictionary. Keeping the dictionary in memory takes a lot of space. Looking each word up on disk is slow. Burton Bloom's 1970 paper offers a middle path: a tiny structure that answers "definitely not here" or "probably here" in a fraction of the space.

His own example is automatic hyphenation. Simple rules can hyphenate about 90 percent of English words. The remaining words need a dictionary on disk. If you could quickly rule out most words that are not in the exception list, you would rarely touch the disk. The structure he describes is now called a Bloom filter.

A Bloom filter is a row of bits plus a few hash functions. It can say a thing is definitely not in a set, or probably in it. It never forgets something you added, but it sometimes claims to have seen something it has not. In exchange it uses very little memory.

Adding and checking

Start with m bits, all zero. Pick k different hash functions. To add a word, run it through each hash function. Each gives a position, and you set those k bits to 1. That is all. The word is not stored.

Adding a word: run it through several hash functions. Each one points at a position in a row of bits, and those bits are set to 1. The word itself is not stored.

To check a word, compute its k positions the same way and look at those bits.

  • If any bit is 0, the word was never added. Had it been, that bit would be 1. This answer is always right.
  • If all bits are 1, the word was probably added. But other words may have set those same bits by coincidence. That is a false positive.

Keep reading with Pro

This paper is part of Pro. Pro and Architect open the full breakdown, with animated diagrams, interactive elements you can play with and a quiz. A few papers stay free to read in full.

Still to read

2 more sections, 1 more diagram and 2 interactive elements to play with

  • Why errors only go one way
  • Where Bloom filters earn their keep

Found this breakdown useful?

Share it with someone else wrestling with this paper.

Discussion0

Join the Discussion

Sign in to leave comments, reply to others, or like insights.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!

Enjoyed this? Get more like it.

New paper breakdowns, levels, and one concept worth knowing, straight to your inbox.

No spam, ever. Unsubscribe in one click.

Enjoyed this content?

Your support keeps us creating free resources

We put a lot of hours into researching and writing these guides. If it helped you, consider buying us a coffee. Every bit goes toward keeping ScaleDojo's content free and growing.

$

One-time payment via Stripe. ScaleDojo account required.