Skip to content
Tutorials Center
My learning

Topics

Lesson 57 of 225 ยท Hashing

Bloom Filters and Probabilistic Sets

Learn how Bloom filters answer set membership in tiny memory: bit arrays, k hash functions, false positives, the sizing formula, a Python implementation and count-min sketch.

A Python set answers "have I seen this?" perfectly, but it must store every item. Suppose you are building a web crawler that has visited two billion URLs, or a database that wants to skip a slow disk read when a key definitely does not exist. Storing every key would take gigabytes. What if you could accept a tiny, controllable chance of being wrong in exchange for using roughly 10 bits per item instead of the whole item?

That is the bargain of a Bloom filter, the best-known probabilistic data structure. It answers membership questions with two possible replies: "definitely not in the set" or "probably in the set". It never forgets an item you added (no false negatives), but it sometimes claims it has seen an item it has not (a false positive). In this lesson you will understand why, build one, size it with a formula, and meet its cousins, the counting Bloom filter and the count-min sketch.

How a Bloom filter works

A Bloom filter has two ingredients: a bit array of m bits (all zero at first) and k different hash functions, each mapping an item to a position in 0..m-1.

  • add(item): compute the k positions and set those bits to 1.
  • contains(item): compute the k positions. If any bit is 0, the item was definitely never added. If all are 1, it was probably added.
TEXT
m = 12 bits, k = 3 hash functions   (made-up positions for illustration)

start:        0 0 0 0 0 0 0 0 0 0 0 0

add "cat"  -> positions 1, 5, 9
              0 1 0 0 0 1 0 0 0 1 0 0

add "dog"  -> positions 2, 5, 10
              0 1 1 0 0 1 0 0 0 1 1 0

query "cow" -> positions 1, 2, 9 -> all 1 -> "probably yes"  (FALSE POSITIVE:
               other items set those bits)
query "pig" -> positions 3, 5, 9 -> bit 3 is 0 -> "definitely no"

Why there are never false negatives: adding an item sets its bits, and bits are never cleared, so the item's bits are still 1 later. Why false positives happen: different items can set the same bits, so a never-added item can find all its bits already set by others. The fuller the array, the likelier that is.

You cannot list the items, you cannot delete one (clearing a bit could erase other items' evidence), and you cannot read the items back. You only get the membership test.

Python A Bloom filter by hand

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Every word you added is reported present (that guarantee never breaks). Here the three unknown words are all reported absent because at least one of their bits is still 0. With more words added, some unknown words would be reported present, and each such "yes" is a false positive.

Getting k hash functions cheaply

You do not need k independent hash functions. A well-known result says two are enough: compute h1 and h2 once, then use

TEXT
position_i = (h1 + i ยท h2) mod m        for i = 0, 1, ..., k-1

This is double hashing again. Take both values from different halves of one hashlib digest, which keeps the output stable between runs (Python's built-in hash() of strings is randomized, see hash functions). Make h2 odd so that it cannot be zero.

The math: how often does it lie?

After adding n items to an m-bit filter with k hash functions, the probability that a never-added item is wrongly reported present is approximately

TEXT
p โ‰ˆ (1 - e^(-kยทn / m))^k

Intuition: each of the kยทn bit-setting operations hits a given bit with probability 1/m, so a given bit is still 0 with probability about e^(-kn/m). A false positive needs all k probed bits to be 1.

For a target false-positive rate p and n expected items, the best sizes are

TEXT
m = -n ยท ln(p) / (ln 2)ยฒ          bits
k = (m / n) ยท ln 2                hash functions

Memory per item depends only on p: roughly 4.8 bits per item for 10%, 9.6 bits for 1%, and 14.4 bits for 0.1%. That is true no matter how large the items are.

Python Sizing a Bloom filter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The last line shows what happens if you under-size the filter: 2 bits per item with 7 hash functions fills the array and the predicted false-positive rate climbs to about 0.81 (four out of five unknown items look present).

A full implementation

Now put it together as a class that sizes itself from n and p, stores bits compactly in a bytearray (8 bits per byte), and uses double hashing from one digest.

Python A BloomFilter class

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 2,000 items at a 1% target, the filter needs only about 2.4 kilobytes, and the measured false-positive count lands close to the 100 expected in 10,000 queries. Notice that about half the bits end up set: at the optimal k, a filter is half full when it reaches its design capacity.

Watch out: a Bloom filter degrades if you add far more items than you sized it for. Past its design capacity the fraction of 1 bits climbs and the false-positive rate rises quickly. Plan for the maximum number of items, or use a scalable variant that chains new filters.

Complexity

Operation Time Space
add O(k) none extra
might_contain O(k) none extra
whole filter O(m) bits, about 1.44 ยท logโ‚‚(1/p) bits per item

Since k is a small constant (usually 3 to 10), both operations behave like O(1), and the structure never grows with item size.

Where Bloom filters are used

  • Databases and storage engines keep one per file so that a read for a missing key skips the disk entirely.
  • Crawlers and caches check "have I already fetched this URL?" before touching a big store.
  • Spell checkers, password-breach checks and malware lists use them to keep a large blocklist small enough to ship.
  • Network routers and CDNs use them for fast "is this cached?" pre-checks.

The pattern is always the same: put a cheap Bloom filter in front of an expensive lookup. "Definitely no" answers are trusted and skip the expensive step; "probably yes" answers trigger the real lookup, which resolves the rare false positive.

Counting Bloom filters (supporting delete)

Replace each bit with a small counter. add increments the k counters, remove decrements them, and an item is possibly present if all its counters are above zero. Deletion now works, at the cost of more memory (typically 4 bits per counter) and the risk that removing an item you never added corrupts the counts.

Python A counting Bloom filter

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bloom filters are the first of a family of sketches: structures that summarize a huge stream in fixed memory, with a bounded error.

  • Count-min sketch answers "about how many times did I see this item?" It is a grid of counters with d rows, each row with its own hash function. Adding an item increments one cell per row; the estimated count is the minimum of its d cells. Collisions can only make counters bigger, so the estimate never undercounts, and taking the minimum picks the least-inflated cell.
  • HyperLogLog estimates how many distinct items a stream contained using a few kilobytes, by tracking the longest run of leading zero bits seen in the items' hashes (a rare long run suggests many distinct items). You will find it in databases as an approximate COUNT(DISTINCT ...).
Python A count-min sketch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The estimates are never below the exact counts. This sketch is deliberately tiny (12 columns, 3 rows), so crowding shows: the rare item seen once is estimated at 8 and the never-seen item at 5, because other items share its cells. The heavy hitters (50, 20) stay close. Increasing the width reduces the error, and increasing the depth makes a large error less likely.

Common mistakes

  • Expecting "no false positives". A "yes" only means "probably". Always verify with the real store when a wrong answer matters.
  • Trying to delete from a plain Bloom filter. Use a counting variant, or rebuild.
  • Under-sizing. Choose n as the maximum you will ever add, not the average.
  • Using Python's hash() for the filter and saving it to disk: string hashes change between runs, so the saved bits become meaningless. Use hashlib or another stable hash.
  • Using too many or too few hash functions. Use the formula; both extremes raise the false-positive rate.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. A Bloom filter answers 'definitely not in the set'. What can you conclude?

    Bits are never cleared, so an added item always has all its bits set. Finding a 0 bit proves the item was never added: Bloom filters have no false negatives.
  2. 2. What causes a Bloom filter false positive?

    Different items can set overlapping bits. If every one of a new item's k positions is already 1, the filter claims it has seen the item.
  3. 3. How does the memory a Bloom filter needs per item depend on the item's size?

    The filter stores only hash-derived bits. Bits per item is about 1.44 ยท log2(1/p), set by the false-positive rate.
  4. 4. A count-min sketch estimate for an item is never lower than its true count. Why?

    Each cell contains the item's own increments plus those of any colliding items, so every cell is at least the true count; the minimum is the least inflated of them.
  5. 5. Why is a plain Bloom filter unable to support delete?

    A bit may be shared by several items. Clearing it would create false negatives for the others, which breaks the filter's main guarantee.

Summary

  • A Bloom filter is an m-bit array plus k hash functions; it answers "definitely not" or "probably yes".
  • No false negatives; false positives occur at a rate about (1 - e^(-kn/m))^k.
  • Size it from the item count n and target rate p: m = -n ln p / (ln 2)ยฒ, k = (m/n) ln 2. About 10 bits per item gives a 1% error rate.
  • Use stable hashes (hashlib) and double hashing h1 + iยทh2 to get k positions from one digest.
  • Counting Bloom filters allow deletes; count-min sketches estimate frequencies and HyperLogLog estimates distinct counts, all in small fixed memory.

Next: Designing an LRU Cache