cf.completefrontend
ADVANCED DATA STRUCTURES · ADVANCED

Bloom filter

A tiny bit array that answers "have I seen this before?" with "definitely not" or "maybe", using a few hash functions and far less memory than a set.

Time O(k * L) per add or checkSpace O(size) bits3 practice problemsStep-through picture

The idea

A set that stores every word you have seen can grow huge. A Bloom filter stores only a fixed array of bits (0s and 1s), no matter how many words you add. The price: it sometimes says "maybe" for a word you never added. It never says "no" for a word you did add.

To add a word, run it through a few different hash functions. A hash function turns text into a number, always the same number for the same text; here each number is a position in the bit array. Set the bit at every one of those positions to 1.

To check a word, compute the same positions. If any of those bits is 0, the word was definitely never added, because adding it would have set that bit. If all are 1, the word was probably added, but other words may have set those bits by chance. That chance is called the false positive rate.

An everyday example

A guest book with ink stamps

At a party, every guest presses three rubber stamps onto one shared sheet of paper; the stamps a guest uses depend on their name. Later, to check whether someone came, you look for their three stamps. If any is missing, they certainly didn't come. If all three are there, they probably came, but three other guests may have left those same stamps between them.

How the example maps to the code
In the exampleIn the code
The shared sheetthis.bits
Which stamps a name usesthis.hash(text, seed) for each seed
Pressing the stampsthis.bits[...] = 1
A stamp is missing: certainly not heresome bit is 0, so mightContain is false
All stamps there: probably hereevery bit is 1, so mightContain is true

From the slow way to bloom filter

  1. The exact way to answer "have I seen this before?" is a Set of everything seen. Its memory grows with every item: 10 million web addresses of about 50 characters each is well over 500 MB. That is too big to ship to a browser or to keep in fast memory, even though each answer is just yes or no.
  2. Suppose we may be wrong in one direction only: "no" must always be true, but "yes" may sometimes be a mistake that a slower exact check can catch later. Then we don't need to store the items at all. Hash each item to a position in a fixed array of bits and set that bit to 1. A check that finds a 0 bit knows for sure the item was never added.
  3. With one hash function, two different items land on the same bit often, so "yes" is wrong too often. Use k hash functions instead: adding an item sets k bits, and a check says "maybe" only when all k of its bits are 1. An item that was never added would have to hit k set bits by chance, which is much less likely than hitting one.
  4. The rest is tuning. With m bits, n items, and k hash functions, the chance of a wrong "maybe" is about (1 - e^(-k × n / m))^k. About 10 bits per item with 7 hash functions gives about 0.8%. A fixed bit array, k hashes per word, and an "all bits set" check: that is a Bloom filter.

How it works

  1. Create bits, an array of size zeros, and choose a few hash functions. Here each one is the same formula with a different seed.
  2. hash(text, seed): start with h = 0; for each character, h = (h * seed + charCode) % size. The result is a bit position.
  3. add(text): for every seed, set bits[hash(text, seed)] = 1.
  4. mightContain(text): for every seed, look at bits[hash(text, seed)].
  5. If any of them is 0, return false (definitely not added). If all are 1, return true (maybe added).

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. class BloomFilter {
  2. constructor(size, seeds) {
  3. this.bits = new Array(size).fill(0);
  4. this.seeds = seeds;
  5. }
  7. hash(text, seed) {
  8. let h = 0;
  9. for (const char of text) {
  10. h = (h * seed + char.charCodeAt(0)) % this.bits.length;
  11. }
  12. return h;
  13. }
  15. add(text) {
  16. for (const seed of this.seeds) this.bits[this.hash(text, seed)] = 1;
  17. }
  19. mightContain(text) {
  20. return this.seeds.every((seed) => this.bits[this.hash(text, seed)] === 1);
  21. }
  22. }

How fast it is

TimeO(k * L) per add or check
Extra memoryO(size) bits

Each operation computes k hashes over a word of L characters, regardless of how many words were added. The bit array never grows.

  • Best caseO(L)

    A check whose first position holds 0, like "snow": every stops after one hash of the L characters.

  • Average caseO(k × L)

    Every add, which always computes all k hashes, and checks of words that were added or nearly match.

  • Worst caseO(k × L)

    A check that answers true, such as "lime", computes all k hashes. The cost never depends on how many words were added.

Common mistakes

  • Treating true as "definitely present". It only means "maybe"; confirm with an exact lookup if it matters.
  • Trying to remove a word by clearing its bits, which can make other added words report "no". Use a counting filter for removal.
  • Using hash functions that are not independent (for example the same seed twice), which gives the false positive rate of fewer functions.
  • Making the bit array too small for the number of items, so almost every bit becomes 1 and every check says "maybe".

When to use it

Look for these clues in a problem:

  • You need a fast "have we seen this?" check over a huge set, and memory is tight.
  • A wrong "maybe" is acceptable because a slower exact check can follow, but a wrong "no" is not.
  • Items are only added, never removed (or use a counting variant).
  • The task gives you exact hash functions and asks which bits are set or what a check returns.

Check yourself

Answer each one in your head first, then open it.

In the trace, why does mightContain("lime") return true?

Its positions are 1 and 10. Bit 1 was set by sand and bit 10 by red, so both are 1 even though lime itself was never added.

Why can a Bloom filter never answer "no" for a word that was added?

Adding a word sets all its positions to 1, and no operation ever sets a bit back to 0. So every later check finds all 1s.

How many hashes does mightContain("snow") compute, and why?

Just 1. Its first position, bit 2, is 0, and every stops at the first false.

Why can't you remove red by clearing bits 10 and 12?

Other words may use those bits too. Clearing bit 10 here would make mightContain("lime") say false, and the same could happen to a word that really was added, breaking the "no is always right" promise.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 3 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The filter keeps one property: a bit, once 1, stays 1. No line of the code ever sets a bit to 0. So after add(text), every one of text's k positions is 1, and they stay 1 no matter what is added later. The hash functions always give the same positions for the same text, so mightContain(text) finds all 1s and returns true. That's why an added item never gets a "no".

So a "no" is always right. If mightContain finds a 0 at one of text's positions, then add(text) can't have run, because it would have set that bit and nothing could have cleared it. The answer "definitely not added" follows straight from the property.

A "yes" is only likely. Other words share the same bit array, and together they may have set every position of a word that was never added, as with lime in the trace. The more bits are 1, the more often that happens, which is why the size must grow with the number of items. A good rule: m ≈ -n × ln(p) / (ln 2)² bits for a wrong-"maybe" rate p, which is about 9.6 bits per item for 1%, with k ≈ (m / n) × ln 2 hash functions.

Going deeper

3 more ideas

Why "no" is always right

Bits only ever change from 0 to 1. When a word is added, all of its positions become 1 and stay 1. So if a check finds a 0 at one of a word's positions, that word can't have been added. A "yes" can be wrong because different words can share positions.

Choosing the size

More bits and a sensible number of hash functions lower the false positive rate. A common rule of thumb: about 10 bits per item with 7 hash functions gives roughly a 1% false positive rate, far less memory than storing the items themselves. Too many hash functions fill the array quickly; too few make collisions likely.

Cost and limits

Adding and checking compute k hashes over a word of length L, so each is O(k * L), independent of how many words were added. Memory is fixed at size bits. You can't list the words back, and you can't remove one by clearing bits, because other words may share them; a counting Bloom filter keeps small counters instead of bits to allow removal.

Work it by hand

Every step in a table, with why

A 13-bit filter with two hash functions (seeds 5 and 9). Add three words, then check four. The bits column shows index 0 on the left and index 12 on the right.

size = 13, seeds = [5, 9]

StepCallPositions for seeds 5, 9bits afterResultWhy
1add("red")10, 120000000000101-For seed 5, h goes 114 % 13 = 10, then (10 × 5 + 101) % 13 = 8, then (8 × 5 + 100) % 13 = 10. Seed 9 gives 12. Both bits become 1.
2add("sand")4, 10100100000101-Two more bits are set. The filter now has 4 of 13 bits on.
3add("jade")0, 71100100100101-After three words, 6 of the 13 bits are 1.
4mightContain("red")10, 12unchangedtrueBoth bits are 1, as they must be for a word that was added.
5mightContain("blue")10, 3unchangedfalseBit 10 is 1, set by red, but bit 3 is 0. blue was definitely never added.
6mightContain("lime")1, 10unchangedtrueA false positive: bit 1 came from sand and bit 10 from red. lime was never added, but the filter can't tell.
7mightContain("snow")2, -unchangedfalseBit 2 is 0, so every stops right there and the second hash is never computed.

The filter answered true for red, which was added, false for blue and snow, which is always right, and true for lime, which is a false positive. With 6 of 13 bits set, about 21% of all three-letter strings would get a wrong "maybe" from this tiny filter, which is why real filters use far more bits per item.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Bloom filterO(1)O(n)Per add or check: k hashes of the word, however many items were added. About 10 bits per item for a 1% wrong-"maybe" rate, when memory matters and a wrong "maybe" is acceptable.
Hash setO(1)O(n)You need exact answers, or need to list or remove items. It stores every item, so it uses far more memory per item.
Sorted array with binary searchO(log n)O(n)The set is fixed, you also need "what is the nearest item?", and items are small enough to store.
Scan a listO(n)O(n)Only for a few items, where simplicity wins.

Extra memory: O(size), fixed when the filter is made. This code keeps each bit as a number in a normal array for clarity; a real filter packs 8 bits into each byte of a Uint8Array.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Bloom filter and the other approaches, on a scale where each line up is 10 times more steps.
  • Bloom filter, Hash set O(1)
  • Sorted array with binary search O(log n)
  • Scan a list O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Bloom filter111
Hash set111
Sorted array with binary search31020
Scan a list101,0001 million

Inputs that need care

5 tricky inputs
The empty string ""
The loop never runs, so hash returns 0 for every seed. After jade set bit 0, mightContain("") returns true even though "" was never added. Reject empty input if that matters.
The same word added twice
Its bits are already 1, so nothing changes. A Bloom filter can't count how many times a word was added.
The same seed twice, such as [5, 5]
Both hashes give the same position, so the filter acts like it has one hash function and false positives become much more common. Use different seeds.
A seed that is a multiple of size, such as 13 with 13 bits
(h × 13 + code) % 13 throws away h, so only the last character matters and words ending in the same letter always collide. Pick seeds that share no factor with size.
Far more words than the filter was sized for
Almost every bit becomes 1, and almost every check says "maybe". Size the filter for the most items you expect, or start a new, bigger filter when it fills.

Variations and follow-ups

Twists interviewers add

Counting Bloom filter

Store a small counter instead of a bit at each position. add increases the k counters, a remove decreases them, and a check looks for counters above 0. Removal now works, at the cost of a few bits per position instead of one.

Two hashes make many

Instead of k separate hash functions, compute two, h1 and h2, and use (h1 + i × h2) % size as the i-th position. The false positive rate stays almost the same and each word is only hashed twice.

Growing filters

When a filter reaches its planned number of items, freeze it and start a new one with more bits and a stricter target rate. A check asks every filter, and says "maybe" if any of them does.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "huge set", "limited memory", "probably seen", or "skip an expensive lookup when we know the answer is no". If false positives are not allowed, it's the wrong tool.
  • Explain the one-way promise: bits only turn on, so "no" is certain and "yes" is "maybe". Then explain where false positives come from: other items' bits.
  • Work a tiny example by hand, like the trace: show one true "yes", one certain "no", and one false positive. It proves you understand all three outcomes.
  • Expect "how do you delete?". Answer: you can't clear bits, because other items may share them; use a counting Bloom filter with small counters instead.
  • Expect "how big should it be?". Answer with the rule of thumb: about 10 bits per item and 7 hash functions for a 1% rate, or m = -n × ln(p) / (ln 2)² in general.

Where frontend code uses it

The same idea in real UI code
  • Browsers have used Bloom-filter-like structures to check URLs against large blocklists locally, only asking a server when the filter says "maybe".
  • A feed or recommendation widget can keep a small Bloom filter of item ids the user has already seen, to skip repeats without storing every id.
  • Some CDNs and databases use Bloom filters to skip disk lookups for keys that are definitely not stored.

Related algorithms