Bloom Filter Explained with Python: Fast Membership Tests

By Engr. Henry Akpan

"Definitely Not" or "Probably Yes"

A sign-up page wants to say instantly whether a username is already taken, among 50 million users. A web browser wants to warn about dangerous websites without downloading a list of every bad URL. A database wants to avoid reading a disk block that cannot contain the key you asked for. All three need a very fast, very small way to test whether something is in a huge set. A Bloom filter does this using just a few bits per item. The trade-off: it can say "definitely not in the set" with certainty, but "in the set" only means "probably". This tutorial explains how a Bloom filter works, implements one in Python, measures its false positive rate, shows how to choose its size and number of hash functions, and covers its limitations and real uses. All outputs come from running the code.

How a Bloom Filter Works

A Bloom filter has two parts:

  • an array of m bits, all starting at 0;
  • k different hash functions, each mapping an item to a position from 0 to m − 1.

Adding an item: compute its k hash positions and set all those bits to 1.

Checking an item: compute its k positions. If any of those bits is 0, the item was definitely never added (adding it would have set that bit). If all k bits are 1, the item is probably in the set: either it was added, or other items happened to set all those bits between them, which is a false positive.

So a Bloom filter has no false negatives, but a small, controllable rate of false positives. It never stores the items themselves, only bits, which is why it is so compact.

A Bloom Filter in Python

We need k hash functions. A standard trick (double hashing) derives them all from two hash values h1 and h2: position i is (h1 + i × h2) mod m. We take h1 and h2 from a SHA-256 digest so the results are the same every time the program runs. (Python's built-in hash() for strings is randomised between runs, so it would give different bits each time.)

import hashlib
import math

class BloomFilter:
    def __init__(self, m, k):
        self.m, self.k = m, k
        self.bits = bytearray((m + 7) // 8)    # m bits packed into bytes
        self.count = 0

    def _positions(self, item):
        digest = hashlib.sha256(item.encode("utf-8")).digest()
        h1 = int.from_bytes(digest[:8], "big")
        h2 = int.from_bytes(digest[8:16], "big") | 1   # odd, so steps differ
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, item):
        for p in self._positions(item):
            self.bits[p // 8] |= 1 << (p % 8)
        self.count += 1

    def __contains__(self, item):
        return all(self.bits[p // 8] >> (p % 8) & 1 for p in self._positions(item))

bf = BloomFilter(m=1000, k=4)
for name in ["ada", "musa", "chidi", "fatima", "tunde"]:
    bf.add(name)

print("ada" in bf, "tunde" in bf)
print("zainab" in bf, "emeka" in bf)
print(len(bf.bits), "bytes for", bf.m, "bits")

Output:

True True
False False
125 bytes for 1000 bits

Every added name is found. Names never added are (almost always) reported absent. The whole filter is 125 bytes, no matter how long the names are.

Measuring the False Positive Rate

Let's fill a filter with 1,000 items and then test 10,000 items that were never added, counting how many are wrongly reported as present:

def false_positive_rate(m, k, n, trials=10_000):
    bf = BloomFilter(m, k)
    for i in range(n):
        bf.add(f"user{i}")
    hits = sum(f"stranger{j}" in bf for j in range(trials))
    return hits / trials

def predicted(m, k, n):
    return (1 - math.exp(-k * n / m)) ** k

for m, k in [(5000, 3), (10000, 7), (20000, 7)]:
    actual = false_positive_rate(m, k, 1000)
    print(f"m={m:5} k={k}: measured {actual:.3%}, predicted {predicted(m, k, 1000):.3%}")

Output:

m= 5000 k=3: measured 8.950%, predicted 9.185%
m=10000 k=7: measured 0.660%, predicted 0.819%
m=20000 k=7: measured 0.060%, predicted 0.020%

The measured rates are close to the theory. (The smallest rates are noisy: 0.06% is just 6 false positives out of 10,000 tests.) With 10 bits per item (m = 10,000 for 1,000 items) and 7 hash functions, fewer than 1 in 100 strangers are wrongly flagged. Doubling to 20 bits per item makes false positives rarer than 1 in 1,000.

Choosing m and k

For n items and a target false positive probability p, the standard formulas are:

  • number of bits: m = −n ln p / (ln 2)²
  • number of hash functions: k = (m/n) ln 2, rounded to a whole number
def design(n, p):
    m = math.ceil(-n * math.log(p) / math.log(2) ** 2)
    k = max(1, round(m / n * math.log(2)))
    return m, k

for p in [0.01, 0.001]:
    m, k = design(50_000_000, p)
    print(f"p={p}: m={m:,} bits ({m / 8 / 1024 / 1024:.1f} MB), k={k}, {m / 50_000_000:.1f} bits per item")

Output:

p=0.01: m=479,252,919 bits (57.1 MB), k=7, 9.6 bits per item
p=0.001: m=718,879,379 bits (85.7 MB), k=10, 14.4 bits per item

Fifty million usernames, averaging perhaps 12 characters each, would take hundreds of megabytes stored in a hash set. A Bloom filter does the "is it taken?" check with a 1% false positive rate in about 57 MB, and every extra 4.8 bits per item cuts the error rate tenfold. The size depends only on n and p, not on how long the items are.

Too few hash functions leave each item's bits easy to match by chance; too many fill the array with 1s too quickly. The best k makes about half the bits 1 when the filter is full.

Limitations of a Bloom Filter

  • False positives: a "yes" must be confirmed with a slower exact lookup (in a database, for example) when it matters. A "no" never needs checking.
  • No deletion: clearing an item's bits could clear bits shared with other items, creating false negatives. A counting Bloom filter stores small counters instead of bits to allow removal, and cuckoo filters support deletion too.
  • Fixed capacity: adding far more than n items makes the false positive rate rise sharply. Scalable Bloom filters add new layers as they fill.
  • No listing: you cannot retrieve the items from the filter, which can also be a privacy advantage.

Where Bloom Filters Are Used

  • Databases and storage engines such as Cassandra, HBase, RocksDB and LevelDB keep a Bloom filter per data file, so a lookup can skip files that definitely don't contain the key, saving disk reads.
  • Web caches and content delivery networks avoid caching "one-hit wonder" pages by only caching a URL on its second request, tracked with a Bloom filter.
  • Security: checking whether a password appears in a list of millions of leaked passwords, or whether a URL is on a blocklist, before doing a slower check.
  • Networking and blockchains: lightweight clients use Bloom filters to ask for only the transactions they might care about.

Summary

  • A Bloom filter is an m-bit array plus k hash functions; adding sets k bits, and checking tests whether all k are set.
  • It has no false negatives: "no" is certain, "yes" means probably.
  • The false positive rate is about (1 − e^(−kn/m))ᵏ; about 10 bits per item with k = 7 gives roughly 1%.
  • Choose m = −n ln p / (ln 2)² and k = (m/n) ln 2.
  • Standard Bloom filters cannot delete items or list them, and their accuracy drops if overfilled.

Related Tutorials