see https en wikipedia orgwikibloomfilter the use of this data structure is to test membership in a set compared to python s builtin set it is more spaceefficient in the following example only 8 bits of memory will be used bloom bloomsize8 initially the filter contains all zeros bloom bitstring 00000000 when an element is added two bits are set to 1 since there are 2 hash functions in this implementation titanic in bloom false bloom addtitanic bloom bitstring 01100000 titanic in bloom true however sometimes only one bit is added because both hash functions return the same value bloom addavatar avatar in bloom true bloom formathashavatar 00000100 bloom bitstring 01100100 not added elements should return false notpresentfilms the godfather interstellar parasite pulp fiction film bloom formathashfilm for film in notpresentfilms doctest normalizewhitespace the godfather 00000101 interstellar 00000011 parasite 00010010 pulp fiction 10000100 anyfilm in bloom for film in notpresentfilms false but sometimes there are false positives ratatouille in bloom true bloom formathashratatouille 01100000 the probability increases with the number of elements added the probability decreases with the number of bits in the bitarray bloom estimatederrorrate 0 140625 bloom addthe godfather bloom estimatederrorrate 0 25 bloom bitstring 01100101
from hashlib import md5, sha256

HASH_FUNCTIONS = (sha256, md5)


class Bloom:
    def __init__(self, size: int = 8) -> None:
        self.bitarray = 0b0
        self.size = size

    def add(self, value: str) -> None:
        h = self.hash_(value)
        self.bitarray |= h

    def exists(self, value: str) -> bool:
        h = self.hash_(value)
        return (h & self.bitarray) == h

    def __contains__(self, other: str) -> bool:
        return self.exists(other)

    def format_bin(self, bitarray: int) -> str:
        res = bin(bitarray)[2:]
        return res.zfill(self.size)

    @property
    def bitstring(self) -> str:
        return self.format_bin(self.bitarray)

    def hash_(self, value: str) -> int:
        res = 0b0
        for func in HASH_FUNCTIONS:
            position = (
                int.from_bytes(func(value.encode()).digest(), "little") % self.size
            )
            res |= 2**position
        return res

    def format_hash(self, value: str) -> str:
        return self.format_bin(self.hash_(value))

    @property
    def estimated_error_rate(self) -> float:
        n_ones = bin(self.bitarray).count("1")
        return (n_ones / self.size) ** len(HASH_FUNCTIONS)