DSA Bloom Filters

A Bloom filter is a bit array that answers set membership with a small chance of a false yes. A no answer is always exact.

Setting bits for one item

Three hash positions are computed for one word. Those three bits are set to one.

import hashlib
def positions(word, m, k):
    out = []
    for i in range(k):
        digest = hashlib.md5((str(i) + ':' + word).encode()).hexdigest()
        out.append(int(digest, 16) % m)
    return out
print(positions('apple', 32, 3))

A zero bit proves absence

A word whose bits are not all set was never added. The check needs no stored words.

bits = [0] * 16
for p in [2, 5, 9]:
    bits[p] = 1
query = [2, 5, 11]
print('bits set for stored', [bits[p] for p in [2, 5, 9]])
print('query all set', all(bits[p] for p in query))

More bits lower the false rate

A larger array spreads the same items over more bits. Fewer collisions means fewer false yes answers.

print('items 20 in 32 bits load', 20 * 3 / 32)
print('items 20 in 256 bits load', 20 * 3 / 256)

Example

import hashlib

class Bloom:
    def __init__(self, m, k):
        self.m = m
        self.k = k
        self.bits = [0] * m
    def _pos(self, word):
        out = []
        for i in range(self.k):
            digest = hashlib.md5((str(i) + ':' + word).encode()).hexdigest()
            out.append(int(digest, 16) % self.m)
        return out
    def add(self, word):
        for p in self._pos(word):
            self.bits[p] = 1
    def might_have(self, word):
        return all(self.bits[p] for p in self._pos(word))

words = ['word' + str(i) for i in range(40)]
bf = Bloom(256, 3)
for w in words:
    bf.add(w)
misses = sum(1 for w in words if not bf.might_have(w))
print('stored words missed', misses)
probes = ['probe' + str(i) for i in range(200)]
false_yes = sum(1 for w in probes if bf.might_have(w))
print('probes', len(probes))
print('false positives', false_yes)
print('measured rate', false_yes / len(probes))

Key points

A false positive is a yes answer for an item never added
A false negative never happens in a Bloom filter
Each item sets k bits chosen by k hash functions
A query checks the same k bits for the item
One zero bit proves the item was never added

In this example, forty words are added to a filter of 256 bits. Every stored word is found again, so the miss count is zero. Two hundred fresh words are probed, and the false positives among them are counted. That counted share is the measured false-positive rate.

Note

The hashes here use hashlib, because the built-in hash changes per run

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

import hashlib

class Bloom:
    def __init__(self, m, k):
        self.m = m
        self.k = k
        self.bits = [0] * m
    def _pos(self, word):
        out = []
        for i in range(self.k):
            digest = hashlib.md5((str(i) + ':' + word).encode()).hexdigest()
            out.append(int(digest, 16) % self.m)
        return out
    def add(self, word):
        for p in self._pos(word):
            self.bits[p] = 1
    def might_have(self, word):
        return all(self.bits[p] for p in self._pos(word))

words = ['word' + str(i) for i in range(40)]
bf = Bloom(256, 3)
for w in words:
    bf.add(w)
misses = sum(1 for w in words if not bf.might_have(w))
print('stored words missed', misses)
probes = ['probe' + str(i) for i in range(200)]
false_yes = sum(1 for w in probes if bf.might_have(w))
print('probes', len(probes))
print('false positives', false_yes)
print('measured rate', false_yes / len(probes))

Exercise

A Bloom filter answers no for a word. What is certain?

The word might still be present The word was definitely never added The filter is full The hash functions collided