中文
devexamples

Bloom Filter for Membership Tests

Use a Bloom filter to rule out absent keys with no false negatives, trading a small false-positive rate for large memory savings.

PythonResilience

Code

snippet
import hashlib
from typing import Iterable


class BloomFilter:
    def __init__(self, size: int, hash_count: int) -> None:
        if size <= 0 or hash_count <= 0:
            raise ValueError("size and hash_count must be positive")
        self.size = size
        self.hash_count = hash_count
        self.bits = bytearray(size)

    def _positions(self, item: str) -> Iterable[int]:
        for index in range(self.hash_count):
            digest = hashlib.sha256(f"{index}:{item}".encode()).digest()
            yield int.from_bytes(digest[:4], "big") % self.size

    def add(self, item: str) -> None:
        for position in self._positions(item):
            self.bits[position] = 1

    def might_contain(self, item: str) -> bool:
        return all(self.bits[position] == 1 for position in self._positions(item))

Related Examples