#275 How it works, by example 6.5 min
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.
Run the filter
Copy the code folder first. Run python run.py and read the table. Predict whether any added key was missed, then check the missed column. Notice how the bits set column grows as the filter is overfilled.
A hint
A key that was added always has all of its bits set.
Try three hashes
In run.py, change K_HASHES from 7 to 3 in the line that sets M_BITS, K_HASHES and PLANNED. Predict whether the rate at 1,000 keys goes up or down, and at 3,000 keys, then run python run.py. When I ran it, 1,000 keys gave 1.71% (worse than 0.90%), but 3,000 keys gave 20.94% (better than 41.55%). Change K_HASHES back to 7 afterwards, because the next exercise starts from the original file.
A hint
Fewer hashes set fewer bits per key, so the filter fills more slowly.
Give it three times the bits
In run.py, change M_BITS from 10_000 to 30_000, with K_HASHES set back to 7 if you changed it. Predict the false positive rate at 3,000 keys, then run python run.py. When I ran it, the rate at 1,000 keys was 0.00% and at 3,000 keys 0.94%, with 50% of bits set. Change M_BITS back to 10_000 afterwards.
A hint
3,000 keys in 30,000 bits is again 10 bits per key.
Use a single hash
In run.py, check that M_BITS is back at 10_000, then change K_HASHES to 1 and run python run.py. Predict whether the rate at 1,000 keys is better or worse than with 7 hashes. When I ran it, the rate at 1,000 keys was 9.12%, the formula said 9.52%, and nothing was missed.
A hint
With one hash, a false positive needs only one bit to be set by chance.
These tasks are for you to try on your own machine. Nothing is checked or saved.
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.
Up next in How it works, by example
More in How it works, by example
Related videos
- #274 How File Compression Works: Huffman Coding in 40 Lines How it works, by example
- #01 Local AI Agent in Python: No API Key (Ollama) AI agents and MCP
- #02 RAG From Scratch in Python: Chunk, Embed, Retrieve (Local) RAG and vector search
- #03 pgvector vs Chroma vs Qdrant: Same Data, Real Results RAG and vector search
