Bloom filter in Python
Bit array with k hash functions giving a space-efficient approximate set with no deletions.
- File
bloom_filter.py, 69 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bloom-filter/. The authors are listed in prov/3RBEYS.jsonl.
"""Bloom filter (Bloom 1970): an approximate set with no false negatives."""
import hashlib
Key = str | bytes | int
class BloomFilter:
"""A bit array of m bits with k hash functions.
insert and query take O(k) time. A query for an inserted key always
returns True. A query for another key returns True with probability
about (1 - exp(-k n / m))^k after n inserts. Keys are str, bytes or int;
the hash functions are derived from BLAKE2b with the given seed, so the
filter is the same in each run.
"""
def __init__(self, m: int, k: int, seed: int = 0) -> None:
if m < 1 or k < 1:
raise ValueError("m and k must be positive")
self.m = m
self.k = k
self.seed = seed
self.bits = bytearray((m + 7) // 8) # @line L1: m bits, all 0
self.count = 0 # number of insert calls, for the user
def _positions(self, key: Key) -> list[int]:
"""The k positions h_1(key), ..., h_k(key) in [0, m).
Double hashing (Kirsch and Mitzenmacher): g_i = h1 + i * h2 mod m.
"""
d = hashlib.blake2b(
repr(key).encode(), digest_size=16, key=self.seed.to_bytes(8, "little")
).digest()
h1 = int.from_bytes(d[:8], "little")
h2 = int.from_bytes(d[8:], "little") | 1 # odd, so it is not 0
return [(h1 + i * h2) % self.m for i in range(self.k)] # @line L2
def _get(self, i: int) -> bool:
return (self.bits[i >> 3] >> (i & 7)) & 1 == 1
def insert(self, key: Key) -> None:
"""Add key to the set. Bits only change from 0 to 1."""
for p in self._positions(key): # @line L3
self.bits[p >> 3] |= 1 << (p & 7) # @line L4
self.count += 1
def query(self, key: Key) -> bool:
"""False if key was surely never inserted; True if it may have been."""
for p in self._positions(key): # @line L5
if not self._get(p): # @line L6
return False
return True # @line L7
def ones(self) -> int:
"""The number of bits that are 1."""
return sum(bin(b).count("1") for b in self.bits)
def union(self, other: "BloomFilter") -> "BloomFilter":
"""The filter of the union of the two sets. Same m, k and seed needed."""
if (self.m, self.k, self.seed) != (other.m, other.k, other.seed):
raise ValueError("the filters must have the same m, k and seed")
out = BloomFilter(self.m, self.k, self.seed)
out.bits = bytearray(a | b for a, b in zip(self.bits, other.bits))
out.count = self.count + other.count
return out
test_bloom_filter.py 101 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/bloom-filter/. The authors are listed in prov/3RBEYS.jsonl.
import math
import random
import pytest
from bloom_filter import BloomFilter, Key
class FixedBloom(BloomFilter):
"""A filter whose positions come from a table, as in the example of the page."""
def __init__(self, table: dict[Key, list[int]]) -> None:
super().__init__(16, 3)
self.table = table
def _positions(self, key: Key) -> list[int]:
return self.table[key]
def test_example() -> None:
table: dict[Key, list[int]] = {
"cat": [1, 6, 11],
"dog": [4, 6, 13],
"owl": [2, 9, 13],
"fox": [3, 9, 11],
"emu": [2, 4, 11],
}
f = FixedBloom(table)
f.insert("cat")
assert f.ones() == 3
f.insert("dog")
assert f.ones() == 5
f.insert("owl")
assert f.ones() == 7
assert [i for i in range(16) if f._get(i)] == [1, 2, 4, 6, 9, 11, 13]
assert f.query("cat") and f.query("dog") and f.query("owl")
assert not f.query("fox")
assert f.query("emu") # a false positive
def test_edges() -> None:
f = BloomFilter(1, 1)
assert not f.query("a")
f.insert("a")
assert f.query("a") and f.query("b") # one bit: everything is a false positive now
g = BloomFilter(64, 4, seed=3)
assert not any(g.query(x) for x in range(100))
g.insert(b"x")
g.insert("x")
g.insert(0)
assert g.query(b"x") and g.query("x") and g.query(0)
with pytest.raises(ValueError):
BloomFilter(0, 1)
with pytest.raises(ValueError):
BloomFilter(8, 0)
def test_no_false_negatives_random() -> None:
rng = random.Random(1970)
for _ in range(500):
m = rng.randint(1, 200)
k = rng.randint(1, 6)
f = BloomFilter(m, k, seed=rng.randrange(1000))
inserted: set[int] = set()
for _ in range(rng.randint(0, 40)):
x = rng.randrange(1000)
if rng.random() < 0.5:
f.insert(x)
inserted.add(x)
else:
# an inserted key is always found; others may or may not be
assert f.query(x) or x not in inserted
assert all(f.query(x) for x in inserted)
assert f.ones() <= min(m, k * len(inserted))
def test_union() -> None:
a, b = BloomFilter(500, 3, seed=7), BloomFilter(500, 3, seed=7)
both = BloomFilter(500, 3, seed=7)
for x in range(40):
(a if x % 2 else b).insert(x)
both.insert(x)
assert a.union(b).bits == both.bits
with pytest.raises(ValueError):
a.union(BloomFilter(500, 3, seed=8))
def test_false_positive_rate() -> None:
m, n, k = 10_000, 1_000, 7
f = BloomFilter(m, k, seed=11)
for x in range(n):
f.insert(x)
trials = 50_000
fp = sum(f.query(x) for x in range(n, n + trials)) / trials
exact_given_bits = (f.ones() / m) ** k
expected = (1 - math.exp(-k * n / m)) ** k
assert abs(fp - exact_given_bits) < 0.003
assert abs(fp - expected) < 0.003
What the next level needs
- the tests did not run in this build