Bloom filters

Use cases

Bloom filters are a probabilistic data structure for set membership checks. Membership checks are O(1), and they use far less memory than a hash table for large datasets.

The tradeoff is accuracy: Bloom filters can return false positives, but they never return false negatives. In other words, if it says an item is not present, that answer is guaranteed.

Instead of storing full values, a Bloom filter stores bit positions produced by multiple hash functions. Common use cases include spell checkers, banned IP lists, cache admission checks, and malicious URL checks.

For example, storing 100,000 entries with a 0.1% (p = 0.001) false-positive rate needs about 1,437,759 bits (~175.5 KB). That is small enough to ship to clients for local checks and reduce server work.

The sizing equations are:

m = -(n * ln(p)) / (ln(2)^2)

k = (m / n) * ln(2)

where n is expected entries, p is desired false-positive rate, m is number of bits, and k is number of hash functions.

Realtime visualizations

The toy Bloom filter below uses 24 bits and 3 hash functions so you can watch the bitset change in realtime. Type a word to see which cells each hash touches, add it to the filter, then try membership checks to see why the answer is either “definitely not present” or “possibly present”.

Python example

Here is a simple Bloom filter implementation in Python.

import math
import bitarray
import mmh3


def calc_optimal_params(n_entries, false_positive_rate=0.001):
    m = (-n_entries * math.log(false_positive_rate)) / (math.log(2) ** 2)
    k = (m / n_entries) * math.log(2)
    return int(math.ceil(m)), int(math.ceil(k))


class BloomFilter:
    def __init__(self, n_entries, false_positive_rate=0.001):
        self.size, self.hash_count = calc_optimal_params(
            n_entries, false_positive_rate
        )
        self.bits = bitarray.bitarray(self.size)
        self.bits.setall(False)

    def add(self, item):
        for seed in range(self.hash_count):
            pos = mmh3.hash(item, seed) % self.size
            self.bits[pos] = True

    def contains(self, item):
        for seed in range(self.hash_count):
            pos = mmh3.hash(item, seed) % self.size
            if not self.bits[pos]:
                return False
        return True

def load_words(path='/usr/share/dict/words'):
    with open(path, 'r') as f:
        return [word.strip() for word in f]


if __name__ == '__main__':
    words = load_words()
    bloom = BloomFilter(n_entries=len(words), false_positive_rate=0.001)

    for word in words:
        bloom.add(word)

    tests = ['badwordforsure', 'cat', 'hello', 'jsalj']
    for t in tests:
        state = 'possibly present' if bloom.contains(t) else 'definitely not present'
        print(t, '->', state)