On this page

Bloom Filters, Count-Min Sketch & Probabilistic Structures

A hash set answers "is in the set?" exactly, and pays for it: every key is stored in full, plus pointers, plus empty slots for the load factor. A Bloom filter answers the same question in about 10 bits per key — whatever the key's size — by accepting a tunable rate of false positives and guaranteeing zero false negatives. A Count-Min Sketch answers "how many times has appeared?" in a few kilobytes for a stream of billions, always over-estimating and never under-estimating. HyperLogLog counts distinct elements in a stream of any size to within about 1% using 12 KB.

These are sketches: fixed-size summaries of data that is too big to keep. They are built from nothing more than hash functions and arrays, which is why they sit in Module 1 next to hash tables. What makes them worth a whole lesson is that every one comes with a proof of exactly how wrong it can be — and that proof is what you must be able to reproduce, because it is the only thing that lets you size a filter for production.

This page is the algorithms-side companion of Bloom Filters & Probabilistic Data Structures in the system-design section. That page is about where these structures sit in a distributed architecture; this one is about why the formulas are true, how to implement the structures identically in four languages, and how to recognise the problems they solve.

Why this exists

Burton Bloom published the filter in 1970 ("Space/Time Trade-offs in Hash Coding with Allowable Errors", CACM 13(7)) for a concrete problem: a hyphenation program with a dictionary of exceptional words that did not fit in core memory. Looking up every word on disk was too slow; keeping the dictionary in memory was impossible. A filter that said "definitely not an exception, hyphenate by rule" for 90% of words — and was only occasionally wrong in the safe direction — removed 90% of the disk reads. The shape of that story recurs in every modern use: the filter sits in front of an expensive exact check and short-circuits the common negative case.

The second family, frequency and cardinality sketches, came out of the streaming-algorithms research of the 1980s–2000s: Flajolet and Martin's probabilistic counting (1985), Misra and Gries's frequent-items algorithm (1982), the Count-Min Sketch of Cormode and Muthukrishnan (2005), HyperLogLog of Flajolet, Fusy, Gandouet and Meunier (2007). The driving constraint was a stream that passes once and cannot be stored: a router seeing packets, a search engine seeing queries. The question changed from "store everything and query later" to "what can be answered with a fixed memory budget in one pass, and with what error?"

Today these structures are inside almost every storage engine you use. Every SSTable in LevelDB, RocksDB and Cassandra has a Bloom filter; Redis ships HyperLogLog as a native type; Postgres has a Bloom index extension; CDNs decide what to cache with Bloom filters; network monitors find heavy hitters with Count-Min Sketches. In interviews they are the standard answer to "what if it does not fit in memory?" — provided you can also say how big the filter must be and how wrong it will be.

Pattern triggers

If the problem says or has…Think of…
"is possibly in the set", "definitely not seen", "skip the lookup if absent"Bloom filter (or cuckoo filter if deletes are needed)
"false positives are acceptable, false negatives are not"Bloom filter
"memory budget", "does not fit in RAM", "billions of keys", "bits per key"a sketch, not a hash table
"approximate count", "approximate frequency", "how many times roughly"Count-Min Sketch
"heavy hitters", "top- most frequent in a stream", "trending"Count-Min Sketch + heap, or Space-Saving
"number of distinct / unique at scale", "cardinality", "unique visitors"HyperLogLog
"how similar are these two sets / documents", "near-duplicate detection"MinHash (+ LSH)
"deduplicate a stream with bounded memory"Bloom filter (time-windowed / rotating)
"one pass over the data", "stream", "cannot store"a sketch; combine with reservoir sampling if you need samples
"exact answer required", "no errors allowed"not this lesson — hash table, sorted structure, or disk

Intuition & first principles

The trade

Suppose you must remember URLs (average 50 bytes) to avoid crawling them twice. An exact hash set stores every URL: 50 GB for the strings alone, realistically 70–100 GB with hash-table overhead. A Bloom filter tuned to 1% false positives uses about 9.6 bits per URL — bits ≈ 1.2 GB — regardless of URL length, because it never stores the key, only the fingerprint of its hashes. (The companion page states the same 40× figure.)

The price is precise and one-sided. When the filter says no, the element is definitely absent. When it says yes, the element is probably present, with a false-positive probability that you choose by spending bits. There are never false negatives: every element you inserted will always be reported as present. This asymmetry is the whole design. It is acceptable exactly when a false "yes" costs only an extra exact check (a disk read, a network call), and a false "no" would be a correctness bug (silently skipping a real element).

Bloom filter mechanics

A Bloom filter is an array of bits, initially all 0, plus hash functions , each mapping a key to a position in .

  • Insert : set bits to 1.
  • Query : if all of bits are 1, answer "possibly"; if any is 0, answer "definitely not".
flowchart LR
    X["key x"] --> H1["h1(x) = 5"]
    X --> H2["h2(x) = 12"]
    X --> H3["h3(x) = 6"]
    H1 --> B["bit array, m = 16<br/>set bits 5, 12, 6 on insert<br/>AND bits 5, 12, 6 on query"]
    H2 --> B
    H3 --> B
    B -->|"any bit is 0"| NO["definitely not present"]
    B -->|"all bits are 1"| MAYBE["possibly present"]

No false negatives is immediate: inserting sets all of 's bits, and bits are never cleared, so a later query of finds them all set. A false positive happens when some other insertions happen to have set all of 's bits.

Trace with , and three deliberately simple hash functions on integer keys:

Insert 4, 9, 13; then query 2, 7, 11 (none of which were inserted). Bit 0 is the leftmost character.

StepPositions Bit array afterBits setResult
insert 45, 12, 600000110000010003—
insert 910, 11, 1500000110001110016—
insert 1314, 7, 300010111001110119—
query 23, 6, 12bits are 1, 1, 1—possibly present — a false positive
query 78, 5, 5bits are 0, 1, 1—definitely not
query 1112, 1, 9bits are 1, 0, 0—definitely not

Key 2 was never inserted, but bit 3 came from inserting 13, bit 6 from 4 and bit 12 from 4 — all three of its probes land on bits set by others. Note also query 7: , two of its three probes hit the same bit, so it is effectively protected by only two bits. Weak, correlated hash functions are the first way a real filter under-performs the formula (see Pitfalls).

With 9 of 16 bits set, a random key's three probes all land on set bits with probability about — so one false positive in three queries is unsurprising. That is what the derivation below quantifies.

Deriving the false-positive rate

Assume the hash functions are independent and each maps a key uniformly at random to one of the positions. Insert keys.

Step 1 — one bit survives one hash. A single hash evaluation leaves a particular bit at 0 with probability .

Step 2 — one bit survives all insertions. Inserting keys performs independent hash evaluations. A particular bit is still 0 after all of them with probability

using . Call this ; it is also, by linearity of expectation, the expected fraction of bits that are still 0.

Step 3 — a non-member's probes all hit set bits. A query for a key that was never inserted probes positions. Treat the fraction of set bits as exactly and the probes as independent of each other and of the insertions. Then each probe finds a 1 with probability , and all do with probability

The two approximations — the exponential and treating the fraction of set bits as its expectation with independent probes — are both tight for realistic ; Bose et al. (2008) showed the classical formula slightly under-estimates the true rate, by an amount that vanishes as grows. For the toy above the formula gives 8%, while the actual filter had 9/16 set bits and a per-query false-positive chance near 18%: tiny filters are where the approximation is poor.

Step 4 — the best . For fixed , more hash functions make each query stricter (good) but set more bits (bad). Write and substitute so :

The expression is symmetric in and is minimised (most negative, so is smallest) at . So the optimum has — half the bits set — giving

Inverting: to achieve false-positive rate you need bits per element. Each halving of costs about 1.44 bits per element.

Target FPR Bits per element (exact) usedFPR with that
10%4.793.32310.1%
1%9.596.6471.00%
0.1%14.389.97100.100%
0.01%19.1713.29130.0100%

(Computed from the formulas above; rounding to the nearest integer costs almost nothing because is flat near its minimum — for 9.6 bits/element, gives 1.01% and gives 1.04%.) Remember: about 10 bits per key and 7 hash functions for 1%; about 14 bits and 10 hashes for 0.1%.

No deletions, and the counting fix

You cannot delete from a Bloom filter. Clearing 's bits would also clear bits that other keys share, creating false negatives — the one error the structure promises never to make. The classic fix is the counting Bloom filter (Fan, Cao, Almeida and Broder, 2000): replace each bit with a small counter (typically 4 bits). Insert increments counters; delete decrements them; query tests whether all are non-zero. Cost: 4× the memory, and counters can overflow (with 4 bits, the probability that any counter exceeds 15 is tiny at the optimal but not zero — implementations saturate at 15 and then refuse to decrement that counter, which re-introduces a small false-positive bias rather than a false negative).

Fewer hash functions: the Kirsch–Mitzenmacher trick

Computing 7 or 10 independent hashes per key is the dominant cost of a Bloom filter. Kirsch and Mitzenmacher ("Less Hashing, Same Performance: Building a Better Bloom Filter", ESA 2006; Random Structures & Algorithms 2008) proved that two hash functions suffice: compute and once, then use

and the asymptotic false-positive rate is unchanged. This is double hashing, the same idea as the open-addressing probe sequence in Hash Tables. Two practical guards: force to be odd (or otherwise non-zero) so that the positions do not collapse onto one, and when is a power of two prefer an odd so the probe sequence visits distinct positions. The implementation below uses exactly this scheme with FNV-1a and a DJB2 variant as the two base hashes.

Scalable Bloom filters

A Bloom filter is sized for a planned . Insert twice as many keys and the false-positive rate does not double — it explodes, because the fraction of set bits approaches 1. When is unknown, a scalable Bloom filter (Almeida, Baquero, Preguiça and Hutchison, 2007) keeps a list of filters: when the current one reaches its design capacity, a new, larger one is started (geometric growth) with a tighter target rate (geometric decay, ratio –), so that the union's rate converges to a chosen bound: . Queries check every filter; inserts go to the newest.

Cache-friendly variants: blocked Bloom filters and cuckoo filters

A standard Bloom query touches random bits, i.e. up to cache misses — for a large filter, 7 misses × ~100 ns is the real cost, not the hashing. Blocked Bloom filters (Putze, Sanders and Singler, 2007) first hash the key to one cache-line-sized block (512 bits), then place all bits within that block: one cache miss per query, at the cost of about one extra bit per element for the same false-positive rate. RocksDB's and most modern engines' filters are blocked (RocksDB's "format version 5" filter) or go further with register-blocked and SIMD-probed layouts.

Cuckoo filters (Fan, Andersen, Kaminsky and Mitzenmacher, "Cuckoo Filter: Practically Better Than Bloom", CoNEXT 2014) take a different route: store a short fingerprint of each key (say 8–16 bits) in one of two candidate buckets of a cuckoo hash table, with 4 slots per bucket. Lookup checks two buckets (two cache misses); delete works by removing the fingerprint; and because the second bucket is derived from the first bucket and the fingerprint alone ("partial-key cuckoo hashing", ), items can be relocated without the original key. Space is about bits per item at load , which beats the Bloom filter's once is below roughly 3%: at 0.1%, about 13.6 bits per item versus 14.4. The cost is a small chance that an insert fails when the table is nearly full, and slower inserts when relocations cascade.

Count-Min Sketch

A Count-Min Sketch (Cormode and Muthukrishnan, "An improved data stream summary: the count-min sketch and its applications", J. Algorithms 2005) estimates frequencies. It is a array of counters with one hash function per row.

  • Update : for each row , count[j][h_j(x)] += c.
  • Estimate : .
flowchart LR
    X["key x, count +1"] --> R0["row 0: cell h0(x) += 1"]
    X --> R1["row 1: cell h1(x) += 1"]
    X --> R2["row 2: cell h2(x) += 1"]
    R0 --> E["estimate = min over rows<br/>never below the true count"]
    R1 --> E
    R2 --> E

Every counter that touches contains 's true count plus whatever other keys collided into that cell. So every row over-estimates, and the minimum is the row with the least collision noise. A Count-Min Sketch never under-estimates. Deleting (negative counts) is allowed as long as no true count goes negative.

Trace with rows, counters, , , over the stream 3, 7, 3, 1, 3, 7, 5:

ItemCells touchedRow 0 afterRow 1 after
3row0[3], row1[2][0, 0, 0, 1][0, 0, 1, 0]
7row0[3], row1[2][0, 0, 0, 2][0, 0, 2, 0]
3row0[3], row1[2][0, 0, 0, 3][0, 0, 3, 0]
1row0[1], row1[0][0, 1, 0, 3][1, 0, 3, 0]
3row0[3], row1[2][0, 1, 0, 4][1, 0, 4, 0]
7row0[3], row1[2][0, 1, 0, 5][1, 0, 5, 0]
5row0[1], row1[0][0, 2, 0, 5][2, 0, 5, 0]

Estimates after the stream ( total count):

KeyTrue countRow 0 cellRow 1 cellEstimate = minError
11row0[1] = 2row1[0] = 22+1
33row0[3] = 5row1[2] = 55+2
51row0[1] = 2row1[0] = 22+1
72row0[3] = 5row1[2] = 55+3
2, 4, 6 (never seen)00000

Every estimate is the truth, never below. The errors here are large relative to the counts because the toy hash functions are terrible: both and depend only on , so keys 3 and 7 collide in every row and the min cannot separate them. The error bound below assumes the rows' hash functions are independent, which these are not — the trace is as much a lesson about hashing as about sketching.

The error bound, and its proof sketch. Let be the total count in the stream. Choose and , with the rows' hash functions drawn independently from a pairwise-independent family. Then for every key :

Proof. Fix and a row . The cell equals where is the collision noise. By pairwise independence, for each , so by linearity of expectation

is non-negative, so Markov's inequality gives . The estimate exceeds only if every row's noise does, and the rows are independent, so

Memory is counters — independent of the number of distinct keys. For and : , , about 13,600 counters, 109 KB with 64-bit counters, to track frequencies in a stream of any length with error at most 0.1% of the total.

Heavy hitters (the keys with ) are found by maintaining a min-heap of the current top- candidates keyed by their estimate, re-estimating a key on each arrival; because estimates never under-count, no true heavy hitter is missed, though false candidates can appear. Conservative update (Estan and Varghese, 2002) increments only the counters that currently equal the minimum — the others are already at least as large as the truth requires — which reduces over-estimation substantially in practice but breaks the ability to merge sketches by addition and to delete.

HyperLogLog

HyperLogLog estimates cardinality — the number of distinct elements — of a stream too large to deduplicate. The intuition: hash every element to a uniform bit string. Among distinct values, the chance that at least one hash begins with zero bits is about , so the longest run of leading zeros observed satisfies . A single such observation has enormous variance (one lucky hash doubles the estimate), so the stream is split by the first bits of the hash into registers, each tracking its own maximum leading-zero count over the elements routed to it, and the estimates are combined with a harmonic mean, which tames the outliers:

Flajolet, Fusy, Gandouet and Meunier ("HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm", AofA 2007) proved the relative standard error is . Each register needs only enough bits to hold a leading-zero count (5 bits for 32-bit hashes, 6 for 64-bit), so memory is bits:

Registers Memory (6-bit registers)Standard error
= 1,024768 B3.25%
= 16,38412 KB0.81%
= 65,53648 KB0.41%

Redis's PFADD / PFCOUNT use registers: 12 KB per key with a standard error of 0.81%, counting up to distinct items (Redis documentation; see also Redis Internals). The original paper uses "linear counting" (a correction based on the number of empty registers) for small cardinalities where the raw estimate is biased, and Google's HyperLogLog++ (Heule, Nunkesser and Hall, 2013) adds 64-bit hashing, an empirically-fitted bias correction and a sparse representation for small sets. Two HLLs with the same merge by taking the register-wise maximum — the union's estimate for free, which is why per-day sketches can be rolled up into per-month counts.

MinHash and locality-sensitive hashing

MinHash (Broder, "On the resemblance and containment of documents", 1997) estimates the Jaccard similarity of two sets. Apply a random hash to every element and keep the minimum, . The minimum over is some element ; exactly when , which happens with probability . So the indicator "the two minima agree" is an unbiased estimate of , and with independent hashes the fraction of agreeing minima estimates with standard error . A document becomes a signature of small integers — 128 hashes = 512 bytes for any document size — and signatures can be compared without the documents. Locality-sensitive hashing groups the signature into bands so that similar documents collide in at least one band with high probability and dissimilar ones rarely do, turning all-pairs near-duplicate detection into hashing. AltaVista used it to deduplicate the web.

Top- without a sketch: Misra–Gries and Space-Saving

If you only need the most frequent items, you do not need per-key frequency estimates. Misra–Gries (1982) keeps counters: increment if the item has a counter, else allocate one if free, else decrement all counters (dropping any that reach zero). Any item with frequency above is guaranteed to survive. Space-Saving (Metwally, Agrawal and El Abbadi, 2005) is the practical variant: when full, replace the minimum-count item with the new one and inherit its count (plus one), tracking an error bound per item. These are previewed here; Module 9's Streaming & Sketching Algorithms page (wave 6) covers them with proofs.

Two things that are not approximate

Skip lists are randomised but exact: every query returns the true answer; only the running time is probabilistic. They belong with balanced trees — see Advanced Data Structures. Reservoir sampling picks a uniform random sample of items from a stream of unknown length in one pass; it is a randomised algorithm, not a sketch, and belongs to Module 5's randomised-algorithms page (wave 4).

Choosing hash functions

Sketches need hash functions that are fast and well-distributed, not cryptographic. MurmurHash3 (Appleby, 2008–2011) and xxHash / XXH3 (Collet, 2012–2019) run at several GB/s with excellent avalanche behaviour, and both are seedable, so " independent hashes" is "one function, seeds" — or, with Kirsch–Mitzenmacher, two seeds. Cryptographic hashes like SHA-256 are 10–50× slower and buy nothing here: a Bloom filter is not trying to resist an adversary who chooses keys to collide. (If it must — e.g. a filter whose false positives can be triggered by an attacker to cause expensive lookups — use a keyed hash such as SipHash with a secret seed.) See Hashing Algorithms. The implementation below uses FNV-1a and a DJB2 variant because they are a few lines each and portable; they are good enough for the demonstration and noticeably worse than Murmur3 for production.

Mechanics: exact vs approximate, a comparison

The "ladder" for this topic is not brute → optimal but exact → approximate at each rung of memory.

QuestionExact structureExact memory for keysSketchSketch memoryError
Is in the set?hash set of keys≥ 8 GB (8-byte keys), 50–100 GB (URLs)Bloom filter at 1%1.2 GB (9.6 bits/key)false positives 1%, no false negatives
Is in the set, with deletes?hash setas abovecuckoo filter at 1%~1.3 GB (≈ 10 bits/key)false positives ≈ 1%; inserts can fail near full
How many times has appeared?hash map key → count≥ 16 GBCount-Min Sketch, , 27,183 × 7 × 8 B ≈ 1.5 MBover-estimate by ≤ with prob ≥ 0.999
How many distinct?hash set≥ 8 GBHyperLogLog, 12 KB± 0.81% standard error
How similar are two sets?store both, intersectsizes of both setsMinHash, 128 hashes512 B per set± ≈ 4% absolute

What these have in common: memory is a function of the error you accept, not the data size. That is the property an interviewer is probing for when they say "and now the data is 100× bigger".

StructureInsertQueryDeleteMerge two sketchesWhat is guaranteed
Bloom filterno (counting variant: yes)bitwise OR (same , , hashes)no false negatives
Cuckoo filter amortised, may fail (2 buckets)yesno simple mergeno false negatives while no insert failed
Count-Min Sketchyes (if counts stay ≥ 0)cell-wise add (same , , hashes)never under-estimates
HyperLogLognoregister-wise maxunbiased estimate with known std error
MinHash per element per pairnoelement-wise min (union)unbiased Jaccard estimate

Correctness and analysis

The two proofs that matter are above: the false-positive derivation with its independence assumptions made explicit, and the Count-Min bound via Markov's inequality and independent rows. Three further facts are worth stating as theorems:

Bloom filters have no false negatives. Bits are only ever set, never cleared; a query of an inserted key re-derives the same positions, all of which were set at insertion. The argument fails the moment you add deletion — which is the entire reason counting and cuckoo filters exist.

The minimum is the right combiner for Count-Min. Each row's cell is with , so every row is an upper bound on ; the tightest upper bound available is the minimum. Averaging rows would be worse (it adds noise from the noisier rows); the median is used by the related Count Sketch, where the noise is signed and averages out.

Merging sketches is exact for the union. Two Bloom filters with identical parameters OR'd together equal the filter you would have built from the union of their inputs — same bits set, so the same false-positive rate as a single filter of the combined . Two Count-Min sketches added cell-wise equal the sketch of the concatenated streams. Two HLLs max'd register-wise equal the HLL of the union, because each register stores a maximum, and the maximum over a union is the maximum of the maxima. This is why sketches are the natural tool for distributed aggregation: shard, sketch, merge.

Complexity

OperationTimeSpace
Bloom insert / query hashes and bit probes; with Kirsch–Mitzenmacher (2 hashes + arithmetic steps) bits,
Counting Bloomsame bits typical
Cuckoo filter insert expected; bounded relocations (500 by convention) before declaring failure bits per item
Cuckoo filter query / delete: two buckets of 4 slots—
Count-Min update / estimate, (5–7 in practice) counters,
HyperLogLog add: hash, index, count leading zeros, max bits
HyperLogLog count—
MinHash signature integers per set

Cache behaviour dominates. A Bloom filter of 1.2 GB does not fit in any cache; each of the probes is a likely cache miss (~100 ns), so a query costs roughly ns ≈ 0.7 µs — slower than hashing. Blocked Bloom filters bring this to one miss; cuckoo filters to two. Count-Min rows are small enough (tens of KB) to stay in L2, so its cost really is hashes. HyperLogLog at 12 KB lives in L1.

Implementation

Both classes share two base hashes (32-bit FNV-1a and a DJB2 XOR variant, over the ASCII bytes of the key), combined by double hashing with forced odd. The tests use an inline xorshift32 generator with a fixed seed so that all four languages generate the same keys and must report the same false-positive count — 108 of 10,000 non-members for bits, , (1.08%, against a predicted 1.0%). The Count-Min test checks no under-estimation on every key and the exact estimates a → 505, b → 306, c → 104 (true counts 500, 300, 100) and 2 for a key never seen. If any language disagreed, its hashing would be wrong — this is the self-check.

MASK32 = 0xFFFFFFFF


def fnv1a(key: str) -> int:
    h = 2166136261
    for ch in key:
        h ^= ord(ch)
        h = (h * 16777619) & MASK32
    return h


def djb2x(key: str) -> int:
    h = 5381
    for ch in key:
        h = ((h * 33) ^ ord(ch)) & MASK32
    return h


def positions(key: str, k: int, size: int) -> list[int]:
    """Kirsch-Mitzenmacher double hashing: k positions from two hashes."""
    h1, h2 = fnv1a(key), djb2x(key) | 1
    return [(h1 + i * h2) % size for i in range(k)]


class BloomFilter:
    def __init__(self, m: int, k: int) -> None:
        self.m, self.k = m, k
        self.bits = bytearray((m + 7) // 8)

    def add(self, key: str) -> None:
        for p in positions(key, self.k, self.m):
            self.bits[p >> 3] |= 1 << (p & 7)

    def might_contain(self, key: str) -> bool:
        return all((self.bits[p >> 3] >> (p & 7)) & 1 for p in positions(key, self.k, self.m))


class CountMinSketch:
    def __init__(self, w: int, d: int) -> None:
        self.w, self.d = w, d
        self.table = [[0] * w for _ in range(d)]

    def add(self, key: str, count: int = 1) -> None:
        for j, c in enumerate(positions(key, self.d, self.w)):
            self.table[j][c] += count

    def estimate(self, key: str) -> int:
        return min(self.table[j][c] for j, c in enumerate(positions(key, self.d, self.w)))


class XorShift32:
    def __init__(self, seed: int) -> None:
        self.x = seed & MASK32

    def next(self) -> int:
        x = self.x
        x ^= (x << 13) & MASK32
        x ^= x >> 17
        x ^= (x << 5) & MASK32
        self.x = x & MASK32
        return self.x


if __name__ == "__main__":
    bf = BloomFilter(9600, 7)                      # 9.6 bits/key, k = 7 -> ~1% FPR
    members = [f"user:{i}" for i in range(1000)]
    for key in members:
        bf.add(key)
    assert all(bf.might_contain(key) for key in members)          # no false negatives, ever
    rng = XorShift32(2463534242)
    false_positives = sum(bf.might_contain(f"ghost:{rng.next() % 1000000}") for _ in range(10000))
    assert false_positives == 108, false_positives                # identical in all 4 languages
    assert false_positives / 10000 < 0.02                          # within 2x of the predicted 1%

    cms = CountMinSketch(16, 4)
    rng2 = XorShift32(88172645)
    stream = ["a"] * 500 + ["b"] * 300 + ["c"] * 100 + [f"z{rng2.next() % 1000}" for _ in range(100)]
    truth: dict[str, int] = {}
    for key in stream:
        cms.add(key)
        truth[key] = truth.get(key, 0) + 1
    assert all(cms.estimate(key) >= n for key, n in truth.items())  # never under-estimates
    assert (cms.estimate("a"), cms.estimate("b"), cms.estimate("c")) == (505, 306, 104)
    assert cms.estimate("nope") == 2                               # noise on a never-seen key
    print("ALL TESTS PASSED")
import java.util.BitSet;
import java.util.HashMap;
import java.util.Map;

public class ProbabilisticSketches {

    static long fnv1a(String key) {
        int h = 0x811C9DC5;                       // 2166136261 as a wrapping int
        for (int i = 0; i < key.length(); i++) {
            h ^= key.charAt(i);
            h *= 16777619;                        // wraps mod 2^32, as intended
        }
        return Integer.toUnsignedLong(h);
    }

    static long djb2x(String key) {
        int h = 5381;
        for (int i = 0; i < key.length(); i++) h = (h * 33) ^ key.charAt(i);
        return Integer.toUnsignedLong(h);
    }

    /** Kirsch-Mitzenmacher double hashing: k positions from two hashes. */
    static int[] positions(String key, int k, int size) {
        long h1 = fnv1a(key), h2 = djb2x(key) | 1L;
        int[] out = new int[k];
        for (int i = 0; i < k; i++) out[i] = (int) ((h1 + i * h2) % size);
        return out;
    }

    static final class BloomFilter {
        final int m, k;
        final BitSet bits;
        BloomFilter(int m, int k) { this.m = m; this.k = k; this.bits = new BitSet(m); }
        void add(String key) { for (int p : positions(key, k, m)) bits.set(p); }
        boolean mightContain(String key) {
            for (int p : positions(key, k, m)) if (!bits.get(p)) return false;
            return true;
        }
    }

    static final class CountMinSketch {
        final int w, d;
        final long[][] table;
        CountMinSketch(int w, int d) { this.w = w; this.d = d; this.table = new long[d][w]; }
        void add(String key, long count) {
            int[] cols = positions(key, d, w);
            for (int j = 0; j < d; j++) table[j][cols[j]] += count;
        }
        long estimate(String key) {
            int[] cols = positions(key, d, w);
            long best = Long.MAX_VALUE;
            for (int j = 0; j < d; j++) best = Math.min(best, table[j][cols[j]]);
            return best;
        }
    }

    static final class XorShift32 {
        int x;
        XorShift32(long seed) { x = (int) seed; }
        long next() {
            x ^= x << 13;
            x ^= x >>> 17;
            x ^= x << 5;
            return Integer.toUnsignedLong(x);
        }
    }

    static void check(boolean ok, String what) { if (!ok) throw new AssertionError(what); }

    public static void main(String[] args) {
        BloomFilter bf = new BloomFilter(9600, 7);
        for (int i = 0; i < 1000; i++) bf.add("user:" + i);
        for (int i = 0; i < 1000; i++) check(bf.mightContain("user:" + i), "false negative");
        XorShift32 rng = new XorShift32(2463534242L);
        int falsePositives = 0;
        for (int i = 0; i < 10000; i++) if (bf.mightContain("ghost:" + (rng.next() % 1000000))) falsePositives++;
        check(falsePositives == 108, "fp count " + falsePositives);
        check(falsePositives / 10000.0 < 0.02, "fp rate");

        CountMinSketch cms = new CountMinSketch(16, 4);
        XorShift32 rng2 = new XorShift32(88172645L);
        Map<String, Integer> truth = new HashMap<>();
        java.util.List<String> stream = new java.util.ArrayList<>();
        for (int i = 0; i < 500; i++) stream.add("a");
        for (int i = 0; i < 300; i++) stream.add("b");
        for (int i = 0; i < 100; i++) stream.add("c");
        for (int i = 0; i < 100; i++) stream.add("z" + (rng2.next() % 1000));
        for (String key : stream) { cms.add(key, 1); truth.merge(key, 1, Integer::sum); }
        for (Map.Entry<String, Integer> e : truth.entrySet())
            check(cms.estimate(e.getKey()) >= e.getValue(), "under-estimate " + e.getKey());
        check(cms.estimate("a") == 505 && cms.estimate("b") == 306 && cms.estimate("c") == 104, "estimates");
        check(cms.estimate("nope") == 2, "unseen key");
        System.out.println("ALL TESTS PASSED");
    }
}
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

std::uint32_t fnv1a(const std::string& key) {
    std::uint32_t h = 2166136261u;
    for (unsigned char c : key) { h ^= c; h *= 16777619u; }   // wraps mod 2^32
    return h;
}

std::uint32_t djb2x(const std::string& key) {
    std::uint32_t h = 5381u;
    for (unsigned char c : key) h = (h * 33u) ^ c;
    return h;
}

// Kirsch-Mitzenmacher double hashing: k positions from two hashes.
std::vector<std::size_t> positions(const std::string& key, int k, std::size_t size) {
    std::uint64_t h1 = fnv1a(key), h2 = djb2x(key) | 1u;
    std::vector<std::size_t> out(k);
    for (int i = 0; i < k; ++i) out[i] = static_cast<std::size_t>((h1 + i * h2) % size);
    return out;
}

class BloomFilter {
    std::size_t m_;
    int k_;
    std::vector<std::uint64_t> words_;
public:
    BloomFilter(std::size_t m, int k) : m_(m), k_(k), words_((m + 63) / 64, 0) {}
    void add(const std::string& key) {
        for (std::size_t p : positions(key, k_, m_)) words_[p >> 6] |= std::uint64_t{1} << (p & 63);
    }
    bool mightContain(const std::string& key) const {
        for (std::size_t p : positions(key, k_, m_))
            if (!((words_[p >> 6] >> (p & 63)) & 1u)) return false;
        return true;
    }
};

class CountMinSketch {
    std::size_t w_;
    int d_;
    std::vector<std::vector<std::int64_t>> table_;
public:
    CountMinSketch(std::size_t w, int d) : w_(w), d_(d), table_(d, std::vector<std::int64_t>(w, 0)) {}
    void add(const std::string& key, std::int64_t count = 1) {
        auto cols = positions(key, d_, w_);
        for (int j = 0; j < d_; ++j) table_[j][cols[j]] += count;
    }
    std::int64_t estimate(const std::string& key) const {
        auto cols = positions(key, d_, w_);
        std::int64_t best = INT64_MAX;
        for (int j = 0; j < d_; ++j) best = std::min(best, table_[j][cols[j]]);
        return best;
    }
};

struct XorShift32 {
    std::uint32_t x;
    explicit XorShift32(std::uint32_t seed) : x(seed) {}
    std::uint32_t next() { x ^= x << 13; x ^= x >> 17; x ^= x << 5; return x; }
};

int main() {
    BloomFilter bf(9600, 7);
    for (int i = 0; i < 1000; ++i) bf.add("user:" + std::to_string(i));
    for (int i = 0; i < 1000; ++i) assert(bf.mightContain("user:" + std::to_string(i)));   // no false negatives
    XorShift32 rng(2463534242u);
    int falsePositives = 0;
    for (int i = 0; i < 10000; ++i)
        if (bf.mightContain("ghost:" + std::to_string(rng.next() % 1000000u))) ++falsePositives;
    assert(falsePositives == 108);
    assert(falsePositives / 10000.0 < 0.02);

    CountMinSketch cms(16, 4);
    XorShift32 rng2(88172645u);
    std::vector<std::string> stream;
    for (int i = 0; i < 500; ++i) stream.push_back("a");
    for (int i = 0; i < 300; ++i) stream.push_back("b");
    for (int i = 0; i < 100; ++i) stream.push_back("c");
    for (int i = 0; i < 100; ++i) stream.push_back("z" + std::to_string(rng2.next() % 1000u));
    std::unordered_map<std::string, std::int64_t> truth;
    for (const auto& key : stream) { cms.add(key); ++truth[key]; }
    for (const auto& [key, n] : truth) assert(cms.estimate(key) >= n);                     // never under-estimates
    assert(cms.estimate("a") == 505 && cms.estimate("b") == 306 && cms.estimate("c") == 104);
    assert(cms.estimate("nope") == 2);
    std::cout << "ALL TESTS PASSED\n";
    return 0;
}
function fnv1a(key: string): number {
  let h = 2166136261;
  for (let i = 0; i < key.length; i++) {
    h ^= key.charCodeAt(i);                 // ASCII keys: char code == byte
    h = Math.imul(h, 16777619) >>> 0;       // 32-bit wrapping multiply, then unsigned
  }
  return h >>> 0;
}

function djb2x(key: string): number {
  let h = 5381;
  for (let i = 0; i < key.length; i++) h = (Math.imul(h, 33) ^ key.charCodeAt(i)) >>> 0;
  return h >>> 0;
}

/** Kirsch-Mitzenmacher double hashing: k positions from two hashes. */
function positions(key: string, k: number, size: number): number[] {
  const h1 = fnv1a(key), h2 = (djb2x(key) | 1) >>> 0;   // h1 + i*h2 < 2^36, exact in a double
  const out: number[] = new Array(k);
  for (let i = 0; i < k; i++) out[i] = (h1 + i * h2) % size;
  return out;
}

class BloomFilter {
  private bits: Uint8Array;
  private m: number;
  private k: number;
  constructor(m: number, k: number) {
    this.m = m;
    this.k = k;
    this.bits = new Uint8Array((m + 7) >> 3);
  }
  add(key: string): void {
    for (const p of positions(key, this.k, this.m)) this.bits[p >> 3] |= 1 << (p & 7);
  }
  mightContain(key: string): boolean {
    for (const p of positions(key, this.k, this.m)) if (((this.bits[p >> 3] >> (p & 7)) & 1) === 0) return false;
    return true;
  }
}

class CountMinSketch {
  private table: number[][];
  private w: number;
  private d: number;
  constructor(w: number, d: number) {
    this.w = w;
    this.d = d;
    this.table = Array.from({ length: d }, () => new Array<number>(w).fill(0));
  }
  add(key: string, count: number = 1): void {
    const cols = positions(key, this.d, this.w);
    for (let j = 0; j < this.d; j++) this.table[j][cols[j]] += count;
  }
  estimate(key: string): number {
    const cols = positions(key, this.d, this.w);
    let best = Infinity;
    for (let j = 0; j < this.d; j++) best = Math.min(best, this.table[j][cols[j]]);
    return best;
  }
}

class XorShift32 {
  private x: number;
  constructor(seed: number) { this.x = seed >>> 0; }
  next(): number {
    let x = this.x;
    x ^= x << 13;
    x ^= x >>> 17;
    x ^= x << 5;
    this.x = x >>> 0;
    return this.x;
  }
}

function check(ok: boolean, what: string): void { if (!ok) throw new Error(what); }

const bf = new BloomFilter(9600, 7);
for (let i = 0; i < 1000; i++) bf.add(`user:${i}`);
for (let i = 0; i < 1000; i++) check(bf.mightContain(`user:${i}`), "false negative");
const rng = new XorShift32(2463534242);
let falsePositives = 0;
for (let i = 0; i < 10000; i++) if (bf.mightContain(`ghost:${rng.next() % 1000000}`)) falsePositives++;
check(falsePositives === 108, `fp count ${falsePositives}`);
check(falsePositives / 10000 < 0.02, "fp rate");

const cms = new CountMinSketch(16, 4);
const rng2 = new XorShift32(88172645);
const stream: string[] = [];
for (let i = 0; i < 500; i++) stream.push("a");
for (let i = 0; i < 300; i++) stream.push("b");
for (let i = 0; i < 100; i++) stream.push("c");
for (let i = 0; i < 100; i++) stream.push(`z${rng2.next() % 1000}`);
const truth = new Map<string, number>();
for (const key of stream) { cms.add(key); truth.set(key, (truth.get(key) ?? 0) + 1); }
for (const [key, n] of truth) check(cms.estimate(key) >= n, `under-estimate ${key}`);
check(cms.estimate("a") === 505 && cms.estimate("b") === 306 && cms.estimate("c") === 104, "estimates");
check(cms.estimate("nope") === 2, "unseen key");
console.log("ALL TESTS PASSED");

Why 108 and not 100: the predicted 1.0% is an expectation; the observed count for one filter and one set of 10,000 queries is binomially distributed around it (standard deviation about ), and the weak demonstration hashes add a little bias. Replace FNV-1a/DJB2 with two seeds of MurmurHash3 and re-run to see the number move.

Sizing helper. Given and : , . For , : bits ≈ 1.20 GB, .

Real-world uses

LSM-tree storage engines. Every SSTable in LevelDB, RocksDB and Cassandra carries a Bloom filter over its keys. A point lookup that misses the memtable would otherwise have to binary-search the index of every SSTable that might hold the key — one disk read per level. The filter turns most of those into "definitely not here" in a few hundred nanoseconds. RocksDB's default of 10 bits per key corresponds to a ~1% false-positive rate; Cassandra exposes bloom_filter_fp_chance per table (default 0.01 for most compaction strategies, 0.1 for levelled). See Storage Engines and Cassandra Internals.

CDN caching and one-hit wonders. Akamai reported that roughly three-quarters of the objects requested from its edge caches were requested exactly once ("one-hit wonders"); caching them on first access evicted useful content. The fix is a Bloom filter of recently-seen URLs: cache an object only when the filter says it has been seen before (Maggs and Sitaraman, "Algorithmic Nuggets in Content Delivery", ACM SIGCOMM CCR 2015). The occasional false positive caches a one-hit wonder — harmless. See Caching Strategies.

Chrome Safe Browsing (historically). Early versions of Chrome's Safe Browsing kept a Bloom filter of malicious-URL hash prefixes locally so that the browser only contacted Google's servers for the small fraction of URLs the filter flagged; the client-side structure was later replaced by a compressed sorted prefix set, but the design — a local approximate filter in front of a remote exact check — is the canonical pattern. (The companion system-design page describes the same architecture.)

Bitcoin SPV clients. BIP 37 (2012) let lightweight wallets send a Bloom filter of their addresses to full nodes, which returned only matching transactions, with false positives providing plausible deniability. It leaked more privacy than intended, and most nodes now disable it in favour of BIP 157/158 compact block filters.

Spell checkers. McIlroy's Unix spell (1982) squeezed its dictionary into a compressed hash-bit table to fit a PDP-11's 64 KB address space; colliding misspellings were accepted as false positives.

PostgreSQL bloom index. The bloom contrib module builds a signature-file index: each row gets a small Bloom filter over the indexed columns, so an equality query on any subset of those columns can scan the signatures and skip rows that definitely do not match — one index instead of one B-tree per column combination.

Redis HyperLogLog. PFADD / PFCOUNT / PFMERGE give unique-visitor counts per page, per day, per campaign in 12 KB each, and PFMERGE folds daily sketches into a monthly figure. The implementation uses a sparse encoding for small cardinalities and switches to the dense 16,384-register form as the set grows. See Redis Internals.

Network monitoring and stream processing. Count-Min Sketches identify heavy-hitter flows (source IPs, prefixes) on routers at line rate; Apache Spark, Flink and Druid expose CMS and HLL as approximate aggregation functions (approx_count_distinct is an HLL++).

Pitfalls & edge cases

  • Deleting from a plain Bloom filter. Clearing bits creates false negatives, the one error the structure forbids. Use a counting Bloom filter or a cuckoo filter, or rebuild the filter periodically.
  • Counting Bloom filter deletions done wrongly. Deleting a key that was never inserted corrupts other keys' counters (they go to zero → false negatives). Only delete what you know you inserted; many implementations pair the filter with an exact log for that reason.
  • Poor hash independence. The derivation assumes the positions are independent and uniform. Hash functions that share structure (the CMS trace above, or hash(x), hash(x)+1, …) collide together and the real false-positive rate can be several times the predicted one. Use seeded Murmur3/xxHash or Kirsch–Mitzenmacher from two different good hashes.
  • Saturation. A filter sized for keys at 1% is at roughly 10% after inserts and useless after — the rate is a steep function of the fill. Track the number of insertions and rebuild or scale (scalable Bloom filter) when it passes the design capacity.
  • Treating the FPR as per-filter rather than per-query. means each lookup of a non-member has a 1% chance to be wrong. A workload of negative lookups per second produces false positives per second, each costing a real disk read. Size the filter against the expected negative-lookup volume, not against "1% sounds small".
  • Forgetting that Count-Min only over-estimates. Using a CMS estimate as a lower bound (e.g. "at least this many occurrences, so it is safe to delete") is wrong by construction. It is an upper bound.
  • Merging sketches with different parameters. OR-ing two Bloom filters or adding two CMSs is only meaningful with identical , (or , ) and identical hash seeds. Pin the seeds in configuration; do not let each process pick its own.
  • HyperLogLog on small cardinalities. The raw estimator is biased for ; without the linear-counting / HLL++ correction, an HLL of 16,384 registers asked to count 100 items can be off by far more than 0.81%. Use a library that implements the corrections (Redis does).
  • Signed vs unsigned 32-bit arithmetic. In JavaScript, h * 16777619 loses precision beyond and |/^ produce signed 32-bit results. Use Math.imul for wrapping multiplication and >>> 0 to reinterpret as unsigned. In Java, int wraps correctly but % on a negative value is negative — convert with Integer.toUnsignedLong before taking the modulus.
  • Thread safety. Concurrent add on a bit array with plain OR is a benign race only if the OR is atomic at the word level (AtomicLongArray, std::atomic<uint64_t>::fetch_or); CMS counters need atomic adds; HLL register updates are idempotent maxima and can use compare-and-swap.
  • Hashing the wrong bytes. Hashing a string's UTF-16 code units in one language and its UTF-8 bytes in another gives different filters for the same keys; the code above restricts itself to ASCII to sidestep this. Define the byte encoding in the on-disk filter format.

Variations

  • Counting Bloom filter — counters instead of bits; supports delete; 4× memory.
  • Scalable Bloom filter — a growing series of filters with tightening error; for unknown .
  • Blocked / register-blocked Bloom filter — all probes in one cache line; one miss per query; ~1 extra bit per key.
  • Partitioned Bloom filter — disjoint slices of bits, one per hash; slightly higher FPR, simpler analysis.
  • Cuckoo filter — fingerprints in a cuckoo hash table; deletes; better space below ~3% FPR; inserts can fail.
  • Xor filter (Graf and Lemire, "Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters", ACM JEA 2020) — a static filter built once over a known key set, about 1.23 bits per key per bit of fingerprint ( bits at 1% FPR vs 9.6 for Bloom but far faster queries: three memory accesses and two XORs, no multiplication). Immutable, so no inserts after construction; ideal for SSTables. RocksDB's ribbon filter (Dillinger and Walzer, 2021) is the same idea with a different linear-algebra construction and ~30% less space.
  • Quotient filter (Bender et al., 2012) — a compact open-addressing table of fingerprints with cache-friendly linear probing; supports delete, merge and resize; the basis of several SSD-oriented filters.
  • Count sketch (Charikar, Chen and Farach-Colton, 2002) — each row also has a random sign per key; estimates are the median over rows of sign × counter; unbiased (errors in both directions) with error proportional to the norm of the frequency vector rather than , which is much better for skewed data.
  • HyperLogLog++ — 64-bit hashes, empirical bias correction, sparse representation; what most libraries actually implement.
  • Theta sketches (Apache DataSketches) — a sample of the smallest hash values; supports union, intersection and difference of distinct counts, which HLL cannot do.

Practice ladder

Warm-ups are LeetCode design problems that exercise the exact structures you are approximating; the rest are design exercises with a stated memory budget.

1. Design HashSet (LeetCode 705) — build a set with add/remove/contains and no library hash set. Teaches the exact baseline (buckets + chaining) that a Bloom filter replaces.

Hint

An array of buckets, each a list; index by key % buckets. Resize when the load factor passes 0.75. Then ask: how many bytes per key did you spend?

2. Design HashMap (LeetCode 706) — same with values. Teaches what a Count-Min Sketch gives up (the key itself) to get constant memory.

Hint

Buckets of (key, value) pairs. Compare its memory with a CMS of the same error budget for a million keys.

3. Insert Delete GetRandom O(1) (LeetCode 380) — a set with uniform random sampling. Teaches the array + index-map trick that reservoir sampling and cuckoo filters build on.

Hint

Keep the elements in an array and a map value → index. Delete by swapping the victim with the last element, then popping.

Solution
import random


class RandomizedSet:
    def __init__(self) -> None:
        self.vals: list[int] = []
        self.pos: dict[int, int] = {}

    def insert(self, val: int) -> bool:
        if val in self.pos:
            return False
        self.pos[val] = len(self.vals)
        self.vals.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.pos:
            return False
        i, last = self.pos[val], self.vals[-1]
        self.vals[i] = last            # move the last element into the hole
        self.pos[last] = i
        self.vals.pop()
        del self.pos[val]
        return True

    def get_random(self) -> int:
        return self.vals[random.randrange(len(self.vals))]


rs = RandomizedSet()
assert rs.insert(1) and not rs.insert(1) and rs.insert(2)
assert rs.remove(1) and not rs.remove(1)
assert rs.get_random() == 2
assert rs.insert(1) and rs.remove(2) and rs.get_random() == 1
print("ok")

All three operations expected; space. The swap-with-last trick is why deletion keeps the array dense.

4. Shuffle an Array (LeetCode 384) — return a uniformly random permutation. Teaches Fisher–Yates, the one-pass uniform shuffle that reservoir sampling generalises.

Hint

For i from n-1 down to 1, swap a[i] with a[randrange(i+1)]. Prove each permutation has probability by induction on i.

5. Design Skiplist (LeetCode 1206) — search/add/erase with randomised levels. Teaches the difference between randomised time (skip list) and approximate answers (this page).

Hint

Each node gets a level with probability per extra level. Search drops a level when the next node is too large. Exact answers, expected .

6. Design: a URL-seen filter for a web crawler — the crawler will fetch pages; it must not re-crawl a URL, and may skip up to 1% of genuinely new URLs by mistake. Give the memory, the number of hash functions, and what you do when the crawl grows past the plan. Teaches sizing from the formula.

Hint

bits, . Then: who owns the filter when the crawler is sharded across 100 machines?

Solution
import math


def bloom_params(n: int, p: float) -> tuple[int, int]:
    """Bits m and hash count k for n keys at false-positive rate p."""
    m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))
    k = max(1, round(m / n * math.log(2)))
    return m, k


def predicted_fpr(m: int, n: int, k: int) -> float:
    return (1 - math.exp(-k * n / m)) ** k


m, k = bloom_params(1_000_000_000, 0.01)
assert k == 7
assert 1.19e9 < m / 8 < 1.21e9                  # about 1.2 GB
assert abs(predicted_fpr(m, 1_000_000_000, k) - 0.01) < 0.0002
# What happens if the crawl is 3x bigger than planned?
assert predicted_fpr(m, 3_000_000_000, k) > 0.10   # the 1% filter is now worse than 10%
m2, k2 = bloom_params(1_000_000_000, 0.001)
assert k2 == 10 and 14.3 < m2 / 1e9 < 14.4        # 0.1% costs ~14.4 bits/key
print("ok", m, k)

Design notes: shard the filter by URL hash so each crawler shard owns one filter (no cross-machine lookups), persist filters to disk periodically (a filter is just bytes), and when the crawl outgrows the plan start a scalable Bloom filter's next layer at a tighter rate rather than letting the first filter saturate. A false positive here costs one skipped page; a false negative (impossible) would cost a duplicate fetch.

7. Design: heavy hitters in a log stream — a service logs requests per hour; report the 10 most frequent client IPs each hour using under 1 MB. Teaches CMS + heap and the guarantee it does and does not give.

Hint

CMS with (any IP with share is noise) and ; a min-heap of the top-10 by estimated count, refreshed on each arrival. Why can a false heavy hitter appear but a true one never be missed?

Solution
import hashlib
import heapq


def h(key: str, seed: int, size: int) -> int:
    digest = hashlib.blake2b(f"{seed}:{key}".encode(), digest_size=8).digest()
    return int.from_bytes(digest, "little") % size


class CountMinSketch:
    def __init__(self, w: int, d: int) -> None:
        self.w, self.d = w, d
        self.table = [[0] * w for _ in range(d)]

    def add(self, key: str) -> int:
        est = float("inf")
        for j in range(self.d):
            c = h(key, j, self.w)
            self.table[j][c] += 1
            est = min(est, self.table[j][c])
        return int(est)


class HeavyHitters:
    def __init__(self, k: int, w: int, d: int) -> None:
        self.k, self.cms = k, CountMinSketch(w, d)
        self.heap: list[tuple[int, str]] = []        # (estimate, key), min at the top
        self.in_heap: dict[str, int] = {}

    def add(self, key: str) -> None:
        est = self.cms.add(key)
        if key in self.in_heap:
            self.in_heap[key] = est                  # lazy: rebuild the heap from the dict
            self.heap = [(e, kk) for kk, e in self.in_heap.items()]
            heapq.heapify(self.heap)
        elif len(self.heap) < self.k:
            heapq.heappush(self.heap, (est, key)); self.in_heap[key] = est
        elif est > self.heap[0][0]:
            _, evicted = heapq.heapreplace(self.heap, (est, key))
            del self.in_heap[evicted]; self.in_heap[key] = est

    def top(self) -> list[str]:
        return [kk for _, kk in sorted(self.heap, reverse=True)]


hh = HeavyHitters(k=3, w=272, d=5)                   # eps = e/272 = 0.01, delta = e^-5
stream = ["10.0.0.1"] * 400 + ["10.0.0.2"] * 250 + ["10.0.0.3"] * 120
stream += [f"192.168.{i // 256}.{i % 256}" for i in range(230)]   # 230 singletons
for ip in stream:
    hh.add(ip)
assert hh.top() == ["10.0.0.1", "10.0.0.2", "10.0.0.3"]
print("ok")

per arrival (the lazy heap rebuild on a repeat is , fine for ); memory counters plus entries, independent of the number of distinct IPs. Because estimates never under-count, every true heavy hitter has an estimate at least as large as its true count and cannot be evicted by a lighter key; a light key can sneak in only if it is over-estimated, which the bound makes rare.

8. Design: distinct users per day with 12 KB — count unique user IDs per day across events, keep 90 days, and answer "unique users in any date range". Teaches HLL sizing and mergeability.

Hint

One HLL (, 12 KB) per day → 1.08 MB for 90 days. A date range is PFMERGE of the days (register-wise max) — the union is exact in the sketch sense, so the merged estimate has the same 0.81% standard error. You cannot answer "users active on both day 1 and day 2" with HLL; that needs Theta sketches or inclusion–exclusion with compounding error.

9. Design: deduplicate an event stream with bounded memory — events carry an ID and may be redelivered within 10 minutes; drop duplicates using at most 64 MB, accepting that 0.1% of genuinely new events may be wrongly dropped. Teaches time-windowed (rotating) Bloom filters.

Hint

Two filters, current and previous; check both, insert into current; every 10 minutes discard previous, current becomes previous, start a fresh current. Why two and not one? What is the effective window?

Solution
import hashlib


class Bloom:
    def __init__(self, m: int, k: int) -> None:
        self.m, self.k, self.bits = m, k, bytearray((m + 7) // 8)

    def _pos(self, key: str) -> list[int]:
        d = hashlib.blake2b(key.encode(), digest_size=16).digest()
        h1, h2 = int.from_bytes(d[:8], "little"), int.from_bytes(d[8:], "little") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]

    def add(self, key: str) -> None:
        for p in self._pos(key):
            self.bits[p >> 3] |= 1 << (p & 7)

    def __contains__(self, key: str) -> bool:
        return all(self.bits[p >> 3] >> (p & 7) & 1 for p in self._pos(key))


class Deduplicator:
    """Rotating pair of Bloom filters: remembers at least one window, at most two."""

    def __init__(self, m: int, k: int, window: int) -> None:
        self.m, self.k, self.window = m, k, window
        self.cur, self.prev = Bloom(m, k), Bloom(m, k)
        self.epoch = 0

    def _tick(self, now: int) -> None:
        epoch = now // self.window
        if epoch > self.epoch:
            self.prev = self.cur if epoch == self.epoch + 1 else Bloom(self.m, self.k)
            self.cur = Bloom(self.m, self.k)
            self.epoch = epoch

    def seen(self, event_id: str, now: int) -> bool:
        self._tick(now)
        dup = event_id in self.cur or event_id in self.prev
        self.cur.add(event_id)
        return dup


d = Deduplicator(m=1 << 16, k=10, window=600)
assert d.seen("evt-1", now=0) is False
assert d.seen("evt-1", now=5) is True            # redelivered within the window
assert d.seen("evt-1", now=700) is True          # still in 'prev' during the next window
assert d.seen("evt-2", now=700) is False
assert d.seen("evt-1", now=1900) is False        # last seen at 700, two windows later: forgotten
print("ok")

Memory is two filters of bits each; with 64 MB total you get bits per filter, which at 14.4 bits/key for 0.1% handles about 18.6 million new events per 10-minute window. The effective window is between 10 and 20 minutes depending on where in the epoch the first delivery landed — state that in the design, since a redelivery at 19 minutes may or may not be caught.

10. Implement a counting Bloom filter and demonstrate the false-negative hazard — add delete, then show that deleting a key that was never inserted (or deleting twice) can make a real member disappear. Teaches why deletion needs discipline.

Hint

4-bit counters in a bytearray (two per byte, or just one per byte for simplicity). Insert a and b whose positions overlap in one cell; delete b twice; query a.

Common mistakes & interview follow-ups

"The data is 100× bigger — what changes?" For a Bloom filter, memory is linear in at a fixed , so 100× the keys is 100× the bits; the question is whether to accept a higher instead. For CMS and HLL nothing changes: memory depends on , and , not on . Say this explicitly — it is the point of sketches.

"How do you pick the false-positive rate?" From the cost of a false positive versus a bit. If a false positive costs one disk read (~100 µs) and you serve negative lookups per second, 1% is 1,000 wasted reads per second (0.1 s of disk time per second). Halving costs 1.44 bits per key; compare that to the read cost at your scale.

"The filter is in a distributed system — where does it live?" Co-locate it with the data it guards (each SSTable, each shard). Filters merge by OR, so a global view can be assembled from shard filters with identical parameters and seeds. Ship the seed in the file header.

"Keys get deleted — now what?" Counting Bloom filter (4× memory), cuckoo filter (deletes, ~same memory), or periodic rebuild from the source of truth (the LSM approach: SSTables are immutable, so their filters never need deletes).

"Can the Count-Min Sketch tell me the count is at least 1,000?" No — it only upper-bounds. If you need a lower bound, either keep exact counters for the current heavy-hitter candidates (Space-Saving does this) or accept that "estimate − " is a probabilistic lower bound with confidence .

Quick quiz

  1. A Bloom filter has bits. What minimises the false-positive rate, and what is that rate?
Answer

, so or . Rate (with : ).

  1. You insert items into a Bloom filter and then query one of them. What is the probability of a false negative?
Answer

Zero. Bits are never cleared, and the query re-derives the same positions that the insert set.

  1. A Count-Min Sketch has , and has seen events. What can you say about an estimate of 1,500,000 for key ?
Answer

, . The true count is at most 1,500,000 and, with probability at least 99.3%, at least . For a key this frequent the estimate is reliable; for a key with a true count of 100 the same sketch would be useless.

  1. Two Redis HLLs each estimate 1,000,000 distinct users. What does PFMERGE of the two estimate, and with what error?
Answer

The size of the union, anywhere from 1,000,000 (identical sets) to 2,000,000 (disjoint), with the same 0.81% standard error as a single HLL — merging is register-wise max and is exact in the sketch sense. It cannot give the intersection directly.

  1. Why does the Kirsch–Mitzenmacher scheme force to be odd?
Answer

If all positions collapse to and the key is protected by a single bit, raising its false-positive exposure from to roughly the fraction of set bits (~50%). Making odd also guarantees the positions are distinct when is a power of two.

Further reading / sources

  • B. H. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM 13(7), 1970. doi:10.1145/362686.362692
  • A. Broder & M. Mitzenmacher, "Network Applications of Bloom Filters: A Survey", Internet Mathematics 1(4), 2004 — the standard survey, including the false-positive derivation and counting filters.
  • A. Kirsch & M. Mitzenmacher, "Less Hashing, Same Performance: Building a Better Bloom Filter", Random Structures & Algorithms 33(2), 2008.
  • P. Bose et al., "On the false-positive rate of Bloom filters", Information Processing Letters 108(4), 2008.
  • F. Putze, P. Sanders & J. Singler, "Cache-, Hash- and Space-Efficient Bloom Filters", WEA 2007 / ACM JEA 2009.
  • B. Fan, D. G. Andersen, M. Kaminsky & M. Mitzenmacher, "Cuckoo Filter: Practically Better Than Bloom", CoNEXT 2014. doi:10.1145/2674005.2674994
  • T. M. Graf & D. Lemire, "Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters", ACM JEA 25, 2020. arXiv:1912.08258
  • G. Cormode & S. Muthukrishnan, "An improved data stream summary: the count-min sketch and its applications", Journal of Algorithms 55(1), 2005.
  • P. Flajolet, É. Fusy, O. Gandouet & F. Meunier, "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm", AofA 2007. S. Heule, M. Nunkesser & A. Hall, "HyperLogLog in Practice", EDBT 2013.
  • A. Z. Broder, "On the resemblance and containment of documents", SEQUENCES 1997.
  • J. Misra & D. Gries, "Finding repeated elements", Science of Computer Programming 2, 1982. A. Metwally, D. Agrawal & A. El Abbadi, "Efficient computation of frequent and top-k elements in data streams", ICDT 2005.
  • B. Maggs & R. Sitaraman, "Algorithmic Nuggets in Content Delivery", ACM SIGCOMM CCR 45(3), 2015.
  • Redis documentation: HyperLogLog data type; RocksDB wiki: RocksDB Bloom Filter.
  • Mitzenmacher & Upfal, Probability and Computing, 2nd ed., §5.5.3 (Bloom filters) and chapter 15 (streaming sketches) — the textbook treatment of the probability used above; see also Probability for Engineers.
  • Archon: Bloom Filters & Probabilistic Data Structures (system-design companion), Hash Tables, Hashing Algorithms, Storage Engines, System Design Math, Cache Sizing Math.

Module 1 navigation. Previous: Hash Tables. Next: Capstone: Build an LRU Cache & Benchmark It. Module overview: Linear Data Structures. Related in this module: Strings in Depth, Arrays & Strings, Advanced Data Structures. Course home: DSA: Zero to Mastery.