Skip to content
Back to Data StructuresAll lessons

Data Structures

Bloom Filter

add and mightContain: O(k), where k is the number of hash functions. This is a small constant, so both are effectively instant. A Bloom filter also uses far less memory than storing every item.

The idea, in plain English

A Bloom filter is like a bouncer with a bad memory but a clever trick. It doesn't remember names. Instead, whenever someone is added, it flips a few switches on a shared panel. To check a name later, it looks at those same switches. If any switch is still off, that person was definitely never added. If all switches are on, that person was probably added, but that could be a coincidence, called a false positive. One thing it never does is wrongly say 'no' to someone who really was added.

How it works

  1. 1Start with a fixed-size row of switches, called bits. All start off, at 0.
  2. 2add(item): run the item through a few different hash functions. Each one points at one switch. Flip those switches on.
  3. 3mightContain(item): run the same hash functions again. If every switch is on, say 'probably yes.' If even one switch is off, say 'definitely no.'
  4. 4Nothing is ever removed or stored directly. Only the switches remember that anything happened.

When you'd use it

Use a Bloom filter to quickly rule out 'definitely not in the set,' before doing an expensive lookup. Examples: checking a username against millions of taken ones, or asking 'have we crawled this URL before?' Use it when a rare false positive is fine, but a false negative is not.

Common beginner mistakes

  • Don't treat 'might contain' as a guarantee. A Bloom filter can say yes for something never added, called a false positive. Always follow up with a real check when it matters.
  • Don't try to remove an item. A basic Bloom filter can't do this. Flipping a switch off could accidentally make a different, still-present item disappear too.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Might have apple: yes
Might have banana: yes
Might have kiwi: no
Bits set: 00100000011001100000

Note: Real-world Bloom filters use more hash functions and careful sizing, to keep false positives rare. This lesson uses just two simple hash functions, so you can trace the bit flips by hand.

See it in motion

Watch the bitsBloom filteradd and mightContain: O(k), where k is the number of hash functions. This is a small constant, so both are effectively instant. A Bloom filter also uses far less memory than storing every item.
Bit array (3 hashes per item)

Ready. Press play to add items, then query the filter.

0/18
Bits set
0/3
Items added
0
Queries
—
Verdict
Bit set / settingChecking (on)Off bit / false positiveEmpty bit

Not sure this is the right topic? See the learning paths → or where this leads →