DEV Community: zeyad daowd

Bloom Filters

zeyad daowd — Wed, 30 Sep 2026 20:53:18 +0000

TL;DR: Bloom filters (and friends) are a family of probabilistic data structures that answer the question "is this element in the set?" with no false negatives, a bounded false-positive rate, and a small memory footprint: about 14 bits per element at a 0.1% false-positive rate, no matter how long the elements are.

The problem

Let's say you are building an application with millions of users with unique usernames. You get a request with a username and want to check if it exists before allowing a response.

You could send a select query to the database, but that might not be reasonable if you don't want to overload it (and accessing disk is a bit slow).

What about storing the usernames in a hashset in memory (e.g. C++ unordered_set)? Now here comes the interesting part: hashsets use O(n) memory with a big constant. Storing 1 billion strings (don't ask me why you would have a billion users, just follow the example, it generalizes to other data) of 10-20 characters costs around 10 GB to 20 GB of memory, and that's ignoring the overhead of the data structure itself.

So the question is: can we do better on memory without sacrificing fast lookups?

The answer is yes, you can use a Bloom filter.

A Bloom filter answers this exact question with no false negatives (if it says the user doesn't exist, then they don't exist). If it says the user exists, there is a small probability that they actually don't, but we can accept that to save memory :D

How do they work?

A Bloom filter uses an array of m bits and k hash functions.

When an element is added, we hash it with each of the k hash functions and, for each result, set the bit at position hash % m to 1.

To look an element up, we do the same: hash it with each of the k hash functions and check that all k bits are 1. If they are, the element might be in the set. If any of them is 0, the element was definitely never added.

An example: say we have 3 hash functions and a 16-bit array, and we insert alice and bob. We run the 3 hash functions on each and set the corresponding bits (mod 16).

Now what if we want to query carol and dave? We run the same method and check the corresponding bits.

Carol has a bit that is 0, so she was definitely never added. All of dave's bits happen to be 1 (they were set by other names), so the filter says he might exist. That is exactly the false positive case Bloom filters can give you.

Sizing

Key formulas [1]:

p = desired false-positive rate
n = expected number of unique elements
Bit array size: m = -(n * ln(p)) / (ln(2)^2)
Number of hash functions: k = (m / n) * ln(2)
Actual false-positive rate: p = (1 - e^(-kn/m))^k

What about some numbers? For the same example with 1 billion elements and a 0.1% false-positive rate, we use n = 10^9 and p = 0.001. That gives m ≈ 14.4 * 10^9 bits, which is about 1.8 GB (~1.7 GiB), with k ≈ 10 hash functions.

Compared with 10 to 20 GB for the hashset, this looks pretty good. Notice that the length of the strings doesn't matter to a Bloom filter, only the number of strings does. If we doubled the username length, the Bloom filter would use the same memory, while the hashset's footprint would roughly double.

Pros and cons

Pros:

Small memory footprint (about 14 bits per element at 0.1%)
Constant-time lookups (k hash computations)
Zero false negatives
Supports parallel operations

Cons:

False positives
Parameter sensitivity and hash function dependence
You can't remove an item from the filter

Traditional Bloom filters don't support deletion. You can't just set the hashed bits back to zero, because those bits may be shared with other elements, so you would effectively delete more than one element.

Counting Bloom filters

...But what if, instead of setting a bit to 1, we used more than one bit per entry (we call it a counter) and incremented the counter at position hash % m?

Well, you just created a counting Bloom filter. Now you increment the counters when inserting an item, and you can decrement them to delete it.

Here is an example of inserting alice and bob and then deleting alice, with 4-bit counters (they can reach 15) instead of 1 bit per entry.

Keep in mind: if a counter reaches its maximum (1111 with 4 bits), it becomes saturated and we stop changing it, neither incrementing nor decrementing.

Why? Let's imagine a very naive scenario. We use a single hash function and 2-bit counters (max value 3), and the hash function for some reason maps alice, bob, carol and dave to the same counter. After adding the first three names, the counter is 3 (11 in binary). Adding dave would overflow it, so we can't let it wrap around to 0, and we leave it at 3.

Now what if we remove alice, bob and carol? If we decremented the counter each time, it would reach 0, and querying dave would say he doesn't exist. That's a false negative, and we hate those.

The deeper problem is that once the counter reads 3, the filter can't tell whether 3, 4 or 100 names landed there, so any decrement is a guess. Leaving saturated counters untouched is the only safe choice. The cost is that such a counter may stay non-zero even after every item using it is gone, which can only cause extra false positives, never false negatives. (With 4-bit counters and a properly sized filter, reaching 15 is rare.)

Scalable Bloom filters

Another issue: notice how we fixed the array size and the number of hash functions based on the expected input size (or an assumption of our maximum input size)? Let's say that after 1 billion usernames it turns out you still need more.

You can't simply grow the bit array, because hashes are taken modulo the array size, so every existing element would now map to different bits. And you can't rehash either, because the filter never stored the original elements.

Luckily there is a variant that fixes this: scalable Bloom filters.

We start with a normal Bloom filter. Once it is full, we stack another filter on top of it, usually a bigger one, while keeping the overall false-positive rate bounded. New elements are inserted into the newest (active) filter, and when querying we have to check every layer of the stack.

Note: it is still worth starting the first layer with a good estimate of the input size. A low initial guess means many layers, and every lookup has to run the hash functions of each layer, which hurts performance.

Where they're used

Databases like Apache Cassandra use Bloom filters on SSTables (Sorted String Tables) to avoid reading data files that can't contain the requested key.
The MyRocks storage engine in MariaDB uses Bloom filters to speed up point lookups (queries that ask for a single key).
CDNs (content delivery networks) like Akamai use Bloom filters to handle "one-hit wonders". They don't want to cache objects that are only requested once, so when an object is requested and isn't in the Bloom filter, it isn't cached and is added to the filter. If it's requested again, it's found in the filter and gets cached.

If you found this interesting, there are more variants worth a look, like Cuckoo filters and Ribbon filters.

References

[1] https://bloomy.hexdocs.pm/Bloomy.Params.html
[2] https://redis.io/blog/bloom-filter/
[3] https://www.geeksforgeeks.org/system-design/bloom-filters-in-system-design/
[4] https://grindengineer.substack.com/p/bloom-filters-how-databases-skip-millions-of-disk-reads
[5] https://medium.com/@suresh.sk1691/bloom-filter-0d3ad654536c
[6] https://www.geeksforgeeks.org/python/bloom-filters-introduction-and-python-implementation/
[7] https://corte.si/posts/code/bloom-filter-rules-of-thumb/
[8] https://mariadb.com/docs/server/server-usage/storage-engines/myrocks/myrocks-and-bloom-filters
[9] https://medium.com/@nitishmehta3/optimize-lookups-with-bloom-filters-fast-cheap-and-almost-honest-dbec172f720f
[10]https://cassandra.apache.org/doc/latest/cassandra/managing/operating/bloom_filters.html

Count-Min Sketch

zeyad daowd — Wed, 02 Sep 2026 15:18:06 +0000

TL;DR: Count-Min Sketch lets you estimate how many times something occurred in a massive stream, using a fixed-size matrix (~54KB) instead of a hashmap that could reach terabytes, with a small error that's bounded with high probability.

The Problem

Imagine the following leetcode-style problem:

You have a stream of visitors to a website, each visitor can visit your website multiple times. The target is relatively simple: you need to know how many times a specific person visited your website.

Looks easy - we can use a hashmap and increment the entry for the user by each visit. Lookups would be O(1), which is good, and you'd need O(n) memory, where n is the number of unique users - which looks good as well.

Where it breaks

Now imagine you are tracking post visibility for a social media application. We can just store a hashmap for each post - now the space complexity would be O(n * m), where m is the number of posts.

Imagine there are 1 million users and 1 million posts, and we want to keep an exact counter for every user/post pair. Even ignoring the storage required for the keys and the overhead of the hashmap itself, we'd need:

1 × 10^6 × 1 × 10^6 × 4 bytes = 4 × 10^12 bytes

That's more than 3.5 terabytes of memory.

Conclusion: hashmap storage explodes when trying to count over a lot of data. That's where Count-Min Sketch comes in.

Count-Min Sketch

Count-Min Sketch utilizes a fixed 2D matrix that doesn't grow with input size, with width W and depth D. The width and depth can be chosen by setting:

w = ⌈e/ε⌉
d = ⌈ln 1/δ⌉

e = 2.718 (Euler's constant)
δ = probability of failure
ε = error rate

Disclaimer: Count-Min Sketch is a probabilistic data structure - it doesn't provide the accurate answer (this was my first time hearing about probabilistic data structures). If you found that interesting take a look onto Hyperloglog and bloom filters

It guarantees the following:

The estimated frequency is never smaller than the true frequency.

With probability at least 1 - δ, the estimate is at most ε × N larger than the true frequency, where N is the total number of observations.

true count ≤ estimated count ≤ true count + ε * N (with probability ≥ 1 - δ)

Now that we have a depth × width matrix, we'll also have some hash functions (equal to depth).

For each input, we do the following:

for row in 0..d-1:
    column = hash_i(element) % width
    matrix[row][column] += 1

(Each row has its own independent hash function - hash_i refers to the hash function for row i.)

After some input entries, you might have the following matrix:

Looking up a frequency

If you want to get the frequency of element E1, you look at the hashed values:

Hash function	Hashed value % width	Matrix entry	Value
`hashFunction1(E1)`	1	`matrix[0][1]`	3
`hashFunction2(E1)`	6	`matrix[1][6]`	2
`hashFunction3(E1)`	3	`matrix[2][3]`	2
`hashFunction4(E1)`	1	`matrix[3][1]`	2

result = min(3, 2, 2, 2) = 2

To get the final frequency, you take the minimum of the values in the corresponding matrix entries: 2.

Why the minimum?

Every counter we look at contains the true count of E1 plus any counts added by other elements that happened to collide with it. Therefore, collisions can only make a counter larger, never smaller. Taking the minimum across the rows gives us the best estimate among the counters.

Why give up exact answers?

At first, giving up exact answers might sound like a bad idea. But imagine you're trying to find the top 100 most-viewed posts out of billions of events. You probably don't care whether a post was viewed 1,002,341 or 1,002,350 times - you care that you can identify the posts being viewed a lot, without storing a counter for every possible item.

That's where the tradeoff becomes useful: a tiny amount of error in exchange for much less memory.

Example calculation for high accuracy

For failure probability δ = 0.01 (confidence = 99%) and error rate ε = 0.001:

width ≈ 2,718
depth = 5
total matrix size = 5 × 2718 × 4 bytes = 54,360 bytes (< 54 KB)

The time complexity for retrieval is O(depth), which is a constant - so basically O(1) as well.

Where is this used in the industry?

Redis - Count-Min Sketch is implemented natively as part of Redis' core probabilistic data structures.
Network analysis - tracking IP addresses to detect DDoS attacks.
Heavy hitters - finding items that occur more than a threshold of the stream.

So, next time a counting problem mentions "billions of events," you know there's a structure for exactly that.