"""
See https://en.wikipedia.org/wiki/Bloom_filter
The use of this data structure is to test membership in a set.
Compared to Python's built-in set() it is more space-efficient.
In the following example, only 8 bits of memory will be used:
>>> bloom = Bloom(size=8)
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.add("Titanic")
>>> bloom.bitstring
'01100000'
>>> "Titanic" in bloom
True
However, sometimes only one bit is added
because both hash functions return the same value
>>> bloom.add("Avatar")
>>> "Avatar" in bloom
True
>>> bloom.format_hash("Avatar")
'00000100'
>>> bloom.bitstring
'01100100'
Not added elements should return False ...
>>> not_present_films = ("The Godfather", "Interstellar", "Parasite", "Pulp Fiction")
>>> {
... film: bloom.format_hash(film) for film in not_present_films
... } # doctest: +NORMALIZE_WHITESPACE
{'The Godfather': '00000101',
'Interstellar': '00000011',
'Parasite': '00010010',
'Pulp Fiction': '10000100'}
>>> any(film in bloom for film in not_present_films)
False
but sometimes there are false positives:
>>> "Ratatouille" in bloom
True
>>> bloom.format_hash("Ratatouille")
'01100000'
The probability increases with the number of elements added.
The probability decreases with the number of bits in the bitarray.
>>> bloom.estimated_error_rate
0.140625
>>> bloom.add("The Godfather")
>>> bloom.estimated_error_rate
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)
Bloom Filters are one of a class of probabilistic data structures. The Bloom Filter uses hashes and probability to determine whether a particular item is present in a set. It can do so in constant time: O(1) and sub-linear space, though technically still O(n). An important feature of a Bloom Filter is that it is guaranteed never to provide a false negative, saying an element isn't present when it is. However, it has a probability (based on the tuning of its parameters) of providing a false positive, saying an element is present when it is not. The Bloom Filter uses a multi-hash scheme. On insertion, the inserted object is run through each hash, which produces a slot number. That slot number is flipped to 1 in the bit array. During a presence check, the object is run through the same set of hashes, and if each corresponding slot is 1, the filter reports the object has been added. If any of them are 0, it reports that the object has not been added. The hashes must be deterministic and uniformly distributed over the slots for the Bloom filter to operate effectively.
Operation | Average |
---|---|
Initialize | O(1) |
Insertion | O(1) |
Query | O(1) |
Space | O(n) |
k
), and with an array of bits of size M
with each bit set to 0. There are 3 distinct schemes to tune these parameters.
M
and k
are explicitly set by the userk
and M
are calculated based off the expected number of elements to minimize false positives.k
and M
are calculated based off a desired error rate.k
hashesn
determine the slot within the filter m
by calculating n % M = m
m
within the filter to 1k
hashesn
determine the slot within the filter m
by calculating n % M = m
m
, if m
is set to 0 return falseAs an example, let us look at a Bloom Filter of Strings, we will initialize the Bloom Filter with 10 slots an we will use 3 hashes
slot | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
state | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Let's try to insert foo
, we will run foo
through our three hash functions
h1(foo) = 2
h2(foo) = 5
h3(foo) = 6
With hashes run, we will flip the corresponding bits to 1
slot | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
state | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
Let's first try querying bar
, to query bar
we run bar
through our three hash functions:
h1(bar) = 3
h2(bar) = 4
h3(bar) = 6
If we look at our bit array, bits 3 and 4 are both not set, if even just 1 bit is not set, we return false, so in this case we return false. bar
has not been added
Let's now try to query foo
, when we run foo
through our hashes we get:
h1(foo) = 2
h2(foo) = 5
h3(foo) = 6
Of course, since we already inserted foo, our table has each of the three bits our hashes produced set to 1, so we return true, foo
is present
Let's say we inserted bar
and the current state of our table is:
slot | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|---|
state | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
Let's now query baz
, when we run baz through our hash functions we get:
h1(baz) = 3
h2(baz) = 5
h3(baz) = 6
Notice that this does not match either the result of foo
or bar
, however because slots 3, 5, and 6 are already set, we report true, that baz is in the set, and therefore produce a false positive.
The probability of false positives increases with the probability of hash collisions within the filter. However, you can optimize the number of collisions if you have some sense of the cardinality of your set ahead of time. You can do this by optimizing k
and M
, M
should be ~ 8-10 bits per expected item, and k
should be (M/n) * ln2
.