Probabilistic data structures

Overview

Probabilistic data structures answer questions about huge data sets using tiny, fixed memory by accepting a small, controlled error. A Bloom filter tests set membership ('definitely not present' or 'probably present'). HyperLogLog estimates the number of distinct items (unique visitors) within about 1% using kilobytes. Count-Min Sketch estimates how often each item appears (heavy hitters).

They matter at scale. Tracking 1 billion unique user IDs exactly needs gigabytes; a HyperLogLog needs about 12 KB. Databases, caches, CDNs, and analytics systems use these structures to skip unnecessary disk reads, count uniques, and find trending items in streams.

When to use it

• Avoiding expensive lookups for items that definitely do not exist.
• Counting unique visitors, searches, or devices at massive scale.
• Finding top-K or trending items in a stream.
• Situations where approximate answers are acceptable and memory is tight.

Where it shows up in interviews

Where it is used in real software

Key terms

False positive

The structure says 'maybe present' when the item is absent (Bloom filter).

False negative

Saying 'absent' when present; Bloom filters never do this.

Bloom filter

Bit array plus k hash functions for membership tests.

HyperLogLog

Estimates cardinality from the maximum run of leading zeros in hashed values.

Count-Min Sketch

Grid of counters giving upper-bound frequency estimates.

How it works, step by step

1. 1
   Choose the question

   Membership (Bloom), distinct count (HyperLogLog), or frequency (Count-Min Sketch).

2. 2
   Choose acceptable error

   For example 1% false positives, which determines memory and hash count.

3. 3
   Hash items

   Use fast, well-distributed hash functions (MurmurHash, xxHash).

4. 4
   Update on each event

   Set bits, update registers, or increment counters in O(1).

5. 5
   Query and verify when needed

   Treat 'maybe' as a hint and confirm with the source of truth if exactness matters.

Exact vs probabilistic

1 billion distinct user IDs (16 bytes each)

Orders-of-magnitude memory savings in exchange for small, bounded, one-sided errors.

Implementation

1// Bloom filter with double hashing2class BloomFilter {3  private bits: Uint8Array;4  constructor(private size: number, private hashes: number) { this.bits = new Uint8Array(Math.ceil(size / 8)); }5 6  private hash(value: string, seed: number) {7    let h = 2166136261 ^ seed;                      // FNV-1a variant8    for (let i = 0; i < value.length; i++) { h ^= value.charCodeAt(i); h = Math.imul(h, 16777619); }9    return h >>> 0;10  }11  private positions(value: string) {12    const h1 = this.hash(value, 0), h2 = this.hash(value, 0x9747b28c) || 1;13    return Array.from({ length: this.hashes }, (_, i) => (h1 + i * h2) % this.size);14  }15  add(value: string) { for (const p of this.positions(value)) this.bits[p >> 3] |= 1 << (p & 7); }16  mightContain(value: string) { return this.positions(value).every((p) => (this.bits[p >> 3] & (1 << (p & 7))) !== 0); }17 18  // Optimal sizing for n items and false-positive rate p19  static forCapacity(n: number, p: number) {20    const m = Math.ceil((-n * Math.log(p)) / Math.LN2 ** 2);21    return new BloomFilter(m, Math.max(1, Math.round((m / n) * Math.LN2)));22  }23}24 25const seen = BloomFilter.forCapacity(1_000_000, 0.01);   // ~1.2 MB26seen.add("https://example.com/a");27seen.mightContain("https://example.com/a"); // true28seen.mightContain("https://example.com/z"); // false (almost always)

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Treating 'maybe present' as certain.

  Fix: Confirm with the source of truth when correctness matters.

• Undersized Bloom filters.

  Fix: False positives explode as the filter fills; size for expected capacity and rebuild as it grows.

Interview questions

Practice problems