learning-it by example

#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.

1. What does a Bloom filter answer when asked about a key, and which kind of wrong answer can it never give?
2. A Bloom filter has 10,000 bits and 7 hashes and was planned for 1,000 keys. After 1,000 made-up keys were added in a Python Bloom filter experiment, what was measured?
3. A Bloom filter with 10,000 bits and 7 hashes was planned for 1,000 keys. What happened to its false positive rate when it was filled with 3,000 made-up keys, three times its plan?
4. In a Python Bloom filter built with hashlib, how does the code get k bit positions for each key?
5. Why can a plain Bloom filter not delete a key?

Practice only: nothing is saved and no score counts towards anything. Each answer comes with the reason.

  1. 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.

  2. 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.

  3. 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.

  4. 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

All How it works, by example videos

Related videos