learning-it by example

Back to the video

Bloom Filters Explained: Build One and Measure Errors

A 10,000 bit Bloom filter gave 0.9% false positives, then 41.6% once I overfilled it.

Video #275 ยท How it works, by example

Steps in the video

  1. 0:00 Zero misses, and 0.9% false positives from 10,000 bits
  2. 0:38 The idea
  3. 1:08 Setup
  4. 1:26 k bit positions per key
  5. 1:58 Add and ask
  6. 2:19 The textbook estimate
  7. 2:53 The experiment
  8. 3:59 How real systems size it
  9. 4:31 What this does not show
  10. 5:02 Mistakes to avoid
  11. 5:32 My take and next steps
  12. 5:55 Recap

Files

  • bloom.py (29 lines)
  • keys.py (15 lines)
  • run.py (19 lines)

Download the code (zip)

Tested with

Python 3.12.15

What this does not show

Keys are made up; rates come from one sample of 10,000 keys, using salted SHA-256 rather than ideal hashes.

Sources

Learning IT by Example.