Bloom Filters

Bloom Filters

Arpit Bhayani<br>engineering, databases, and systems. always building.

A Bloom filter is a probabilistic data structure that answers a very specific question - have I seen this thing before? - while using almost no memory.

There is a trade-off, though - bloom filters can be ‘wrong’. A Bloom filter will never tell you something is absent when it is actually present, but it might occasionally claim something exists when it does not.

In this essay, we explore Bloom filters end-to-end, from fundamental concepts to advanced variants like counting and deletable Bloom filters, the nuances of hash functions, and real-world benchmarks and use-cases.

Why Bloom Filters Matter

Say, you are building a recommendation engine for a content platform with millions of users. Each user has seen thousands of articles. When generating recommendations, you need to filter out articles the user has already seen.

Storing every article ID for every user in a hash set would consume enormous amounts of memory. Let’s crunch the numbers…

Assumptions:

10 million active users

Each user has seen an average of 5,000 articles

Article IDs are 64-bit integers (8 bytes each)

Storing article IDs directly in a hash set:

Per user storage:<br>5,000 article IDs * 8 bytes = 40,000 bytes = 40 KB

Hash set overhead (typical 2x for load factor + pointers):<br>40 KB * 2 = 80 KB per user

Total for all users:<br>80 KB * 10,000,000 users = 800 GB<br>That is 800 GB of RAM just for tracking which articles users have seen. Even with a more optimistic 1.5x overhead factor, you are looking at 600 GB.

Bloom Filter will take up about ~60GB (one-tenth) of space by not storing actual article IDs, but rather storing the existence in a compact bit array that can answer the question:

has this user probably seen this article?

If the answer is no, you can confidently recommend it. If the answer is yes, you either skip it or do a more expensive lookup to confirm. In practice, this cuts memory usage by more than 90% without slowing down recommendation generation.

Variations of this idea show up in many large systems - Medium uses it in recommendations, Chrome uses it to flag unsafe URLs, and databases rely on Bloom filters to avoid unnecessary disk reads.

The Fundamental Structure

A Bloom filter consists of two components: a bit array of m bits, all initially set to zero, and a collection of k independent hash functions. Each hash function maps an arbitrary input to one of the m array positions.

To add an element to the filter:

def add(element):<br>for i in 1 to k:<br>position = hash_i(element) mod m<br>bit_array[position] = 1<br>To check if an element might exist in the filter:

def contains(element):<br>for i in 1 to k:<br>position = hash_i(element) mod m<br>if bit_array[position] == 0:<br>return false<br>return true<br>If any bit at the computed positions is zero, the element was definitely never added. Those positions would have been set to one during insertion. However, if all bits are one, the element might have been added, or those positions might have been set by other elements. This is the source of false positives.

Consider a concrete example. Suppose you have a 10 bit array and two hash functions. You insert the strings “apple” and “banana”:

hash1(“apple”) mod 10 = 2, hash2(“apple”) mod 10 = 5

hash1(“banana”) mod 10 = 3, hash2(“banana”) mod 10 = 7

After these insertions, bits 2, 3, 5, and 7 are set to one. Now you check for “cherry”:

hash1(“cherry”) mod 10 = 2, hash2(“cherry”) mod 10 = 3

Both positions are already one (set by previous insertions), so the filter incorrectly reports that “cherry” might be present. This is a false positive.

Mathematics of False Positives

After inserting n elements using k hash functions into a filter with m bits, the probability that a specific bit remains zero is:

p0 = (1 - 1/m)^(kn)<br>If you have m bits in your array and a hash function that outputs random positions, the probability of hitting any specific bit is 1/m. Hence, the probability of NOT hitting a specific bit with one hash is 1 - 1/m. The probability of that bit being zero with n insertions and each one setting k bits will be (1 - 1/m)^(kn).

For large m, this approximates to:

p0 ≈ e^(-kn/m)<br>The probability of a false positive is the probability that all k bits are set for a random element not in the set:

p_fp = (1 - e^(-kn/m))^k<br>Here’s an interesting and important trade-off. Increasing m (more bits) reduces false positives but uses more memory. Increasing k (more hash functions) can either help or hurt depending on the relationship between k and m/n.

The optimal number of hash functions that minimizes the false positive rate is (via simple differentiation):

k_optimal = (m/n) * ln(2) ≈ 0.693 * (m/n)<br>At this optimal k, the false positive rate becomes:

p_fp ≈ (0.6185)^(m/n)<br>Working backwards, if you want a specific false positive rate p, you need approximately:

m/n = -ln(p) / (ln(2))^2 ≈ -1.44 * ln(p)<br>For a 1% false positive rate, you need about 9.6...