Suppose you are building a web crawler and, for every URL you meet, you must answer one question : “have I seen this before ?”. Storing every URL in a hash set works, until the set grows to billions of entries and no longer fits in memory. What if you could answer that question using a few bits per item, accepting that you will occasionally be told “yes” when the true answer is “no”, but never the reverse ? This is exactly the bargain struck by the Bloom filter, a beautifully simple probabilistic data structure invented by Burton Bloom in 1970 (Bloom, 1970). In this post we build it from scratch, implement it in Python, and derive the mathematics that tells us how to size it.
1. What is a Bloom filter ?
A Bloom filter is a probabilistic data structure for approximate set membership. It supports two operations, insert(x) and contains(x), and it answers the second one with a deliberate asymmetry :
In plain words : it is a forgetful bouncer with a perfect memory for “no”. Ask it “is Alice on the guest list ?” and it either says “she might be, let me double-check” or “definitely not, turn her away”, and when it says no, it is never wrong.
That one-sided error is what buys the enormous space savings. A Bloom filter stores no keys at all, only a compact array of bits, and yet it can vouch, with a tunable and quantifiable error rate, that an element has never been inserted. When a definitive answer is occasionally required, the filter is used as a cheap first line of defence : only the queries it lets through need to touch the slow, exact store on disk.
2. How it works
The machinery has three ingredients : a bit array $B$ of $m$ bits (all initially $0$), and $k$ independent hash functions $h_{1}, \dots, h_{k}$, each mapping an element to one of the $m$ positions.
Insertion. To insert an element $x$, compute the $k$ positions $h_{1}(x), \dots, h_{k}(x)$ and set each of those bits to $1$. Bits are only ever turned on, never off.
Membership query. To test whether $x$ is present, compute the same $k$ positions and inspect the bits. If any of them is $0$, then $x$ was certainly never inserted, because insertion would have set all of them, this is the guaranteed no false negatives property. If all $k$ bits are $1$, the filter reports “possibly present” : the element may have been inserted, or those bits may simply have been set by a combination of other elements, a false positive.
3. A Python implementation
Real Bloom filters do not need $k$ genuinely independent hash functions. A classic result by Kirsch and Mitzenmacher (Kirsch & Mitzenmacher, 2008) shows that two hash functions are enough : the family $h_{i}(x) = h_{1}(x) + i \cdot h_{2}(x) \pmod{m}$ behaves, for our purposes, just like $k$ independent ones. We use Python’s hashlib to derive $h_{1}$ and $h_{2}$ from a single digest.
import hashlib
from math import log
class BloomFilter:
def __init__(self, m: int, k: int):
self.m = m # number of bits
self.k = k # number of hash functions
self.bits = bytearray((m + 7) // 8)
def _positions(self, item: str):
digest = hashlib.sha256(item.encode()).digest()
h1 = int.from_bytes(digest[:8], "big")
h2 = int.from_bytes(digest[8:16], "big")
for i in range(self.k):
yield (h1 + i * h2) % self.m # Kirsch-Mitzenmacher
def add(self, item: str):
for pos in self._positions(item):
self.bits[pos // 8] |= 1 << (pos % 8)
def __contains__(self, item: str) -> bool:
return all(
self.bits[pos // 8] & (1 << (pos % 8))
for pos in self._positions(item)
)
The usage mirrors the guarantee exactly, a negative answer is always trustworthy :
bf = BloomFilter(m=1000, k=7)
for word in ["apple", "banana", "cherry"]:
bf.add(word)
print("apple" in bf) # True (really inserted)
print("cow" in bf) # False (guaranteed correct)
print("grape" in bf) # False, or rarely True (a false positive)
4. The mathematics of false positives
The whole design hinges on one number : the probability that a query for an element we never inserted comes back positive. Let us derive it.
Assume the hash functions distribute elements uniformly and independently over the $m$ bits. When we insert a single element we set $k$ bits ; the probability that one specific bit is left untouched by one hash is $1 - \tfrac{1}{m}$. After inserting $n$ elements, each contributing $k$ hashes, the probability that a given bit is still $0$ is
\[\begin{equation} P(\text{bit} = 0) = \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m}, \label{eq:bitzero} \end{equation}\]using the standard limit $\left(1 - \tfrac{1}{m}\right)^{m} \to e^{-1}$. Consequently the probability that a given bit is $1$ is $\;1 - e^{-kn/m}$.
A false positive occurs when a non-inserted element hashes to $k$ positions that all happen to be $1$. Treating those $k$ bits as independent 1, the false-positive probability is
\[\begin{equation} \varepsilon \;\approx\; \left( 1 - e^{-kn/m} \right)^{k}. \label{eq:fp} \end{equation}\]This compact formula is the design equation of every Bloom filter. In plain words : the more elements you cram in (larger $n$) the more crowded with $1$s the array gets, so accidental all-ones collisions, false positives, become more likely ; give it more room (larger $m$) and they become rarer.
5. Choosing the parameters
Formula $\eqref{eq:fp}$ exposes a genuine trade-off in $k$. Too few hash functions and each query inspects too little evidence ; too many and the array saturates with $1$s, so almost everything looks present. There is a sweet spot, found by minimising $\varepsilon$ over $k$ for fixed $m$ and $n$ :
\[\begin{equation} k^{\ast} = \frac{m}{n}\,\ln 2 \;\approx\; 0.693\,\frac{m}{n}. \label{eq:koptimal} \end{equation}\]Substituting $k^{\ast}$ back into $\eqref{eq:fp}$ and rearranging gives the number of bits required to hit a target error rate $\varepsilon$ :
\[\begin{equation} m = -\,\frac{n \ln \varepsilon}{(\ln 2)^{2}}. \label{eq:msize} \end{equation}\]6. Variants and where they are used
The plain Bloom filter cannot delete elements (turning a bit off might erase evidence of some other element). This limitation spawned a family of refinements :
- Counting Bloom filters replace each bit by a small counter, so insertions increment and deletions decrement, restoring removal at the cost of more space (Fan et al., 2000).
- Scalable and partitioned Bloom filters grow gracefully when $n$ is not known in advance.
- Cuckoo filters achieve similar space efficiency while supporting deletion and often lower false-positive rates.
Bloom filters are quietly everywhere. Databases such as Cassandra, HBase and Google’s Bigtable use them to avoid disk reads for keys that are absent ; the same trick guards the LSM-tree lookups in RocksDB. Web browsers have used them for safe-browsing URL blacklists, content-delivery networks use them for cache filtering, and Bitcoin’s lightweight clients once used them to request relevant transactions without revealing exactly which addresses they cared about. Whenever “probably yes / definitely no” is good enough, a Bloom filter turns a memory problem into a handful of bits.
7. Conclusion
The Bloom filter is a small masterpiece of engineering trade-offs : by giving up the ability to store keys, and by tolerating a controlled, quantifiable rate of false positives, it answers set-membership queries in constant time and a fistful of bits per element. Its one-sided error, never a false negative, is what makes it trustworthy where it matters, and its design equations $\eqref{eq:fp}$–$\eqref{eq:msize}$ let us dial the error rate to whatever a system can afford. More than fifty years after Burton Bloom described it, it remains a first reflex for anyone who needs to check things without the luxury of remembering them.
References
- Bloom, B. H. (1970). Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM, 13(7), 422–426.
@article{Bloom1970, author = {Bloom, Burton H.}, title = {Space/Time Trade-offs in Hash Coding with Allowable Errors}, journal = {Communications of the ACM}, volume = {13}, number = {7}, pages = {422--426}, year = {1970}, publisher = {ACM} } - Fan, L., Cao, P., Almeida, J., & Broder, A. Z. (2000). Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol. IEEE/ACM Transactions on Networking, 8(3), 281–293.
@article{Fan2000, author = {Fan, Li and Cao, Pei and Almeida, Jussara and Broder, Andrei Z.}, title = {Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol}, journal = {IEEE/ACM Transactions on Networking}, volume = {8}, number = {3}, pages = {281--293}, year = {2000}, publisher = {IEEE} } - Kirsch, A., & Mitzenmacher, M. (2008). Less Hashing, Same Performance: Building a Better Bloom Filter. Random Structures & Algorithms, 33(2), 187–218.
@article{Kirsch2006, author = {Kirsch, Adam and Mitzenmacher, Michael}, title = {Less Hashing, Same Performance: Building a Better Bloom Filter}, journal = {Random Structures \& Algorithms}, volume = {33}, number = {2}, pages = {187--218}, year = {2008}, publisher = {Wiley} }
-
This independence assumption is a slight simplification, the events “bit $i$ is set” are weakly correlated, so $\eqref{eq:fp}$ is a very good approximation rather than an exact identity. Bose et al. derived the exact expression, which differs only negligibly for the array sizes used in practice. ↩