Bloom Filter

A set that fits in a few bits

Suppose a web browser must warn about millions of dangerous URLs. Storing every URL is too big. A Bloom filter stores only a short bit array and answers membership questions with two possible replies:

• “Definitely not in the set” (always correct)
• “Probably in the set” (right most of the time, sometimes a false positive)

How it works

You need an array of m bits (all 0) and k hash functions, each mapping a word to a position.

add(x):    for each hash function h:  bits[h(x)] ← 1
check(x):  for each hash function h:
               if bits[h(x)] == 0:  return "definitely not"
           return "probably yes"

Worked example

With m = 16 and k = 3, adding cat, dog and bird sets 7 distinct bits: 1, 3, 8, 9, 11, 14 and 15.

Sheep was caught by bits that cat, dog and bird had already set.

Why false negatives are impossible

Bits are never turned back to 0. A word that was added keeps all of its k bits set forever, so check finds them all 1.

Choosing m and k

With n items the false positive rate is about (1 − e^(−kn/m))^k. For m = 16, k = 3, n = 3 that is about 8%. The best k is roughly (m/n) · ln 2. In practice about 10 bits per item and k = 7 give a 1% error rate, far smaller than storing the items.

Where is it used?

• Databases (Cassandra, HBase, Chrome’s safe-browsing) skip a slow disk lookup when the filter says “definitely not”.
• Caches avoid storing items that were requested only once.
• Spell checkers and network routers check large sets cheaply. See also the hash table, which stores the real keys.

Code

class Bloom:
    def __init__(self, m=16, k=3):
        self.m, self.k, self.bits = m, k, [0] * m

    def _hashes(self, s):
        a, b = 5381, 2166136261
        for ch in s.encode():
            a = ((a * 33) ^ ch) & 0xFFFFFFFF
            b = ((b ^ ch) * 16777619) & 0xFFFFFFFF
        step = b % (self.m - 1) + 1
        return [(a + j * step) % self.m for j in range(self.k)]

    def add(self, s):
        for h in self._hashes(s):
            self.bits[h] = 1

    def check(self, s):
        return all(self.bits[h] for h in self._hashes(s))

Common mistakes

• Thinking “probably yes” means “yes”. Always confirm with the real data when a wrong answer matters.
• Trying to delete from a standard Bloom filter.
• Using a too small array for the number of items, which makes almost every check answer “probably yes”.