Skip to content
Optimal Lab

System Design · interactive

Bloom filters

A Bloom filter answers “have I seen this?” using a few bits per item instead of storing the items. It can say “no” for sure, and “probably yes” with a small chance of being wrong. 24 bits, 3 hash functions.

24 bits · 13 set

  1. 10
  2. 11
  3. 02
  4. 03
  5. 14
  6. 05
  7. 06
  8. 17
  9. 18
  10. 09
  11. 110
  12. 011
  13. 012
  14. 013
  15. 114
  16. 115
  17. 016
  18. 117
  19. 118
  20. 019
  21. 120
  22. 121
  23. 022
  24. 123
  • alice → 20, 7, 10
  • bob → 15, 4, 21
  • carol → 17, 18, 23
  • dave → 14, 15, 8
  • erin → 0, 1, 14

check("zoe") → bits 14, 9, 0: 1, 0, 1

Definitely not added

Definitely not added

Check a name

Names added

Expected false-positive rate with 5: 10.0%

  1. 1

  2. 2

    Hash the item the same way and look at those bits.

    bits 14, 9, 0

  3. 3

  4. 4

In production

Tools and technologies

Bloom filters sit in front of slow lookups in databases, caches and browsers.

Not tied to one language — use these names when you search docs or design a system.