Explain how a Bloom filter works and what errors it can make.

It is an array of m bits and k hash functions. To add an item, set the k bits its hashes point to. To query, check those k bits: if any is 0 the item is definitely absent, and if all are 1 it is probably present. It never gives a false negative, but it can give a false positive, and the chance grows as more bits are set. Add and query are O(k) and space is O(m), independent of the number of items.

You expect 10 million items and can accept a 1% false-positive rate. Roughly how much memory does a Bloom filter need?

About 9.6 bits per item for a 1% rate, so roughly 96 million bits, which is about 12 megabytes, with around 7 hash functions. The formula is m = -n ln(p) / (ln 2)² and k = (m / n) ln 2. A hash set of the same 10 million items would take far more memory, because it stores the items themselves.

Find the most frequent items in a stream too large to keep in memory.

Use a Count-Min sketch with d rows and w columns. Each item adds 1 to one counter per row, and its estimate is the minimum of its d counters, which is never below the true count. Keep a small min-heap of the current top k items by estimate. Updates are O(d + log k) and memory is O(d × w + k), fixed regardless of the stream length. The error is controlled by w (accuracy) and d (confidence).

How do you size a Count-Min sketch for a given error and confidence?

Choose the error eps as a fraction of the total count N and the failure probability delta. Use width w = ceil(e / eps) and depth d = ceil(ln(1 / delta)). With probability at least 1 - delta, the estimate is at most the true count plus eps × N, and it is never below the true count.

When should you not use a Bloom filter?

When the set is small enough to hold exactly, when you need deletes or to list the items, or when a false positive is expensive and cannot be double-checked. Use a hash set in those cases. A Bloom filter is also a poor fit if you cannot estimate the number of items in advance, because an overfull filter gives many false positives.

Probabilistic Data Structures

intermediate · 30 min · Last reviewed 31 Oct 2026 · by TheLearningLoop Team

Key takeaways

A Bloom filter answers 'definitely not' or 'probably yes'. It has false positives but never false negatives, and it cannot delete.
A Count-Min sketch estimates how often an item appeared. Estimates are never below the truth, and the smallest of the d counters is the least inflated.
Both use fixed memory, however much data arrives. A larger table means a smaller error, and sizing comes from the error rate you accept.

New to this topic? Read the overview first: Data Structures & Algorithms: The Big Picture

When to use a probabilistic data structure

Use a Bloom filter when you need to:

Ask "have I possibly seen this before?" for billions of items, in a few bits per item, and a wrong "yes" now and then is acceptable but a wrong "no" is not.
Avoid an expensive lookup most of the time, such as a disk read or a database query for a key that does not exist.

Use a Count-Min sketch when you need to:

Count how often each item appears in a huge or endless stream with fixed memory, and an estimate that is never too low is good enough.
Find the heavy hitters, the few items that appear most often, such as trending hashtags or the busiest IP addresses.

Use something else when:

You need exact answers or the set is small: use a hash set or hash map.
You must delete items: a plain Bloom filter cannot (use a counting Bloom filter or a cuckoo filter).
You need to count distinct items, not membership or frequency: use HyperLogLog.
A wrong answer is costly and cannot be double-checked: use an exact structure.

Do not write your own in production. Use your database's or library's version (see the real-world section). Building a small one by hand is for learning and interviews.

How probabilistic data structures work

Exact structures store every item, so memory grows with the data. Probabilistic structures store a compact summary and accept a small, controlled error in return. They are always built from hashing: a hash function turns any item into a position, and several hash functions spread an item over several positions.

Think of a stamp card at a cafe where nobody writes names. Each visitor presses stamps on a few spots chosen by their name. If one of your spots is still blank, you were definitely never here. If all your spots are stamped, you were probably here, but other people's stamps may have covered them.

Teaching simplification: the code samples make k hash functions from one function plus a seed. Real libraries usually compute two good hashes and combine them (double hashing), which behaves much like k independent hashes.

Bloom filter rule: a "no" is always correct, and a "yes" means "probably". It has false positives but never false negatives.

A Bloom filter is a row of m bits, all 0. To add an item, run it through k hash functions and set the k bits they point to. To ask, check the same k bits: if any is 0, the item was definitely never added. If all are 1, it was probably added, because other items may have set those same bits.
A Count-Min sketch is a small table of counters with d rows and w columns, one hash function per row. To count an item, add 1 to one counter in each row. To estimate it, read its d counters and take the smallest. Other items sharing a counter can only add to it, so the estimate is never below the truth and the minimum is the least inflated.

Both can give a wrong answer, but in one known direction and with a probability you control by choosing the size.

A worked dry run

Take a 16-bit Bloom filter with k = 3 (the same hash used by the simulation). Add cat: its hashes point at bits 2, 10 and 13, so those become 1. Add dog: bits 4, 12 and 15 become 1. Now ask about zebra: its hashes point at bits 3, 10 and 12. Bits 10 and 12 are 1 (set by cat and dog), but bit 3 is 0, so the answer is definitely not. Ask about dog: bits 4, 12 and 15 are all 1, so the answer is probably yes, and here that is true. A false positive would need a never-added word whose three bits were all set by other words, which becomes likely as the filter fills.

Try it

Pick a structure and a size, then step through. Watch the false positives or the over-count.

Probabilistic Data Structures

Step 1 of 18 · Press Space to play, arrow keys to step

StructureSize

Bit array (16 bits, 3 hash functions)

Initial state. A Bloom filter is 16 bits, all 0. To add a word, set 3 bits chosen by 3 hash functions. It stores no words at all.

step:: 0
bits set:: 0
false positives:: 0

Speed

Things to try:

Run the Bloom filter with Roomy (64 bits, 3 words added). Words that were never added come back "definitely not". Then run Crowded (16 bits, 8 words added). More bits are set, so more never-added words are wrongly reported as "probably in the set".
Run the Count-Min sketch with Roomy (32 counters per row). Estimates are exact or nearly so. Switch to Crowded (4 counters per row) and the total over-count rises, but no estimate is ever below the true count.
In both, look at the counter row: the structure never stores the items themselves.

Probabilistic structure operations: add, query and size it

Bloom filter add. Compute k positions and set those bits to 1. Cost O(k).

Bloom filter query. Compute the same k positions. If any bit is 0, answer "definitely not". If all are 1, answer "probably yes". Cost O(k).

Count-Min add. For each of the d rows, add 1 to the counter at that row's hash position. Cost O(d).

Count-Min estimate. Read the counter in each row and return the minimum. Cost O(d).

Sizing a Bloom filter. For n items and a target false-positive rate p, the number of bits is about m = -n × ln(p) / (ln 2)², which is roughly 9.6 bits per item for 1% and 14.4 bits per item for 0.1%. The best number of hash functions is k = (m / n) × ln 2, about 7 for 1%. A bigger filter gives fewer false positives. With n items added, the false-positive rate is about (1 - e^(-kn/m))^k.

Sizing a Count-Min sketch. To keep the over-count within eps × N (where N is the total number of items seen) with probability at least 1 - delta, use width w = ceil(e / eps) and depth d = ceil(ln(1 / delta)). For example, eps = 0.001 and delta = 0.01 need 2,719 columns and 5 rows, which is 13,595 counters regardless of the stream length.

A Bloom filter has no false negatives, but it has false positives, and a Count-Min sketch never under-counts. This is the interview fact: both errors only go one way.

Edge cases. An empty Bloom filter answers "definitely not" to everything. A filter filled past its planned n has most bits set and answers "probably" to almost everything, so plan n in advance. Count-Min counters are fixed-size integers in real systems and can overflow on very long streams. An item never added gets an estimate of 0 only when at least one of its counters was never touched by other items.

Probabilistic structure time complexity

Structure	Add	Query	Space	Error
Bloom filter	O(k)	O(k)	O(m) bits	False positives only
Counting Bloom filter	O(k)	O(k)	O(m) counters	False positives, supports delete
Count-Min sketch	O(d)	O(d)	O(d × w) counters	Over-counts only
HyperLogLog (distinct count)	O(1)	O(1)	A few kilobytes	About 1% error on the count
Hash set (exact)	O(1) average	O(1) average	O(n) items	None

k is the number of hash functions, m the number of bits, d the number of rows and w the width of each. These costs do not depend on n, which is the point: the structure stays the same size as the stream grows.

Probabilistic structures vs exact structures

Job	Bloom filter	Count-Min sketch	HyperLogLog	Hash set / map
"Is X in the set?"	Yes, with false positives	No	No	Exact
"How many times did X occur?"	No	Over-estimate	No	Exact
"How many different items?"	No	No	About 1% error	Exact but large
Memory for a billion items	About a gigabyte (1%)	Fixed, you choose	A few kilobytes	Tens of gigabytes
Can delete an item	No	Only by subtracting an item you know was added; otherwise estimates can be wrong	No	Yes
Answer can be wrong	Yes ("yes" only)	Yes (too high only)	Yes (slightly either way)	Never

n is the number of items. These structures win when memory is the limit and a small, one-sided error is acceptable. They never replace an exact structure when every answer must be right.

How to explain probabilistic structures in an interview

Say the trade first: "I trade a small, one-sided error for a large saving in memory." Then say which side: Bloom filters give false positives only, Count-Min sketches over-count only.
Describe a Bloom filter in one breath: "a bit array and k hashes; set k bits to add; if all k bits are set, the answer is 'maybe'". Mention that you can compute the size from the false-positive rate you want.
Give a use that shows why it helps: "check a Bloom filter before reading the disk, so most misses never touch the disk."
Name what they cannot do: delete (for plain Bloom), enumerate the items, or give exact counts. Offer the exact alternative when the data is small.

Where you meet probabilistic structures in real systems

They are used wherever data is too big to keep exactly and a small, one-sided error is fine. Here are three of them drawn out, the first with code you can run, then more examples.

Example 1: Skipping disk reads for keys that do not exist

A database stores its data in many files on disk. To read a key, it would normally have to look in each file. If every file keeps a small Bloom filter of its keys in memory, a lookup asks the filter first. A "definitely not" answer skips the file with no disk read. An occasional "probably" costs one wasted read. Open the example below to see the picture and the code.

Code: a Bloom filter and a Count-Min sketchTime O(k) and O(d)Memory O(m) and O(d × w)

The filter answers from memory. A definite no skips the disk. A probable yes reads the disk, which finds the key or finds nothing (a false positive that cost one read).

# A Bloom filter (is it in the set?) and a Count-Min sketch (how many times?).
# Both use k simple hash functions made from one function plus a seed.
# Bloom: time O(k) per add or query, memory O(m) bits, no false negatives, some false positives.
# Count-Min: time O(d) per add or query, memory O(d * w) counters, estimates are never too low.

def slot(word, seed, size):
    h = 5381 + seed * 7919
    for b in word.encode():
        h = (h * 33 + b) % 1000003
    return h % size

class Bloom:
    def __init__(self, m, k):
        self.bits, self.k = [False] * m, k

    def add(self, word):
        for i in range(self.k):
            self.bits[slot(word, i, len(self.bits))] = True

    def might_contain(self, word):      # False means "definitely not". True means "probably".
        return all(self.bits[slot(word, i, len(self.bits))] for i in range(self.k))

class CountMin:
    def __init__(self, width, depth):
        self.rows = [[0] * width for _ in range(depth)]

    def add(self, word):
        for i, row in enumerate(self.rows):
            row[slot(word, i, len(row))] += 1

    def count(self, word):              # the smallest counter is the least inflated by collisions
        return min(row[slot(word, i, len(row))] for i, row in enumerate(self.rows))

bloom = Bloom(64, 3)
for w in ["cat", "dog", "fox"]:
    bloom.add(w)
print("dog:", "maybe" if bloom.might_contain("dog") else "no")
print("zebra:", "maybe" if bloom.might_contain("zebra") else "no")

cm = CountMin(32, 3)
for w in "a b a c a b d a e c a f g h".split():
    cm.add(w)
print("count a:", cm.count("a"))
print("count b:", cm.count("b"))
print("count z:", cm.count("z"))

Each version builds a Bloom filter (64 bits, 3 hash functions) from the words cat, dog and fox, and a Count-Min sketch (32 counters per row, 3 rows) from a stream of 14 words. Every version was compiled and run, and printed dog: maybe, zebra: no, and the counts a: 5, b: 2 and z: 0. The hash function here is a simple teaching example; real systems use stronger, well-mixed hashes. Sizes are examples, so a larger filter gives fewer false positives.

Example 2: Finding trending items in a stream

A social site wants the most-mentioned hashtags in the last hour out of millions of different tags. Keeping an exact counter for every tag takes too much memory. A Count-Min sketch gives each tag an estimate in fixed memory, and a small heap of the current top tags (checked against the sketch as items arrive) gives the trending list.

Every mention updates the sketch. The estimate decides whether the tag enters a small heap of the current top items. Memory stays fixed however many different tags appear.

Example 3: The fuller the filter, the more it lies

A Bloom filter's false-positive rate depends on how full it is. The same 16-bit filter that answers well with 3 words becomes unreliable with 8, because most bits end up set.

Each added word sets up to three bits. After eight words most bits are 1, so a word that was never added can find all its bits already set: a false positive.

More real-world scenarios

4. Databases and storage engines

LSM-tree stores such as Cassandra, RocksDB and HBase keep a Bloom filter per data file so that reads for missing keys skip most files. Bigtable-style systems introduced this approach.

5. Web caches and CDNs

A cache can avoid storing a file that is requested only once (a "one-hit wonder") by admitting an object only when a Bloom filter says it was seen before.

6. Browsers and security lists

Checking every URL against a list of millions of unsafe sites by network call would be slow. A local Bloom filter answers "definitely safe" instantly, and only a "maybe" triggers a precise check.

7. Duplicate detection in crawlers

A web crawler must not fetch the same URL twice. A Bloom filter of seen URLs gives a fast, compact check, accepting that a few new URLs are wrongly skipped.

8. Password and username checks

A site can keep a Bloom filter of known leaked or taken names. A "no" is certain, so most checks need no database query.

9. Network monitoring

A Count-Min sketch tracks packets per source address at line speed to find heavy senders, such as the sources of a denial-of-service attack, with a small fixed table.

10. Analytics and trending

Counting page views, search queries or hashtags across millions of distinct keys uses sketches to find the top items cheaply.

11. Distributed systems

Servers send a Bloom filter of what they hold instead of a full list. The other side can tell what it is definitely missing, which saves bandwidth when synchronising.

12. Counting distinct visitors

HyperLogLog, a close relative, estimates the number of different values in a stream with a few kilobytes and about 1% error. Redis offers it as PFADD and PFCOUNT.

Language standard libraries

Standard libraries rarely include these structures. Each ecosystem has well-used packages, and databases such as Redis offer them as modules.

Language	Built in?	What to use	Notes
Java	No	Guava `BloomFilter` (third party)	Guava lets you set the expected number of items and the false-positive rate.
C++	No	Write it, or use a third-party library	A `std::bitset` or `std::vector<bool>` plus hashes is a short start.
C#	No	Third-party packages	Check the licence and maintenance of a package before using it.
Rust	No	Crates on crates.io	Many small crates exist. Compare maintenance before choosing one.
Python	No	Third-party packages	For exact sets, the built-in `set` is usually enough.
Go	No	`github.com/bits-and-blooms/bloom` (third party)	A widely used package with a size-from-rate constructor.
JavaScript	No	Third-party packages	In browsers, `Set` is exact and often good enough for small data.
Kotlin	No	Guava through Java	Same as Java.

The takeaway from the table: expect to use a package or the database's version, not the standard library. Redis ships HyperLogLog built in, and offers Bloom and Count-Min structures in its Bloom module.

The takeaway

Whenever a system must answer "have I seen this?" or "how often?" for more data than fits in memory, look for a probabilistic structure: a Bloom filter for membership, a Count-Min sketch for counts. When the data is small or every answer must be exact, it usually uses a hash set or map instead.

Interview questions

Try answering out loud before you reveal hints. Interviewers care about how you reason, not just the final answer.

1.
Explain how a Bloom filter works and what errors it can make.
easy
2.
You expect 10 million items and can accept a 1% false-positive rate. Roughly how much memory does a Bloom filter need?
medium
3.
Find the most frequent items in a stream too large to keep in memory.
hard
4.
How do you size a Count-Min sketch for a given error and confidence?
medium
5.
When should you not use a Bloom filter?
easy

Finished this lesson?

Progress is saved on this device. Create a free account to keep it everywhere.

← Previous

Balanced Trees

Randomized Algorithms

Topics:Bloom filterCount min sketchHyperloglogHashingProbabilisticMemory efficientStreams