📚Before you start

Make sure you're comfortable with Hash Maps & Sets and Heaps & Priority Queues first.

Streaming & Caching Data Structures — Ultimate Reference Guide

A definitive reference for Data Scientists, ML Engineers, AI Researchers, and Backend Engineers working with high-throughput data, LLM serving, recommendation systems, and real-time analytics.

Callout legend: 💡 Expert Insight · ⚠️ Warning · 🧠 Analogy · 🚀 LLM/AI Use Case · 📊 Complexity

LRU Cache
Ring Buffer
Bloom Filter
Count-Min Sketch
Comparative Summary

1. LRU Cache

1.1 Definition & Core Problem

An LRU (Least Recently Used) Cache is a fixed-capacity, in-memory key–value store that, upon reaching capacity, evicts the entry that has gone the longest without being accessed. It enforces a bounded memory footprint while attempting to maximize the hit rate by keeping the temporally hottest items resident.

Core problem solved. Fast storage (RAM, GPU HBM, L1/L2 CPU cache) is small and expensive; the underlying source of truth (disk, network, a recomputation) is large and slow. You cannot keep everything in fast storage. The LRU cache answers the question: "Given a strict memory budget, which items do I keep so that most future requests are served from fast storage?" Its bet is the principle of temporal locality — data accessed recently is likely to be accessed again soon.

Classification.

Deterministic (no probabilistic error — a hit is always exact).
In-memory, bounded-capacity.
An eviction policy (LRU is one of a family: LFU, FIFO, MRU, ARC, CLOCK, 2Q, W-TinyLFU).
Requires O(1) access and O(1) eviction to be practical at scale.

1.2 Intuition & Analogies

🧠 Real-world analogy — the crowded desk. Imagine a small physical desk that holds only 5 documents. Every time you use a document, you place it on top of the pile. When a 6th document arrives and the desk is full, you toss out the one at the bottom — the document you haven't touched in the longest time. The desk always holds your 5 most recently handled documents.

🚀 Domain-specific analogy — the GPU KV cache under memory pressure. During LLM serving, each active sequence holds attention key/value tensors in GPU memory. GPU HBM is tiny relative to demand. A serving system keeps the KV blocks of recently active sequences resident and evicts blocks belonging to sequences that have been idle longest — precisely LRU logic applied to attention state, so that "hot" conversations stay fast while dormant ones spill or recompute.

💡 Expert Insight: "Recently used" is a proxy for "will be used again soon." LRU is optimal only when access patterns exhibit temporal locality. Under a scan (a one-pass sweep over more distinct keys than capacity), that proxy collapses — see §1.5.

1.3 Internal Mechanics & Algorithm

Data model. A correct O(1) LRU cache is the marriage of two structures:

A hash map key → node for O(1) lookup.
A doubly linked list maintaining recency order. The head (or tail, by convention) is the most-recently-used (MRU) end; the opposite end is the least-recently-used (LRU) end — the eviction victim.

Why doubly linked? Because on a hit we must unlink a node from the middle of the list in O(1) and splice it to the MRU end. Removing an arbitrary node in O(1) requires knowing both neighbors, which needs prev and next pointers. A singly linked list would force an O(n) predecessor search.

Operation walkthroughs.

Lookup (get**)**1. Probe the hash map. Miss → return sentinel (-1/None).

Hit → unlink the node from its current position, move it to the MRU end, return its value.

Insert / Update (put**)**1. If key exists → update value, move node to MRU end.

Else create a node, insert at MRU end, add to hash map.
If size > capacity → detach the node at the LRU end, delete its key from the hash map. (Eviction.)

Eviction1. Read the node at the LRU end.

Unlink it (O(1) via the tail sentinel).
Erase its key from the hash map.

💡 Expert Insight: Use sentinel head/tail nodes (dummy nodes that always exist). They eliminate every if node is None branch at the list boundaries, which is where hand-rolled linked-list code almost always has bugs.

Pseudocode.

structure Node: key, value, prev, next

class LRUCache(capacity):
    map = {}                      # key -> Node
    head, tail = Node(), Node()   # sentinels
    head.next = tail; tail.prev = head

    function _remove(node):
        node.prev.next = node.next
        node.next.prev = node.prev

    function _add_to_front(node):          # front = MRU end
        node.next = head.next
        node.prev = head
        head.next.prev = node
        head.next = node

    function get(key):
        if key not in map: return MISS
        node = map[key]
        _remove(node); _add_to_front(node)
        return node.value

    function put(key, value):
        if key in map:
            _remove(map[key])
        node = Node(key, value)
        map[key] = node
        _add_to_front(node)
        if size(map) > capacity:
            lru = tail.prev            # victim
            _remove(lru)
            delete map[lru.key]

Python implementation — idiomatic (OrderedDict). Production Python code should lean on the C-implemented OrderedDict, which is a hash map + doubly linked list internally.

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.cache: OrderedDict = OrderedDict()
        self.capacity = capacity

    def get(self, key):
        if key not in self.cache:
            return None
        self.cache.move_to_end(key)          # mark most-recently-used
        return self.cache[key]

    def put(self, key, value) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)   # evict least-recently-used

# --- runnable demo ---
if __name__ == "__main__":
    c = LRUCache(2)
    c.put(1, "a"); c.put(2, "b")
    assert c.get(1) == "a"     # 1 is now MRU; 2 is LRU
    c.put(3, "c")              # capacity exceeded -> evict key 2
    assert c.get(2) is None    # 2 was evicted
    assert c.get(3) == "c"
    print("OrderedDict LRU: all assertions passed")

Python implementation — explicit doubly linked list (interview / teaching form). This is what OrderedDict does under the hood, spelled out.

class _Node:
    __slots__ = ("key", "val", "prev", "next")
    def __init__(self, key=None, val=None):
        self.key, self.val = key, val
        self.prev = self.next = None

class LRUCacheDLL:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        self.head = _Node()          # sentinel MRU side
        self.tail = _Node()          # sentinel LRU side
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self._remove(node)
        self._add_front(node)
        return node.val

    def put(self, key, val) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = _Node(key, val)
        self.map[key] = node
        self._add_front(node)
        if len(self.map) > self.cap:
            victim = self.tail.prev
            self._remove(victim)
            del self.map[victim.key]

# --- runnable demo ---
if __name__ == "__main__":
    c = LRUCacheDLL(2)
    c.put(1, 1); c.put(2, 2)
    assert c.get(1) == 1
    c.put(3, 3)                 # evicts key 2
    assert c.get(2) is None
    c.put(4, 4)                 # evicts key 1
    assert c.get(1) is None
    assert c.get(3) == 3 and c.get(4) == 4
    print("DLL LRU: all assertions passed")

⚠️ Warning: functools.lru_cache is not a general-purpose cache — it is a memoization decorator keyed on function arguments. It cannot be sized per-key, cannot be invalidated selectively (only cache_clear() wipes everything), and requires hashable arguments. Use it for pure functions; use a real cache object for stateful caching.

1.4 Complexity Analysis

📊

Operation	Time (avg)	Time (worst)	Notes
`get`	O(1)	O(n)*	Hash lookup + O(1) list splice
`put` (insert)	O(1)	O(n)*	Insert + possible O(1) eviction
`put` (update)	O(1)	O(n)*	Value overwrite + O(1) move
Eviction	O(1)	O(1)	Detach LRU-end node via sentinel
Space	O(capacity)	O(capacity)	Map entries + list nodes

Worst case O(n) arises only from hash-map degradation (adversarial collisions / rehash). With a good hash and amortization, all operations are O(1) expected.

💡 Expert Insight: Per-node memory overhead is real. Each entry costs the value plus two pointers (prev/next) plus a hash-map slot. In Python, __slots__ on the node class removes the per-instance __dict__ and can cut node overhead by ~40–50%.

1.5 Edge Cases & Limitations

Scan resistance (the cache-buster). A sequential scan over capacity + 1 distinct keys evicts every useful hot item and yields a 0% hit rate — worse than no cache, because you pay bookkeeping cost for nothing. This is why databases (PostgreSQL, MySQL InnoDB) do not use pure LRU; they use scan-resistant variants (2Q, LRU-K, CLOCK-sweep).
No frequency awareness. An item accessed 1,000 times then idle briefly can be evicted by a burst of one-hit-wonder keys. LFU/W-TinyLFU address this by tracking frequency.
Concurrency. The linked-list mutation on every get makes naive LRU a write-heavy structure — reads mutate shared state. Under multithreading this forces a global lock and becomes a contention bottleneck. (See expert takeaways for the fix.)
Thundering herd / cache stampede. On a miss for a hot key, many threads recompute the same value simultaneously. LRU itself has no request coalescing.
Unbounded key/value size. LRU bounds item count, not bytes. One giant value can blow the memory budget. Size-aware caches bound total bytes instead.

⚠️ Warning: LRU has no time-to-live (TTL) semantics. An item can be served indefinitely as long as it stays hot, even if the underlying data is stale. Correctness-sensitive caches must layer TTL/versioning on top.

1.6 Expert Takeaways

get** mutates — so reads need write locks.** The standard production fix is sharding (partition the keyspace into N independent LRU segments each with its own lock) to reduce contention, or a CLOCK / Second-Chance approximation that replaces the linked-list move with a single atomic "reference bit" set — approximating LRU with far less write traffic. Caffeine (Java) and many CDNs use W-TinyLFU / CLOCK precisely because true LRU's per-read write is a scalability wall.
Amortized recency via sampling. Redis does not implement exact LRU. maxmemory-policy allkeys-lru samples a small number of keys (maxmemory-samples, default 5) and evicts the oldest among the sample — approximate LRU at a fraction of the bookkeeping cost. Raising the sample size trades CPU for eviction accuracy.
Admission control beats eviction policy. W-TinyLFU adds a frequency-based admission filter: a new item is only admitted if it's estimated to be more valuable than the eviction candidate. This single idea (often backed by a Count-Min Sketch — see §4) dramatically raises hit rates over plain LRU on skewed (Zipfian) workloads.
Measure hit rate, not "cache size." The right capacity is where the marginal hit-rate gain per MB flattens. Plot hit rate vs. capacity; the knee is your budget.

💡 Expert Insight: If your workload is Zipfian (a few keys dominate — the norm for web, recsys, and token distributions), a small LRU captures most of the benefit and W-TinyLFU squeezes out the rest. If your workload is uniform or scan-heavy, no recency policy helps — you need more capacity or a different architecture.

1.7 Real-World Applications

DS / Analytics: Feature-store read caches (hot entity features served from RAM instead of a warehouse round-trip); memoized results of expensive aggregation queries; notebook-level result caching.
ML training & serving: Caching decoded/preprocessed samples in a data loader to avoid re-reading and re-parsing from disk each epoch; caching embedding-lookup results for hot IDs in a recommender.
🚀 LLM inference:- Prompt / prefix caching: Reuse the KV state of a shared system prompt or common prefix across requests; LRU decides which cached prefixes stay resident when the prefix cache fills. (vLLM's automatic prefix caching evicts prefix blocks by recency.)
KV-cache block management: In paged-attention serving, physical KV blocks are recycled with recency-aware policies when GPU memory is saturated.
Embedding / retrieval caching: Cache embeddings for frequently seen queries or documents in a RAG pipeline to skip re-encoding.
Distributed systems: CPU caches (hardware approximates LRU with pseudo-LRU trees), CDN edge caches, database buffer pools, DNS resolver caches, HTTP caches.

🚀 LLM Use Case — prefix cache eviction. When many users share a long system prompt, its KV tensors are computed once and cached. As unique prefixes accumulate and GPU memory fills, an LRU-style policy evicts the least-recently-reused prefix blocks — keeping the "hot" shared prompts resident and preserving the latency win of prefix reuse.

1.8 Comparison with Alternatives

Policy	Keeps	Evicts	Scan-resistant?	Frequency-aware?	Best for
LRU	recently used	oldest-untouched	❌	❌	temporal locality workloads
LFU	frequently used	least frequent	⚠️ partial	✅	stable popularity skew
FIFO	newest inserted	oldest inserted	❌	❌	simplicity, no per-access bookkeeping
CLOCK / Second-Chance	ref-bit set	ref-bit clear on sweep	⚠️	❌	low-overhead LRU approximation
ARC	balances recency+frequency	adaptive	✅	✅	mixed, self-tuning (patented)
W-TinyLFU	admission by frequency	LRU within window	✅	✅	modern high-hit-rate caches (Caffeine)
MRU	oldest	most recent	—	❌	when recent items won't be reused (some scans)

When to use LRU: default choice when access shows temporal locality, you need exactness (no false hits), and per-access write cost is acceptable. When not to: scan-heavy or uniform access (add scan resistance), highly skewed with churn (prefer W-TinyLFU), or you need TTL/frequency semantics.

2. Ring Buffer (Circular Buffer)

2.1 Definition & Core Problem

A Ring Buffer (circular buffer, cyclic queue) is a fixed-size array treated as if its ends were joined into a circle, with two indices — a head (read/consume position) and a tail (write/produce position) — that advance modulo the buffer's capacity. When an index reaches the end of the array it wraps around to index 0. It implements a bounded FIFO queue with zero per-element allocation and no data movement.

Core problem solved. A naive queue on a plain array requires shifting all elements on every dequeue (O(n)) or growing unboundedly. A linked-list queue allocates and frees a node per element, thrashing the allocator and destroying cache locality. The ring buffer gives you O(1) enqueue and dequeue, a hard memory ceiling, and contiguous cache-friendly storage — the ideal structure for a producer/consumer boundary where a fast producer and a slower consumer meet across a fixed-size window.

Classification.

Deterministic, bounded-capacity.
Streaming structure — designed for continuous produce/consume flow, not random access.
A FIFO queue with overwrite-or-block-on-full semantics.
The canonical lock-free single-producer/single-consumer (SPSC) data structure.

2.2 Intuition & Analogies

🧠 Real-world analogy — the revolving sushi belt. Chefs (producers) place plates on a circular conveyor; diners (consumers) take them off. The belt has a fixed number of slots. If the belt fills up faster than diners eat, either the chef waits (block) or the oldest untaken plate is removed to make room (overwrite). Nobody ever rearranges the belt — plates just ride around the loop.

🚀 Domain-specific analogy — the token streaming buffer. When an LLM generates tokens faster than the network can flush them to the client (or faster than the UI can render), tokens land in a fixed-size ring buffer. The decoder (producer) writes tokens; the SSE/WebSocket sender (consumer) drains them. The ring decouples the two rates without unbounded memory growth — the bedrock of every streaming-generation pipeline.

💡 Expert Insight: The ring buffer's superpower is decoupling producer and consumer rates while keeping memory bounded. Every real-time pipeline — audio, video, telemetry, token streams — has this shape somewhere.

2.3 Internal Mechanics & Algorithm

Data model. A backing array of size N, plus:

head — index of the next element to read.
tail — index of the next slot to write.
A way to distinguish full from empty, because head == tail is ambiguous (it's true in both states).

The full-vs-empty problem has three standard resolutions:

Keep a count/size** field.** Simplest; empty when count==0, full when count==N. Costs one extra counter that both sides touch (a contention point in concurrent designs).
Sacrifice one slot. Never let the buffer fill completely: full when (tail+1) % N == head. Wastes one slot, needs no counter — common in embedded C.
Use free-running (non-wrapped) indices and mask with & (N-1), requiring N to be a power of two. size = tail - head; empty when head==tail; full when size==N. This is the high-performance approach (used in the Linux kernel kfifo and the LMAX Disruptor) because the mask is a single AND instruction and the indices never need clamping.

Operation walkthroughs.

Enqueue / write (push**)**1. If full then either reject/block (bounded queue) or overwrite by also advancing head (overwriting ring / most-recent-N).

Write element at array[tail].
tail = (tail + 1) % N.

Dequeue / read (pop**)**1. If empty then return sentinel / block.

Read array[head].
head = (head + 1) % N.

**Overwrite (ring-of-last-N mode)**1. On write-when-full, advance head first (drop the oldest), then write and advance tail. The buffer now always holds the most recent N items — the basis of dashcams, flight recorders, and metric sliding windows.

💡 Expert Insight: Choosing a power-of-two capacity turns the modulo (% N) into a bitmask (& (N-1)). Modulo is a division-class instruction (tens of cycles); the mask is ~1 cycle. On a hot streaming path this is a measurable win — and it's why nearly every serious ring buffer forces power-of-two sizing.

Pseudocode.

class RingBuffer(N):        # power of two
    buf  = array(N)
    head = 0                # free-running read index
    tail = 0                # free-running write index
    mask = N - 1

    function size():  return tail - head
    function empty(): return head == tail
    function full():  return size() == N

    function push(x, overwrite=false):
        if full():
            if overwrite: head += 1     # drop oldest
            else: return REJECT
        buf[tail & mask] = x
        tail += 1

    function pop():
        if empty(): return EMPTY
        x = buf[head & mask]
        head += 1
        return x

Python implementation — collections.deque(maxlen=N) (idiomatic overwrite ring). For the "keep the most recent N" use case, the standard library already gives you a C-speed overwriting ring buffer:

from collections import deque

ring = deque(maxlen=4)              # fixed-capacity overwriting ring
for x in range(7):
    ring.append(x)                  # when full, oldest is dropped automatically
assert list(ring) == [3, 4, 5, 6]   # holds the most recent 4
print("deque ring:", list(ring))

Python implementation — explicit power-of-two ring (bounded queue with reject-on-full).

class RingBuffer:
    def __init__(self, capacity: int):
        # round up to the next power of two for mask-based indexing
        n = 1
        while n < capacity:
            n <<= 1
        self._buf = [None] * n
        self._mask = n - 1
        self._head = 0          # free-running read index
        self._tail = 0          # free-running write index

    def __len__(self):
        return self._tail - self._head

    @property
    def capacity(self):
        return self._mask + 1

    def is_empty(self):
        return self._head == self._tail

    def is_full(self):
        return len(self) == self.capacity

    def push(self, x, overwrite: bool = False) -> bool:
        if self.is_full():
            if not overwrite:
                return False                 # reject
            self._head += 1                  # drop oldest
        self._buf[self._tail & self._mask] = x
        self._tail += 1
        return True

    def pop(self):
        if self.is_empty():
            return None
        x = self._buf[self._head & self._mask]
        self._buf[self._head & self._mask] = None   # release reference
        self._head += 1
        return x

# --- runnable demo ---
if __name__ == "__main__":
    rb = RingBuffer(3)                 # rounds up to capacity 4
    assert rb.capacity == 4
    for i in range(4):
        assert rb.push(i) is True
    assert rb.push(99) is False        # full -> rejected
    assert rb.push(99, overwrite=True) # drops oldest (0), writes 99
    assert rb.pop() == 1               # 0 was overwritten
    print("RingBuffer: all assertions passed")

⚠️ Warning: Free-running indices grow without bound. With 64-bit integers this is a non-issue for any realistic runtime, but in fixed-width languages (C/C++ with 32-bit indices) the wraparound of the index itself must be handled — the arithmetic tail - head stays correct across a single unsigned overflow, but comparisons like tail > head do not. Use unsigned modular arithmetic deliberately.

2.4 Complexity Analysis

📊

Operation	Time	Space	Notes
`push` (enqueue)	O(1)	—	Single write + index increment
`pop` (dequeue)	O(1)	—	Single read + index increment
Peek (front)	O(1)	—	`buf[head & mask]`
Random access i	O(1)	—	`buf[(head + i) & mask]`
Search	O(n)	—	No index structure
Space (total)	—	O(N)	Pre-allocated once, never grows

💡 Expert Insight: Ring buffers have the best possible constant factors of any queue: zero allocation after construction, zero data movement, and perfect spatial locality (sequential array access streams through CPU cache lines and triggers hardware prefetch). This is why they dominate latency-critical code — HFT order books, kernel I/O, audio DSP.

2.5 Edge Cases & Limitations

Full-vs-empty ambiguity (see 2.3) — the #1 source of ring-buffer bugs. Pick one resolution and be consistent.
Overwrite silently drops data. In overwrite mode a slow consumer loses the oldest unread items with no error. For telemetry this is acceptable (you want recent data); for financial events it is data loss. Choose block/reject vs. overwrite deliberately per use case.
Fixed capacity is a hard ceiling. If the producer sustainably outpaces the consumer, no ring buffer size saves you — you have a throughput mismatch, not a buffering problem. Sizing only absorbs bursts, not sustained overload.
No random insertion/deletion. It is a queue, not a list. Removing an element from the middle is not an O(1) operation and breaks the model.
False sharing in concurrent rings. If head and tail sit on the same CPU cache line, the producer's write to tail invalidates the consumer's cached head (and vice versa), causing cache-line ping-pong. Fix: pad the two indices onto separate cache lines.

⚠️ Warning: A multi-producer or multi-consumer (MPMC) ring buffer is dramatically harder than SPSC — naive index increments race. You need atomic CAS loops or sequence-number schemes (LMAX Disruptor). Do not take an SPSC ring and add threads; use a purpose-built MPMC queue.

2.6 Expert Takeaways

SPSC lock-free is achievable; MPMC is a research topic. A single-producer/single-consumer ring needs no locks — the producer only writes tail, the consumer only writes head, and with correct memory ordering (acquire/release fences) they never corrupt each other. This is the highest-throughput inter-thread channel there is.
Memory ordering is the real difficulty. On weakly-ordered CPUs (ARM) you must publish the data write before the index update becomes visible, or the consumer reads a slot the producer hasn't filled. Use release on the producer's index store and acquire on the consumer's index load.
Batch to amortize. Reading/writing indices has synchronization cost. Draining/filling in batches (advance the index once per N elements) amortizes that cost and is a core Disruptor optimization.
Pad against false sharing. Align head and tail to separate 64-byte cache lines. This one change can double throughput on a contended ring.

💡 Expert Insight: The LMAX Disruptor — the reference high-performance ring buffer — combines all of the above: power-of-two sizing, pre-allocated slots (no GC churn), cache-line padding, batching, and sequence-number coordination. Studying it is the fastest way to internalize production ring-buffer design.

2.7 Real-World Applications

DS / Analytics: Sliding-window aggregations (last N events for a moving average / rate); reservoir-style recent-event retention; log tailing (dmesg, journald keep the most recent N kernel messages in a ring).
ML training & serving: Replay buffers in reinforcement learning (store the most recent N transitions, overwrite oldest — exactly a ring); batching queues between a data-loading thread and the GPU feed; metric/latency windows for online monitoring.
🚀 LLM inference:- Token streaming: Buffer generated tokens between the decode loop and the network sender (SSE/WebSocket), decoupling generation speed from network flush.
Sliding-window / streaming attention: Architectures like StreamingLLM and sliding-window attention (Mistral) keep only the most recent K token states — a conceptual ring over the KV cache, evicting the oldest positions as new tokens arrive.
Audio streaming ASR/TTS: Real-time speech pipelines ring-buffer PCM audio frames between capture and model inference.
Distributed systems: Kafka partitions are conceptually giant disk-backed ring logs with retention; network card (NIC) RX/TX descriptor rings; kernel pipe buffers; the audio subsystem (ALSA/CoreAudio) DMA rings; UART/serial hardware buffers.

🚀 LLM Use Case — replay buffer for RLHF/online RL. Policy-optimization loops store recent trajectories in a fixed-size ring. New experience overwrites the oldest, keeping the training distribution focused on recent policy behavior while capping memory — the ring's overwrite semantics are the sampling policy.

2.8 Comparison with Alternatives

Structure	Bounded?	Enqueue/Dequeue	Allocation	Random access	Best for
Ring buffer	✅ fixed	O(1) / O(1)	none after init	O(1)	bounded FIFO streaming, SPSC
Dynamic array queue	❌ grows	O(1)* / O(n) naive	amortized realloc	O(1)	unbounded, random access needed
Linked-list queue	❌	O(1) / O(1)	per-element	O(n)	unbounded, no locality need
`deque` (Python)	optional (`maxlen`)	O(1) / O(1)	block-based	O(n) mid	general double-ended queue
Disk log (Kafka)	retention-bounded	O(1) append	segment files	O(1) by offset	durable, replayable streams

When to use a ring buffer: bounded memory is required, the access pattern is FIFO/streaming, and you want zero allocation and maximum cache locality — especially at a single-producer/single-consumer boundary. When not to: you need unbounded growth, frequent mid-sequence insert/delete, or many concurrent producers and consumers (use an MPMC queue or a log).

3. Bloom Filter

3.1 Definition & Core Problem

A Bloom Filter is a space-efficient probabilistic data structure that answers set membership queries — "have I possibly seen this element before?" — with a controllable false-positive rate and zero false negatives. It consists of a bit array of m bits plus k independent hash functions. It stores no elements themselves, only a compressed fingerprint of their presence.

Core problem solved. Exact membership (a hash set) costs memory proportional to the stored elements and their sizes — often hundreds of bits per element. When you have billions of elements, or when the set lives across a slow/expensive medium (disk, network), storing them all in RAM is infeasible. The Bloom filter answers membership using a fixed handful of bits per element (typically ~10 bits for a 1% error rate), independent of element size, at the cost of occasional false positives.

The defining guarantee (memorize this):

"No" is always correct — if the filter says not present, the element was definitely never inserted (no false negatives).
"Yes" is probably correct — if the filter says present, the element is probably inserted, but might be a false positive.

Classification.

Probabilistic, one-sided error (false positives only).
In-memory, fixed-size, insert-only (standard variant supports no deletion).
A membership sketch — trades exactness for radical space savings.

3.2 Intuition & Analogies

🧠 Real-world analogy — the nightclub hand stamp with overlapping ink. Instead of keeping a guest list, the bouncer stamps k spots on a shared grid of m cells for each person who enters, using a per-person pattern. To check if you were here, they look at your k spots. If any is blank, you definitely never entered. If all are stamped, you probably entered — but those spots might have been stamped by other guests whose patterns happened to overlap yours. That overlap is the false positive.

🚀 Domain-specific analogy — skipping the vector DB round-trip. In a RAG system, before issuing an expensive vector-DB or disk lookup for a document ID, consult a Bloom filter of "IDs we have embeddings for." A "no" instantly skips the lookup (guaranteed correct); a "yes" proceeds to the real store. The filter turns a costly I/O into a cheap in-RAM bit-check for the common negative case.

💡 Expert Insight: Beginners think a Bloom filter stores elements. It does not. It stores a lossy union of hash patterns. You can never enumerate its contents or retrieve an element — you can only ask "possibly present?" This is why it's tiny.

3.3 Internal Mechanics & Algorithm

Data model.

A bit array B of length m, all zeros initially.
k independent hash functions h_1 … h_k, each mapping an element to a bit index in [0, m).

Operation walkthroughs.

**Insert(x)**1. Compute the k positions h_1(x) … h_k(x).

Set each of those k bits to 1 (idempotent — already-set bits stay set).

**Query(x) — "might contain"**1. Compute the same k positions.

If all k bits are 1 → return "possibly present".
If any bit is 0 → return "definitely absent".

Delete(x) — not supported in the standard filter. You cannot clear the k bits, because each might be shared by another element; clearing them would introduce false negatives. (Counting Bloom filters, below, add deletion.)

The mathematics of the false-positive rate. This is the heart of the structure.

After inserting n elements into m bits with k hash functions, the probability that a specific bit is still 0 is:

$$P(\text{bit}=0) = \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m}$$

So the probability a bit is 1 is p ≈ 1 - e^{-kn/m}. A false positive occurs when a non-member hashes to k positions that are all already 1:

$$\varepsilon \approx \left(1 - e^{-kn/m}\right)^{k}$$

Optimal k. For fixed m and n, the false-positive rate is minimized when:

$$k^{*} = \frac{m}{n}\ln 2 \approx 0.693 ,\frac{m}{n}$$

Optimal m. To achieve a target error rate ε for n elements, the required bit-array size is:

$$m = -\frac{n \ln \varepsilon}{(\ln 2)^2}$$

which works out to roughly -1.44 log2(ε)** bits per element** — e.g. ~9.6 bits/element for 1%, ~14.4 bits/element for 0.1%, regardless of how large each element actually is.

💡 Expert Insight: At the optimal k, exactly half the bits are set (p = 1/2). If you inspect a production filter and its fill ratio is far from 50%, it's mis-tuned: below 50% wastes space, well above 50% means it's overloaded and ε has ballooned past target.

Pseudocode.

class BloomFilter(m, k):
    B = bitarray(m) all zeros
    hashes = k independent hash functions -> [0, m)

    function add(x):
        for i in 1..k:
            B[ hashes[i](x) ] = 1

    function contains(x):          # "might contain"
        for i in 1..k:
            if B[ hashes[i](x) ] == 0:
                return DEFINITELY_NOT
        return PROBABLY_YES

Python implementation — self-contained, with double hashing. Rather than k distinct hash functions, we use the standard Kirsch–Mitzenmacher technique: derive all k indices from just two base hashes as g_i(x) = (h1 + i*h2) mod m. This is provably as good asymptotically and far cheaper.

import math
import hashlib

class BloomFilter:
    def __init__(self, n_expected: int, false_positive_rate: float = 0.01):
        # optimal sizing from target error rate
        self.m = self._optimal_m(n_expected, false_positive_rate)
        self.k = self._optimal_k(self.m, n_expected)
        self.bits = bytearray((self.m + 7) // 8)   # bit-packed
        self.n = 0

    @staticmethod
    def _optimal_m(n, p):
        return max(1, int(math.ceil(-(n * math.log(p)) / (math.log(2) ** 2))))

    @staticmethod
    def _optimal_k(m, n):
        return max(1, int(round((m / n) * math.log(2))))

    def _two_hashes(self, item):
        data = str(item).encode("utf-8")
        h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
        h2 = int.from_bytes(hashlib.md5(data).digest()[:8], "big")
        return h1, h2

    def _indices(self, item):
        h1, h2 = self._two_hashes(item)
        for i in range(self.k):
            yield (h1 + i * h2) % self.m   # Kirsch-Mitzenmacher double hashing

    def _set(self, idx):
        self.bits[idx >> 3] |= (1 << (idx & 7))

    def _get(self, idx):
        return (self.bits[idx >> 3] >> (idx & 7)) & 1

    def add(self, item):
        for idx in self._indices(item):
            self._set(idx)
        self.n += 1

    def __contains__(self, item):
        return all(self._get(idx) for idx in self._indices(item))

    def current_fpp(self):
        # actual expected false-positive prob given current load
        return (1 - math.exp(-self.k * self.n / self.m)) ** self.k

# --- runnable demo ---
if __name__ == "__main__":
    bf = BloomFilter(n_expected=10_000, false_positive_rate=0.01)
    for i in range(10_000):
        bf.add(f"user_{i}")

    # no false negatives: everything inserted must report present
    assert all(f"user_{i}" in bf for i in range(10_000))

    # measure empirical false-positive rate on never-inserted keys
    fp = sum(f"absent_{i}" in bf for i in range(10_000))
    print(f"m={bf.m} bits, k={bf.k}, bits/elem={bf.m/bf.n:.2f}")
    print(f"empirical FPP={fp/10_000:.4f}  theoretical={bf.current_fpp():.4f}")

⚠️ Warning: The false-positive rate is only valid **up to **n_expected. Every insert past the design capacity monotonically raises ε. There is no automatic resize — the whole point is a fixed bit array. Overfill it and it silently degrades toward "everything is present."

3.4 Complexity Analysis

📊

Operation	Time	Space	Error
Insert	O(k)	—	—
Query (contains)	O(k)	—	FP rate ε; FN rate 0
Delete	❌ unsupported	—	(would cause false negatives)
Space	—	O(m) bits ≈ `-1.44·n·log2(ε)`	independent of element size

k is a small constant (typically 5–15), so insert and query are effectively O(1) — and crucially, independent of the number of elements stored.

💡 Expert Insight: Compare to a hash set: storing 100M 16-byte keys exactly costs ~1.6 GB + overhead. A Bloom filter at 1% error costs ~120 MB — a >10× reduction — and the query is O(k) cache-accesses with no pointer chasing. The savings grow with element size, since the filter's cost is independent of it.

3.5 Edge Cases & Limitations

No deletion in the standard variant (see §3.3). Use a Counting Bloom Filter (each cell is a small counter incremented on add, decremented on delete) if you need removal — at ~4× the space.
Saturation. Once the bit array approaches all-ones (overfilled), every query returns "present" — the filter becomes useless without erroring. Monitor the fill ratio.
No count / no retrieval. It cannot tell you how many times an element was seen, cannot enumerate members, and cannot return the element. (For counts, see Count-Min Sketch, §4.)
Hash quality matters. Correlated or weak hash functions cluster bits and inflate ε beyond theory. Use well-distributed hashes (or double hashing off strong bases).
Union/intersection caveats. Two filters can be unioned with bitwise OR only if they share identical m, k, and hash functions. Intersection via AND is not exact — it over- or under-estimates membership.
Tuning is upfront and irreversible. You must know n in advance. Guess too low and ε blows up; too high and you waste memory. Scalable Bloom Filters (a chain of filters with geometrically growing capacity) address unknown n.

⚠️ Warning: A Bloom filter is not a security primitive. Because non-members can collide to "present," never use a plain Bloom filter as an authorization allow-list — a false positive grants access. And its hashes are typically non-cryptographic, so contents may be probeable.

3.6 Expert Takeaways

Design by error budget, not by feel. Start from the tolerable false-positive rate ε and expected n, then derive m = -n·ln(ε)/(ln2)² and k = (m/n)·ln2. Never hand-pick m and k.
Double hashing is the production default. Kirsch–Mitzenmacher (h1 + i·h2) gives you k indices from two hash computations with no measurable accuracy loss — don't compute k separate cryptographic hashes on the hot path.
The FP rate compounds in pipelines. If you chain filters or query a filter per shard, the effective error is the combination across stages. A 1% filter queried across 100 shards is not 1% overall.
Blocked / register-blocked Bloom filters confine each element's k bits to a single cache line, turning k random memory accesses into one — a large real-world speedup at a slight accuracy cost. This is what high-performance systems (e.g., analytical databases) actually deploy.
Know the successors. A Cuckoo filter or Quotient filter supports deletion, has better cache behavior, and is often smaller at low error rates — consider them when you need deletes or ε < ~0.1%.

💡 Expert Insight: The single most common production incident with Bloom filters is silent overfill: n grows past the design point, ε climbs, and downstream systems mysteriously do more "confirming" work (the false positives fall through to the expensive path). Always alarm on n/n_expected and on the observed fill ratio.

3.7 Real-World Applications

DS / Analytics: Deduplication in streaming pipelines ("have I counted this event/user before?") without storing all IDs; pre-filtering joins to skip keys guaranteed absent; approximate distinct-checks feeding into exact stages.
ML training & serving: Deduplicating training corpora at web scale (has this document/shingle been seen?); feature-store negative caching ("we definitely have no features for this entity — skip the fetch"); filtering already-served recommendations.
🚀 LLM inference & data prep:- Training-data dedup: LLM pretraining corpora are deduplicated with Bloom-filter (and MinHash) pipelines to remove near/exact duplicate documents across trillions of tokens — duplicates hurt model quality and waste compute.
RAG lookup short-circuit: Skip vector-store / KV-store lookups for document IDs guaranteed absent, cutting tail latency on the negative path.
Prompt / prefix cache existence check: Quickly test "do we have a cached prefix for this hash?" before touching the real cache.
Safety / blocklist pre-screening: Cheap first-pass check of tokens/strings against a large blocklist, with a "yes" escalated to an exact check.
Distributed systems: LSM-tree databases (Cassandra, RocksDB, HBase, LevelDB) keep a per-SSTable Bloom filter so a read can skip disk files that definitely don't hold the key — one of the highest-impact uses in all of systems engineering. Also: CDN cache-existence checks, Chrome's historical malicious-URL prefilter, Bitcoin SPV wallets, web-crawler "already visited" sets.

🚀 LLM Use Case — corpus deduplication at scale. Before adding a document to a pretraining set, hash its shingles and query a Bloom filter of already-ingested content. A "no" admits it and inserts; a "yes" routes it to an exact comparison. This removes the overwhelming majority of duplicates in one cheap pass over trillions of tokens, improving downstream model quality.

3.8 Comparison with Alternatives

Structure	Deletion	False positives	False negatives	Space	Counts?
Bloom filter	❌	✅ (tunable ε)	❌ never	~1.44·log2(1/ε) bits/elem	❌
Hash set	✅	❌ none	❌ none	O(elem size)·n (large)	❌
Counting Bloom	✅	✅	❌	~4× Bloom	❌ (only presence)
Cuckoo filter	✅	✅	❌	≈ Bloom, better at low ε	❌
Quotient filter	✅	✅	❌	cache-friendly, mergeable	❌
Count-Min Sketch	➖ (decrement)	over-counts	—	O(w·d)	✅ frequencies

When to use a Bloom filter: membership testing at massive scale where a small, tunable false-positive rate is acceptable, memory is the constraint, and you never need to delete or enumerate. When not to: you need deletion (→ Counting/Cuckoo), exactness (→ hash set), frequencies (→ Count-Min Sketch), or n is unknown/unbounded (→ Scalable Bloom).

4. Count-Min Sketch

4.1 Definition & Core Problem

A Count-Min Sketch (CMS) is a space-efficient probabilistic data structure that estimates the frequency (count) of elements in a stream, using a fixed 2-D array of counters and d hash functions. Where a Bloom filter answers "is it present?", a CMS answers "approximately how many times have I seen it?" — in sublinear space, with a one-sided error: it never undercounts, only overcounts.

Core problem solved. Exact frequency counting (a hash map element → count) grows with the number of distinct elements — untenable for high-cardinality streams (every URL, IP, n-gram, product ID passing through a firehose). CMS gives you frequency estimates in fixed memory independent of cardinality, making "heavy hitters," "top-K," and per-key rate questions answerable on unbounded streams.

The defining guarantee: the estimate is always ≥ the true count (never an undercount), and with probability 1 − δ the overestimate is at most ε·N, where N is the total count in the stream:

$$\hat{f}(x) \ge f(x), \qquad \Pr!\left[\hat{f}(x) \le f(x) + \varepsilon N\right] \ge 1 - \delta$$

Classification.

Probabilistic, one-sided error (over-estimation only).
Streaming, fixed-size, supports increment (and decrement in the turnstile variant).
A frequency / count sketch — the counting cousin of the Bloom filter.

4.2 Intuition & Analogies

🧠 Real-world analogy — tally marks on shared, overlapping sheets. You have d tally sheets, each with w columns. For every event you make one tally mark per sheet, in a column chosen by that sheet's own rule. Different events sometimes share a column (a collision), so a column's tally can be inflated by other events. To estimate one event's count, you read its column on every sheet and take the smallest — the sheet where it suffered the least collision interference is closest to the truth. Since collisions only add marks, the minimum is always an over-estimate, never an under-estimate.

🚀 Domain-specific analogy — token frequency without a giant vocab map. To track how often each token (or n-gram) appears in a massive text stream without materializing a vocab → count dictionary over millions of distinct tokens, a CMS keeps a tiny fixed grid. Frequent tokens (the "heavy hitters") are estimated accurately; the long tail is noisy but cheap. This is exactly what you want for spotting trending tokens/queries.

💡 Expert Insight: The "min" is the entire trick. Every row's counter for x is f(x) plus collision noise from other elements. Noise is always non-negative (counts only go up), so the minimum across rows is the estimate least corrupted by collisions — and provably an upper bound on the truth.

4.3 Internal Mechanics & Algorithm

Data model.

A 2-D counter array of depth d rows × width w columns, all zeros.
d independent hash functions, one per row, each mapping an element to a column in [0, w).
Dimensions from the error targets: w = ⌈e / ε⌉ and d = ⌈ln(1/δ)⌉.

Operation walkthroughs.

Update(x, c) — record c occurrences of x (default c = 1)
1. For each row i in 0…d-1: compute column j = h_i(x).
2. table[i][j] += c.
Estimate(x) — approximate count
1. For each row i: read table[i][h_i(x)].
2. Return the minimum of those d values.
Delete/decrement — supported only in the turnstile model (call update(x, -c)); requires that true counts never go negative, otherwise the min-estimate guarantee breaks.

Why min and not sum/average? Each row independently over-estimates due to collisions. Averaging would fold in every row's noise; the minimum picks the single least-collided estimate. Taking min is what yields the tight one-sided ε·N bound.

Pseudocode.

class CountMinSketch(epsilon, delta):
    w = ceil(e / epsilon)          # width  (columns)
    d = ceil(ln(1 / delta))        # depth  (rows / hashes)
    table = d x w array of zeros

    function update(x, c=1):
        for i in 0..d-1:
            j = hash_i(x) mod w
            table[i][j] += c

    function estimate(x):
        best = +infinity
        for i in 0..d-1:
            j = hash_i(x) mod w
            best = min(best, table[i][j])
        return best

Python implementation — self-contained, salted hashing + heavy-hitter tracking.

import math
import hashlib
import heapq

class CountMinSketch:
    def __init__(self, epsilon: float = 0.001, delta: float = 0.001):
        # epsilon: overestimate <= epsilon * N ;  delta: failure prob
        self.w = int(math.ceil(math.e / epsilon))       # width
        self.d = int(math.ceil(math.log(1.0 / delta)))  # depth
        self.table = [[0] * self.w for _ in range(self.d)]
        self.total = 0

    def _indices(self, item):
        data = str(item).encode("utf-8")
        for i in range(self.d):
            # per-row salt gives d independent hash functions
            h = int.from_bytes(
                hashlib.blake2b(data, digest_size=8,
                                salt=i.to_bytes(2, "big")).digest(), "big")
            yield i, h % self.w

    def update(self, item, count: int = 1):
        for row, col in self._indices(item):
            self.table[row][col] += count
        self.total += count

    def estimate(self, item) -> int:
        return min(self.table[row][col] for row, col in self._indices(item))

    def heavy_hitters(self, candidates, threshold_ratio: float):
        """Return candidates whose estimated freq exceeds threshold_ratio * N."""
        cutoff = threshold_ratio * self.total
        return [(c, self.estimate(c)) for c in candidates
                if self.estimate(c) >= cutoff]

# --- runnable demo ---
if __name__ == "__main__":
    cms = CountMinSketch(epsilon=0.001, delta=0.001)
    # simulate a skewed stream
    stream = (["apple"] * 5000 + ["banana"] * 1200
              + ["cherry"] * 50 + [f"rare_{i}" for i in range(3000)])
    for item in stream:
        cms.update(item)

    for k, true in [("apple", 5000), ("banana", 1200), ("cherry", 50)]:
        est = cms.estimate(k)
        assert est >= true                     # never underestimates
        assert est <= true + 0.001 * cms.total # within epsilon*N bound
        print(f"{k:8s} true={true:5d} est={est:5d} (err={est-true})")
    print(f"N={cms.total}, grid={cms.d}x{cms.w} = {cms.d*cms.w} counters")

⚠️ Warning: Accuracy degrades for low-frequency items. The ε·N error is absolute, scaled by the total stream size — so a key with true count 3 in a stream of 10M can be swamped by collision noise. CMS is a heavy-hitter tool; it is unreliable for the long tail. Do not use it to answer "how many times exactly did this rare key occur?"

4.4 Complexity Analysis

📊

Operation	Time	Space	Error
Update	O(d)	—	—
Estimate	O(d)	—	overest. ≤ ε·N w.p. ≥ 1−δ; never underestimates
Merge (sum two sketches)	O(w·d)	—	exact (same dims/hashes)
Space	—	O(w·d) = O((1/ε)·ln(1/δ))	independent of cardinality

d is a small constant (e.g. ln(1/0.001) ≈ 7), so update/estimate are effectively O(1) and independent of both stream length and distinct-element count.

💡 Expert Insight: The two knobs are orthogonal: width w (∝ 1/ε) controls how tight each estimate is; depth d (∝ ln 1/δ) controls how confident you are of hitting that tightness. Widen the table to reduce error magnitude; deepen it to reduce the probability of a bad estimate. Depth grows only logarithmically in confidence — cheap — so most tuning happens on width.

4.5 Edge Cases & Limitations

Only overestimates. Fine when a slight over-count is safe (rate limiting errs toward caution), dangerous when you bill or make hard cutoffs on the raw estimate.
Long-tail unreliability. As above — absolute error scales with N, drowning rare keys. Pair with a top-K heap or conservative update for better tail behavior.
No enumeration / no distinct count. CMS cannot list which keys it has seen, nor tell you how many distinct keys there were. For cardinality, use HyperLogLog. To find heavy hitters you must supply candidate keys or track them separately (e.g., a companion min-heap).
Hash correlation inflates error. Rows must be independent; reuse the same hash across rows and the min collapses to a single noisy estimate.
Turnstile (decrement) fragility. Allowing decrements is fine only if true counts stay non-negative; otherwise the "min ≥ truth" guarantee is void and estimates can undershoot.

⚠️ Warning: Merging is exact only when both sketches share identical w, d, and hash functions. Merging mismatched sketches silently produces garbage — enforce dimension/seed equality at the API boundary.

4.6 Expert Takeaways

Conservative update (a.k.a. minimal increment). On update, only increment the counters that currently equal the row-minimum for that key. This provably lowers over-estimation (often by a large factor) at zero extra space — a near-free accuracy win that production sketches almost always enable.
Pair CMS with a top-K heap for heavy hitters. CMS alone can't enumerate; the classic "space-saving / heavy-hitters" pattern maintains a small heap of candidate keys and uses the sketch for their counts. This is how trending/top-K is actually built.
Budget from ε and δ, and mind that error scales with N. For a firehose, a fixed ε means growing absolute error as the stream lengthens. Consider windowed/decaying sketches (reset or exponentially decay counts) so old traffic doesn't dominate.
Know its sibling sketches. HyperLogLog for distinct-count (cardinality), CMS for frequency, Bloom for membership, t-digest/KLL for quantiles. Interview and design red flag: reaching for CMS when the question is actually "how many unique?" (that's HLL).

💡 Expert Insight: The interview trap is picking the wrong sketch. Membership → Bloom. "How many unique users?" → HyperLogLog (CMS cannot do this). "How many times did this key appear / who are the top talkers?" → Count-Min Sketch. Frequencies with tight tail accuracy → CMS + conservative update + top-K heap.

4.7 Real-World Applications

DS / Analytics: Heavy-hitter / top-K detection on event streams (most-viewed pages, hottest products); approximate GROUP BY count on unbounded data; per-key rate estimation for anomaly detection; network traffic monitoring (top source IPs, DDoS detection).
ML training & serving: Streaming feature frequency (rare-category detection for encoding decisions); click/impression counting for online recommenders under memory limits; approximate class-balance monitoring on streaming labels; feature-hashing pipelines (CMS is feature hashing's counting relative).
🚀 LLM inference & data pipelines:
- Token / n-gram frequency over massive corpora for vocab analysis, data-quality auditing, and detecting over-represented boilerplate without a full vocab map.
- Trending prompt/query detection in a serving fleet — spot surging query patterns for cache warming or capacity planning.
- Per-tenant / per-key rate limiting & abuse detection at the gateway: approximate request counts per API key in fixed memory across millions of keys.
- Data-mixture auditing: estimate how often documents from a source or a duplicated phrase appear, to rebalance pretraining mixtures.
Distributed systems: Network flow measurement (Cisco/NetFlow-style heavy hitters), database query-optimizer statistics, cache admission policies (W-TinyLFU uses a CMS to estimate access frequency and decide admission — tying §4 back to §1), rate limiters, and log-volume monitoring.

🚀 LLM Use Case — W-TinyLFU prefix-cache admission. A modern LLM prefix/KV cache can gate admission with a Count-Min Sketch of recent access frequencies: when the cache is full, a new prefix is admitted only if the CMS estimates it is accessed more often than the eviction candidate. This frequency-aware admission (backed by a tiny sketch) sharply raises hit rate over plain LRU on the skewed prompt distributions typical of production traffic.

4.8 Comparison with Alternatives

Structure	Answers	Error direction	Distinct count?	Space	Enumerate?
Count-Min Sketch	frequency of a key	overestimate only	❌	O((1/ε)·ln(1/δ))	❌ (needs companion)
Exact hash map	frequency	none	✅	O(distinct keys)	✅
HyperLogLog	# distinct elements	~±1.6/√m relative	✅ (that's its job)	O(m) tiny	❌
Bloom filter	membership (yes/no)	false positives	❌	~1.44·log2(1/ε) bits/elem	❌
Count-Mean-Min / CMS+conservative	frequency, tighter	reduced overest.	❌	≈ CMS	❌
Space-Saving (Stream-Summary)	top-K heavy hitters	bounded	❌	O(K)	✅ (its K keys)

When to use CMS: frequency/heavy-hitter estimation over high-cardinality or unbounded streams, where fixed memory and a one-sided (over-)estimate are acceptable. When not to: you need exact counts (→ hash map), distinct-element counts (→ HyperLogLog), just membership (→ Bloom), or precise long-tail frequencies (→ exact counting or Space-Saving for top-K).

5. Comparative Summary

5.1 Side-by-Side Comparison

Dimension	LRU Cache	Ring Buffer	Bloom Filter	Count-Min Sketch
Category	Eviction policy / cache	Bounded FIFO queue	Membership sketch	Frequency sketch
Deterministic / Probabilistic	Deterministic	Deterministic	Probabilistic (FP only)	Probabilistic (overcount only)
Answers	"value for key" (hot set)	"next/oldest item"	"possibly present?"	"≈ how many times?"
Memory	O(capacity) — full items	O(N) — pre-allocated	O(m) bits (~1.4·log2(1/ε)/elem)	O(w·d) = O((1/ε)ln(1/δ))
Stores actual data?	✅ yes	✅ yes	❌ no	❌ no
Insert / Update	O(1)	O(1)	O(k)	O(d)
Lookup / Query	O(1)	O(1) (front)	O(k)	O(d)
Delete	O(1) (evict)	O(1) (dequeue)	❌ (std) / ✅ counting	➖ turnstile only
Error mode	none (exact)	none; overwrite drops oldest	false positives, no false negatives	overestimate ≤ ε·N, never under
Key tuning knob	capacity; sharding; sample size	capacity (power of 2); overwrite vs block	m, k from (n, ε)	w=e/ε, d=ln(1/δ)
Bounded by	item count	item count	design cardinality n	error targets (not cardinality)
Signature use	KV/prefix cache, buffer pools	token/audio streaming, replay buffers, Kafka	LSM-tree read filter, dedup	heavy hitters, rate limiting, W-TinyLFU

5.2 Decision Guide — "When to Use Which?"

"I need fast repeated access to a bounded hot set of full values." → LRU Cache. Exact values, bounded memory, temporal locality. Add scan resistance / W-TinyLFU if the workload scans or is highly skewed with churn.
"I have a fast producer and a slower consumer and need bounded, allocation-free buffering / the most recent N items." → Ring Buffer. FIFO streaming, zero allocation, great cache locality; overwrite mode for "last N."
"I need to test membership over a huge set and a small false-positive rate is fine, but false negatives are not." → Bloom Filter. Tiny bits-per-element, guaranteed no false negatives, no deletion in the standard form.
"I need approximate frequencies / top talkers over a high-cardinality or unbounded stream in fixed memory." → Count-Min Sketch. Overestimate-only counts; pair with a top-K heap for heavy hitters; use conservative update for tighter tails.
"I need the number of distinct elements." → None of these — use HyperLogLog. (Common trap: CMS counts frequency, not cardinality.)

💡 Expert Insight — they compose. These structures are not rivals; production systems stack them. A modern cache (Caffeine, CDNs) uses an LRU/CLOCK eviction window with a Count-Min Sketch driving W-TinyLFU admission; an LSM-tree database pairs Bloom filters (skip absent SSTables) with ring-buffered write-ahead logs and LRU block caches; an LLM serving stack ring-buffers streamed tokens, LRU-evicts KV/prefix blocks, Bloom-filters dedup during data prep, and can CMS-gate cache admission. Mastery is knowing which guarantee each one gives — exactness, order, membership, or frequency — and combining them so each covers the others' blind spots.

End of reference guide.

Prerequisites: Hash Maps & Sets · Heaps & Priority Queues
See also: Hash Maps & Sets · Heaps & Priority Queues

Section: Domain-Specific DSA · All guides

Table of Contents​

1. LRU Cache​

1.1 Definition & Core Problem​

1.2 Intuition & Analogies​

1.3 Internal Mechanics & Algorithm​

1.4 Complexity Analysis​

1.5 Edge Cases & Limitations​

1.6 Expert Takeaways​

1.7 Real-World Applications​

1.8 Comparison with Alternatives​

2. Ring Buffer (Circular Buffer)​

2.1 Definition & Core Problem​

2.2 Intuition & Analogies​

2.3 Internal Mechanics & Algorithm​

2.4 Complexity Analysis​

2.5 Edge Cases & Limitations​

2.6 Expert Takeaways​

2.7 Real-World Applications​

2.8 Comparison with Alternatives​

3. Bloom Filter​

3.1 Definition & Core Problem​

3.2 Intuition & Analogies​

3.3 Internal Mechanics & Algorithm​

3.4 Complexity Analysis​

3.5 Edge Cases & Limitations​

3.6 Expert Takeaways​

3.7 Real-World Applications​

3.8 Comparison with Alternatives​

4. Count-Min Sketch​

4.1 Definition & Core Problem​

4.2 Intuition & Analogies​

4.3 Internal Mechanics & Algorithm​

4.4 Complexity Analysis​

4.5 Edge Cases & Limitations​

4.6 Expert Takeaways​

4.7 Real-World Applications​

4.8 Comparison with Alternatives​

5. Comparative Summary​

5.1 Side-by-Side Comparison​

5.2 Decision Guide — "When to Use Which?"​

Related Guides​

Table of Contents

1. LRU Cache

1.1 Definition & Core Problem

1.2 Intuition & Analogies

1.3 Internal Mechanics & Algorithm

1.4 Complexity Analysis

1.5 Edge Cases & Limitations

1.6 Expert Takeaways

1.7 Real-World Applications

1.8 Comparison with Alternatives

2. Ring Buffer (Circular Buffer)

2.1 Definition & Core Problem

2.2 Intuition & Analogies

2.3 Internal Mechanics & Algorithm

2.4 Complexity Analysis

2.5 Edge Cases & Limitations

2.6 Expert Takeaways

2.7 Real-World Applications

2.8 Comparison with Alternatives

3. Bloom Filter

3.1 Definition & Core Problem

3.2 Intuition & Analogies

3.3 Internal Mechanics & Algorithm

3.4 Complexity Analysis

3.5 Edge Cases & Limitations

3.6 Expert Takeaways

3.7 Real-World Applications

3.8 Comparison with Alternatives

4. Count-Min Sketch

4.1 Definition & Core Problem

4.2 Intuition & Analogies

4.3 Internal Mechanics & Algorithm

4.4 Complexity Analysis

4.5 Edge Cases & Limitations

4.6 Expert Takeaways

4.7 Real-World Applications

4.8 Comparison with Alternatives

5. Comparative Summary

5.1 Side-by-Side Comparison

5.2 Decision Guide — "When to Use Which?"

Related Guides