Sometimes we must answer "is the element there?" over a huge collection, and a set eats too much memory. A Bloom filter is a memory-efficient probabilistic structure. It gives only two answers: "definitely not" or "maybe yes". So false positives are possible, while false negatives never happen.

A bit array: `w6` gives a false positive, `cow` gives "definitely not"
A bit array: w6 gives a false positive, cow gives "definitely not"

The idea

  • An array of m bits, all 0 at first.
  • k different hash functions.
  • add(x): sets to 1 the k bits pointed to by the k hashes.
  • x in filter: looks at the same k bits; if all are 1 the answer is "maybe yes", if any is 0 it is "definitely not".

Bits only go 0 → 1, so an added element is always found (no false negatives). But other elements may have set the same bits to 1, so an element that was never added can also get "maybe yes".

Implementation

Instead of k separate hash functions we use two hashes: h1 + i * h2 (the Kirsch-Mitzenmacher trick). We take the hashes from hashlib.sha256 so they are deterministic (hash() changes between processes, see hash functions).

python
import hashlib
import math

class BloomFilter:
    def __init__(self, m, k):
        self.m = m
        self.k = k
        self.bits = bytearray((m + 7) // 8)