How a Bloom Filter Works

The entire filter state fits in a single Python integer initialized to zero. Inserting an element calls hash_ to produce a bitmask, then sets the corresponding bits with self.bitarray |= h. Querying an element checks whether all the bits in the element's bitmask are already set: (h & self.bitarray) == h is true only if every bit in h appears in self.bitarray. Because bits are never cleared, a positive result may come from earlier insertions of different elements, which is exactly the false-positive mechanism. Using a Python integer rather than a list of bits means the entire state is one memory object; Python's arbitrary-precision integers grow automatically as size increases without any allocation arithmetic from the caller.

The quality of a Bloom filter depends on its hash functions producing independent, uniformly distributed bit positions. This implementation uses SHA-256 and MD5, which are cryptographic digests and therefore highly independent. For each function, the 32-byte digest is interpreted as a little-endian integer and reduced modulo size to produce a position between 0 and size minus 1. The bit at that position is then set in the result integer using 2**position. Because SHA-256 and MD5 are independent functions, they map the same input to different positions most of the time. When they happen to collide, only one bit changes instead of two, which the Avatar doctest demonstrates explicitly: format_hash("Avatar") returns a mask with only one bit set even though the loop runs twice.

Python's bin() function returns a string like '0b110' for the integer 6. Slicing off the first two characters gives the raw binary digits, but that string only has as many characters as the highest set bit requires. For an 8-bit filter that is only half full, bin(6)[2:] returns '110', not '00000110'. The zfill(self.size) call pads the left side with zeros to the declared filter size, so the bitstring always shows all positions. This matters for the doctest, which asserts specific fixed-width strings like '01100000' that show exactly which of the eight positions are occupied. The bitstring property wraps this into a readable attribute so doctests and callers never work with raw integers.

The false-positive probability for a Bloom filter with k hash functions is approximately the fill fraction raised to the power of k. The property computes this directly: count the 1-bits in the current bitarray with Python's string count("1") method, divide by size to get the fill fraction, and raise it to len(HASH_FUNCTIONS). In the doctest, after adding Titanic and Avatar, 3 of 8 bits are set, giving (3/8) squared = 0.140625. After adding The Godfather, 4 bits are set, giving (4/8) squared = 0.25. The formula reveals the two design levers: increasing size lowers the fill fraction, and using more hash functions raises the exponent. Real-world implementations use the optimal sizing formula to choose the bit array length for a target false-positive rate before any elements are added.

The OR operation in add is the source of the filter's space efficiency and its deletion limitation in equal measure. When "Titanic" is added, bits 1 and 2 are set. When "Ratatouille" happens to hash to the same positions, those bits are already set. If you could remove "Titanic" by clearing its bits, you would simultaneously invalidate "Ratatouille" if it had been added. Since multiple elements share bit positions, a standard Bloom filter cannot tell which elements contributed to each bit: OR combines contributions from all of them without attribution. Counting Bloom filters solve this by replacing each bit with a small counter, incrementing on add and decrementing on delete, at the cost of roughly four times the space. The Redis BLOOM module supports both variants. This implementation is the space-minimal standard form.