Data Structures That Actually Show Up in Production Code

Most data structure material is written for interviews. You memorise that a hash map is O(1), a balanced tree is O(log n), and a graph traversal is O(V + E), you pass the whiteboard round, and then you never think about it again.

Production code works differently. Nobody at a real company asks you to invert a binary tree. What actually happens is that your service starts timing out under load, and it turns out you were doing a linear scan inside a loop. Or your Redis bill triples because you stored ten million small objects in the wrong structure. Or your CI pipeline runs tasks in the wrong order because someone introduced a circular dependency, and the build tool couldn't tell you where.

This chapter covers the three families that show up in nearly every real system — hash maps, trees, and graphs — and shows how they are used in caching layers, HTTP routers, database indexes, package managers, and build systems. Every example is drawn from software you can go and read. Every code sample here was executed before publication, and the performance numbers are measured, not guessed.

Table of Contents

• Learning Objectives
• Prerequisites
• Why This Matters
• First Principles: The Machine Underneath
• Core Concept 1 — Hash Maps
• Core Concept 2 — Trees
• Core Concept 3 — Graphs
• Deep Dive: Internals and Tradeoffs
• Practical Examples
• Production Code Patterns
• Choosing a Structure: Decision Tree
• Comparison Tables
• Common Mistakes
• Real Industry Examples
• Best Practices
• Interview Questions
• Exercises
• Cheat Sheet
• Glossary
• FAQ
• References
• Further Reading

Learning Objectives

After working through this chapter you will be able to:

• Explain what actually happens in memory when you write map[key] = value, and why that determines your service's tail latency.
• Choose between a hash map, a sorted tree, and a trie based on the access pattern rather than on habit.
• Describe why databases use B-trees on disk and LSM trees for write-heavy workloads, and pick correctly between them.
• Implement an O(1) LRU cache, a prefix-tree HTTP router, and a dependency resolver with cycle detection — from scratch, without a library.
• Recognise a graph problem when it is disguised as something else (build ordering, import cycles, permission inheritance, service dependencies).
• Explain consistent hashing and know when hash(key) % N will hurt you.
• Read the source of Redis, Go's runtime, or PostgreSQL and understand the structural decisions being made.
• Answer data structure interview questions with production reasoning instead of memorised complexity tables.

Prerequisites

How to read this: the Core Concepts sections are the foundation. The Deep Dive is what separates someone who uses a hash map from someone who can debug one at 3am. Skip the Deep Dive on a first pass if you like, and come back after the practical examples.

Why This Matters

Here is the honest case for caring, with a measurement rather than an assertion.

The following was run on a standard Linux container with CPython 3.12. One hundred thousand product SKUs, one thousand membership checks:

1000 lookups in a 100k list: 507.0 ms
1000 lookups in a 100k set : 53 µs
ratio: ~9,500x

That is not an academic difference. That is the difference between a request that returns in 60 ms and one that returns in half a second — and it is caused by a single character: [] instead of set(). This exact bug ships constantly, usually as a for loop that checks if item in allowed_items where allowed_items came out of a database as a list.

The same measurement also shows the cost side of the trade:

set container memory : ~4,096 KiB
list container memory:   ~781 KiB

The hash set is roughly five times larger in container overhead. That is the entire discipline in one comparison: you are trading memory for time, and you should know which one you are short of.

Where this knowledge is actually applied

Experienced engineers care about this for one specific reason: structural choices are the hardest thing to change later. You can swap a JSON serialiser in an afternoon. You cannot swap the index type of a 4 TB table without a migration plan, a maintenance window, and a rollback strategy. Getting the shape right early is disproportionately valuable.

First Principles: The Machine Underneath

Before any specific structure, you need three ideas. Everything else in this chapter follows from them.

1. A data structure is a deal about what is cheap

Every data structure makes some operations cheap by making others expensive. There is no structure that is best at everything, and any material that presents one as universally superior is selling something.

An array is a block of memory where element i lives at base_address + i * element_size. Reading element 5,000,000 costs the same as reading element 0 — one arithmetic operation and one memory access. That is why arrays are unbeatable for indexed access. But inserting at the front means shifting every other element right by one, so that operation costs proportionally to the size of the array.

A linked list is the mirror image. Each element holds a pointer to the next one. Inserting anywhere is trivial once you're holding the right node. But finding element 5,000,000 means following five million pointers, each of which may land in a different region of memory.

Neither is "better". They are different deals.

2. Big-O tells you the shape, not the speed

Big-O notation describes how cost grows as input grows. It deliberately discards constant factors.

Discarding constants is what makes the notation useful and also what makes it lie to beginners. A linear scan over a 20-element array is usually faster than a hash lookup, because the array fits in a single CPU cache line region and the hash lookup has to compute a hash, mask it, and chase a pointer. This is why real implementations have small-size special cases: Redis stores small hashes and lists as flat listpacks rather than as hash tables, and only converts to a real hash table past a configured threshold. The asymptotically worse structure wins at small n, so the implementation uses both.

Rule of thumb: below roughly 8–32 elements, "worse" structures often win. Above a few thousand, asymptotics dominate and the constants stop mattering.

3. Memory is not flat — pointer chasing is the hidden cost

Modern CPUs are enormously faster than main memory. To hide that gap they use caches, and they fetch memory in cache lines (64 bytes on x86-64 and most ARM64 chips), not in individual bytes.

The practical consequence: reading data that sits next to data you just read is nearly free. Reading data that sits somewhere random is expensive.

(Latencies are order-of-magnitude figures for typical server hardware; exact values vary by CPU. The ratios are what matter: L1 to RAM is roughly two orders of magnitude.)

This single fact explains design decisions that look arbitrary otherwise:

• Why B-trees have hundreds of children per node instead of two. A binary tree node holds one key; reading it costs a full memory or disk access to use ~16 useful bytes out of a 64-byte cache line or an 8 KB disk page. A B-tree node fills the whole page with keys, so one expensive fetch does hundreds of comparisons' worth of work.
• Why modern hash tables use open addressing. Chained hash tables follow a pointer to a linked list on every collision. Open-addressed tables keep colliding entries in the adjacent array slots, which are usually already in cache.
• Why Go's map implementation changed in Go 1.24. Go replaced its bucket-and-overflow-chain design with a Swiss Table design, storing metadata in a compact control word so probing scans contiguous memory. The Go team reported microbenchmark map operations up to 60% faster, and Datadog reported roughly a 70% reduction in memory for one large production map after the change.

The three questions that pick a structure

Before choosing anything, answer these:

1. How do I look things up? By exact key → hash map. By range or order → tree. By prefix → trie. By relationship → graph.
2. What is the read/write ratio? Read-heavy tolerates expensive writes (indexes, sorted files). Write-heavy needs cheap appends (log-structured designs).
3. Where does it live? In one process's memory, on disk, or across a network? Each boundary changes the answer, because the cost of a "step" changes by orders of magnitude.

Almost every structural mistake in production comes from answering question 1 correctly and forgetting 2 and 3.

Core Concept 1 — Hash Maps

The explanation

A hash map stores key-value pairs in an array. To find where a key goes, you run it through a hash function — a function that turns arbitrary data into a fixed-size number — and use that number to pick an array slot.

slot_index = hash(key) % number_of_slots

That's the entire idea. The array lookup is O(1), the hash computation is O(length of key), and everything else in a hash map implementation exists to handle one problem: two different keys can produce the same slot. This is called a collision, and it is not an edge case. With 23 keys in a 365-slot table you already have a ~50% chance of at least one collision (the birthday paradox). Collisions are the normal condition.

The intuition

Think of a coat check at a large venue. Instead of searching every hook when you return, the attendant hashes your ticket number to a specific rack. Finding your coat takes one step regardless of how many coats are in the building — as long as the racks are reasonably balanced and nobody hands out duplicate tickets.

The two collision strategies

Separate chaining: each slot holds a pointer to a list of entries that landed there. Simple, but every collision costs a pointer dereference into a random memory location.

Open addressing: everything lives in the array. If your slot is taken, you probe the next one (linear probing), or a computed offset (quadratic probing / double hashing), until you find an empty slot. Cache-friendly, but deletion is tricky — you cannot just empty a slot, or you break the probe chains for other keys, so implementations write a tombstone marker instead.

Modern high-performance implementations have converged on open addressing: Google's Abseil flat_hash_map, Rust's standard HashMap (via the hashbrown crate), and Go's map since 1.24 all use Swiss Table–style open addressing. Java's HashMap still uses chaining, for reasons covered in the Deep Dive.

Load factor and resizing

The load factor is entries / slots. As it rises, collisions rise and probe sequences lengthen. Every implementation picks a threshold and grows the array when it is crossed — typically doubling the slot count and rehashing every entry into the new array, because hash(key) % 16 and hash(key) % 32 give different answers.

Java's HashMap grows at a load factor of 0.75 by default. Python's dict resizes when it becomes two-thirds full. Swiss Tables push to roughly 87.5% because their probing is cheap enough to tolerate density.

This matters in production: resizing is an O(n) pause in the middle of an O(1) operation. If you insert a million items into a map that started empty, you pay for roughly twenty full rehashes along the way. This is why almost every language gives you a way to pre-size: make(map[string]int, 1_000_000) in Go, new HashMap<>(expectedSize) in Java, HashMap::with_capacity(n) in Rust. In latency-sensitive services, pre-sizing removes a real source of tail latency.

Redis takes a different approach because it cannot afford a pause: its dictionary keeps two hash tables during a resize and migrates a few buckets on each operation, so no single command blocks for the full rehash. This is a general pattern worth knowing — incremental rehashing trades a bit of complexity and memory for predictable latency.

Real-world example: the cache key space

Every cache you have used is a hash map at its core. Redis stores its entire key space in a dictionary. Memcached does the same. An in-process cache in your application — @lru_cache in Python, Caffeine in Java, sync.Map in Go — is a hash map plus an eviction policy.

The hash map answers "do I have this?" in constant time. The eviction policy answers "what do I throw away when I'm full?" These are two separate problems and they need two separate structures, which is exactly what you will build in the practical examples.

Common misconception

"Hash maps are O(1), so lookups are always fast."

Three ways this is wrong in production:

1. O(1) is amortised and average-case. The worst case for a chained hash map is O(n) — all keys in one bucket. This is not theoretical; it is an attack (see hash flooding, below).
2. Hashing the key is not free. Hashing a 4 KB string costs proportional to 4 KB. If your keys are long, "O(1)" hides a real linear cost. This is why you sometimes see systems hash a fixed prefix, or cache the hash inside the key object — which is exactly what Java's String does with its cached hash field.
3. Order is not guaranteed unless it is documented. Python's dict preserves insertion order and has done since 3.7 as a language guarantee. Go's map deliberately randomises iteration order to stop you depending on it. Java's HashMap gives no ordering; LinkedHashMap does. Writing code that depends on undocumented ordering is a bug that only appears after a runtime upgrade.

Core Concept 2 — Trees

The explanation

A tree is a set of nodes where each node has one parent and any number of children, with one root and no cycles. The property that makes trees useful is that each step down the tree eliminates a large fraction of the remaining possibilities.

A binary search tree keeps everything smaller than a node on its left and everything larger on its right. Finding a value means comparing and descending, halving the search space each time — O(log n) for a tree that is balanced.

The word balanced is doing all the work in that sentence. If you insert 1, 2, 3, 4, 5 into a naive binary search tree in order, you get a linked list wearing a tree costume, and lookups degrade to O(n). Self-balancing trees — red-black trees and AVL trees being the two classics — perform rotations during insertion and deletion to keep the height logarithmic.

The intuition

A tree is a decision procedure. Looking up "Martinez" in a phone book, you don't scan from A. You open near the middle, see you're past M, and go left. Each look eliminates half the book. Twenty such steps get you through a million entries.

Why production trees are wide, not binary

Here is the part interview prep skips. Real systems rarely use binary trees for stored data. They use B-trees and B+ trees, invented by Rudolf Bayer and Edward McCreight in 1970 while they were at Boeing Research Labs.

A B-tree node holds many keys and many child pointers — typically enough to fill one disk page. PostgreSQL uses 8 KB pages by default; MySQL's InnoDB uses 16 KB. With ~100–500 keys per node, the tree gets very shallow:

A billion-row index is four levels deep. The top levels stay cached in memory, so a primary-key lookup on a huge table is typically one or two actual disk reads. That is the single most important performance fact about relational databases, and it is a direct consequence of matching node size to page size.

In a B+ tree — which is what almost every database actually uses — all the real data lives in the leaf nodes, and the leaves are linked together in order. Interior nodes are pure navigation. This is why WHERE created_at BETWEEN ? AND ? is fast on an indexed column: find the first leaf, then walk sideways along the linked leaves. It's also why an index on (a, b) helps a query filtering on a but not one filtering only on b — the tree is sorted by a first, so b alone gives you no way to navigate.

Real-world example: your database's index

When you write:

CREATE INDEX idx_orders_customer ON orders (customer_id, created_at);

PostgreSQL builds a B-tree keyed on the tuple (customer_id, created_at). A query for one customer's recent orders descends the tree to the first matching leaf and reads sequentially. Without the index the database scans every row.

The tradeoff is that the index must be maintained. Every INSERT, UPDATE, or DELETE on an indexed column has to update the tree, which may trigger node splits. This is why a table with fifteen indexes has slow writes, and why the standard advice is to index for the queries you actually run rather than for the ones you might.

Other trees you will meet

• Tries / prefix trees — the path from the root spells out the key. Used for routing, autocomplete, and IP lookup. Covered in depth below.
• Heaps — a tree kept in an array, where the parent is always smaller (or larger) than its children. This is your priority queue: task schedulers, Dijkstra's algorithm, timeout management, heapq in Python.
• Merkle trees — every node holds a hash of its children. Changing one leaf changes the root hash. This is how Git detects what changed, how Cassandra compares replicas without shipping all the data, and how blockchains prove membership.
• Piece trees / ropes — text editors don't store a document as one big string, because inserting a character in the middle of a 50 MB file would copy 50 MB. VS Code stores the document as a balanced tree of pieces pointing into a small number of buffers, so an edit touches a few nodes rather than the whole file.

Common misconception

"Trees are for sorted data; hash maps are for everything else."

The more useful framing is: hash maps destroy order, trees preserve it. A hash map cannot answer "give me all keys between X and Y", "what's the smallest key", or "iterate in sorted order" without scanning everything. If your access pattern includes any of those, you need order, and a hash map is the wrong tool no matter how fast its point lookups are.

This is exactly why Redis sorted sets exist and are implemented as a skip list plus a hash map — the hash map answers "what score does member X have?" in O(1), the skip list answers "give me ranks 100–200" in O(log n + range). Two structures, one logical object, because neither alone covers the access pattern.

Core Concept 3 — Graphs

The explanation

A graph is nodes plus edges. That's it. A tree is a special case (connected, no cycles, one parent per node). A linked list is a very boring graph.

Graphs come in variants that matter:

• Directed vs undirected — does the edge have a direction? "A depends on B" is directed. "A and B are friends" is usually undirected.
• Cyclic vs acyclic — can you follow edges and return where you started? A DAG (directed acyclic graph) is the workhorse of build systems, data pipelines, and package managers, precisely because "no cycles" means "a valid order exists".
• Weighted vs unweighted — do edges carry a cost? Distance, latency, price.

The intuition

If you can say "this relates to that", you have a graph. The skill is recognising graphs when they aren't labelled as such:

Two representations, and why the choice matters

Adjacency matrix — a V×V grid where matrix[i][j] is 1 if there's an edge. Checking whether an edge exists is O(1). Memory is O(V²) whether you use it or not. A million nodes would need a trillion cells. Only viable for small, dense graphs.

Adjacency list — each node holds a list of its neighbours. Memory is O(V + E). Checking a specific edge means scanning that node's list. This is what essentially every real system uses, because real graphs are sparse: a social network user has hundreds of connections, not hundreds of millions.

Real-world example: dependency resolution

You run npm install. The package manager must:

1. Build a graph where each node is a package version and each edge is a requirement.
2. Detect cycles — an import cycle in your own code is a warning, but a cycle in the install graph is a contradiction.
3. Find an order in which every package can be installed after its dependencies. That is topological sort.
4. Resolve conflicts when two packages want incompatible versions of a third.

Step 4 is the hard one, and it is genuinely NP-complete in the general case — version solving can encode boolean satisfiability. Different ecosystems make different tradeoffs. npm historically sidesteps it by allowing multiple copies of a package nested in node_modules. Cargo and Go's module system apply resolution rules that guarantee a single version per major version. Dart's pub, and Python's uv, use PubGrub, a conflict-driven algorithm designed to produce human-readable explanations when resolution fails, rather than the bare "unsatisfiable" a raw SAT solver would emit.

That last point is a good lesson in system design: they didn't pick the fastest algorithm, they picked the one whose failure mode a developer could act on.

Common misconception

"Graph algorithms are for maps and social networks. I'm building a CRUD app."

Every CRUD app has at least one graph in it. Your ORM's cascade-delete order is a topological sort over the foreign key graph. Your module bundler builds an import graph. Your infrastructure-as-code tool builds a resource dependency DAG and executes it in stages. If your framework does it for you, you still need to understand it the day it produces "circular dependency detected" and points at 40 files.

Deep Dive: Internals and Tradeoffs

This section is what separates using a structure from understanding one. Read it once now, and again after you've shipped something that broke.

Inside a modern hash table: Swiss Tables

The design that most new implementations have adopted came out of Google's Abseil library and was presented publicly at CppCon in 2017. The core insight is about memory layout, not about hashing.

A Swiss Table splits the 64-bit hash into two parts:

• H1 — the upper bits, used to pick a starting group of slots.
• H2 — 7 bits, stored in a compact control byte array parallel to the slots.

Each slot has one control byte, which encodes either "empty", "deleted", or "occupied, and here are 7 bits of its hash". Because control bytes are packed contiguously, the CPU can compare a whole group of them at once — Abseil uses SSE2 SIMD instructions to test 16 slots in parallel; Go's implementation packs 8 control bytes into a single 64-bit word and uses bitwise arithmetic (a technique called SWAR — SIMD Within A Register) to achieve the same effect portably.

The payoff: a lookup usually touches one cache line of control bytes, identifies the one or two candidate slots, and does a single full key comparison. Compare that to a chained table, which follows a pointer into unpredictable memory on every collision.

The tradeoff nobody mentions: deletions leave tombstones. In a delete-heavy workload, tombstone density grows and probe sequences lengthen until the table is reorganised. Go's release notes and community reporting both note that deletes got somewhat slower in the Swiss Table implementation while lookups and inserts got substantially faster. If your workload is delete-dominated, benchmark rather than assume.

Why Java's HashMap grows red-black trees inside it

Java's HashMap uses chaining, which means a bucket with many collisions degrades to a linked-list scan. That is an availability problem, not just a performance one.

In 2011, a presentation at the 28th Chaos Communication Congress demonstrated that many web frameworks could be taken down by sending a POST body containing thousands of form parameters engineered to hash to the same bucket. Parsing that body turned an expected O(n) operation into O(n²). A few hundred kilobytes of request could consume minutes of CPU. The class of attack is called hash flooding or algorithmic complexity attack.

Two defences emerged, and both are in production today:

1. Randomised, keyed hashing. SipHash, published by Jean-Philippe Aumasson and Daniel J. Bernstein in 2012, is a fast keyed hash designed for exactly this. The process picks a random key at startup, so an attacker cannot precompute colliding inputs. Python, Ruby, Rust, and Perl all adopted it. In Python you can see this: run python3 -c "print(hash('a'))" twice and you get different answers, unless PYTHONHASHSEED is fixed.
2. Structural degradation limits. Java 8 changed HashMap so that when a single bucket exceeds 8 entries and the table has at least 64 slots, that bucket converts from a linked list into a red-black tree. Worst-case lookup becomes O(log n) instead of O(n). If the bucket shrinks back below 6 entries during a resize, it reverts to a list.

That second mechanism is a lovely piece of engineering: the common case stays cheap, and the pathological case is capped. It's also a reminder that a "hash map" in production is often three structures wearing one interface.

Practical takeaway: if you hash untrusted input — request parameters, JSON keys, user-supplied identifiers — you need either a randomised hash or a bound on how many keys you'll accept. Most modern runtimes give you the first by default. Verify rather than assume, especially in older JVM or Node.js code paths and in any hand-rolled hash function.

B-trees vs LSM trees: the central storage tradeoff

This is the most consequential structural decision in data storage, and it is worth understanding properly.

B-tree (update-in-place). The index is a tree of pages on disk. Writing a row means finding its page, modifying it, and writing that page back. Reads are excellent: a few page fetches, and the data is exactly where the index says. Writes are the problem — updating one 100-byte row rewrites an entire 8 KB or 16 KB page, and the writes land at random offsets across the disk.

LSM tree (log-structured merge). Described by Patrick O'Neil and colleagues in 1996. Writes go to an in-memory sorted structure (a memtable, typically a skip list). When it fills, it is flushed to disk as an immutable sorted file (an SSTable). Background compaction merges these files, discarding overwritten and deleted entries. Writes are sequential and fast. Reads may have to check several files, so each file carries a Bloom filter to skip files that definitely don't contain the key.

The three costs you are trading are sometimes called the RUM conjecture — you can optimise for Read overhead, Update overhead, or Memory/space overhead, but improving two tends to worsen the third.

When to choose which:

• Read-heavy, latency-sensitive, transactional, lots of range queries → B-tree. This is why the default relational databases use it.
• Write-heavy ingest (metrics, events, logs, time series), where you can tolerate occasional compaction-induced latency spikes → LSM.
• Uncertain? B-tree. The predictable latency profile is worth a lot operationally, and PostgreSQL will take you further than most teams expect.

Note on accuracy: exact write amplification factors depend heavily on workload, compaction strategy (leveled vs tiered vs universal), and configuration. Treat any single published number as workload-specific. The directional tradeoff above is stable; the magnitudes are not.

Tries and radix trees: the routing workhorse

A trie (prefix tree) stores keys along the path from the root. To store cat, car, and card, you store c → a → {t, r → {ø, d}}. Lookup cost depends on key length, not on how many keys are stored.

The naive version wastes memory: a chain of single-child nodes for every unique suffix. A radix tree (or compressed trie / PATRICIA trie) merges those chains into single edges labelled with a string. This is what production routers use.

Why this is better than a list of regexes. A regex-based router evaluates patterns one by one — 200 routes means up to 200 regex evaluations per request, and regex engines are not cheap. A radix tree walks the URL once. Cost scales with path depth, which is small and roughly constant, not with route count, which grows with your API. Go's httprouter popularised this approach and the major Go web frameworks adopted it.

The same structure appears wherever prefixes are the natural key:

• IP routing. Finding the route for an address is longest prefix match — 10.0.0.0/8 and 10.1.0.0/16 both match 10.1.2.3, and the more specific one wins. The Linux kernel's IPv4 forwarding table uses a compressed trie (fib_trie) for exactly this.
• Autocomplete and search suggestions. Apache Lucene compiles term dictionaries into finite state transducers — a generalisation of the compressed trie that shares suffixes as well as prefixes, cutting memory dramatically.
• Key-value stores with ordered keys. Redis includes a radix tree implementation (rax) used for stream IDs and cluster key tracking.
• In-memory database indexes. The Adaptive Radix Tree (ART), published by Leis, Kemper and Neumann in 2013, varies node size based on how many children a node actually has, which fixes the memory problem that made tries impractical for general indexing. DuckDB uses ART for its indexes.

Skip lists: the tree that isn't

A skip list, invented by William Pugh in 1990, is a sorted linked list with additional express lanes. Each element is randomly promoted to higher levels with decreasing probability, so higher lanes let you skip large distances. Expected search cost is O(log n).

Why use it instead of a balanced tree, when the guarantee is probabilistic rather than absolute?

1. Implementation simplicity. No rotations, no rebalancing cases. Red-black tree deletion is famously hard to get right; skip list deletion is a few pointer updates.
2. Concurrency. Lock-free and fine-grained-locking skip lists are far easier to build correctly than lock-free balanced trees, because inserts touch a small, local set of pointers. This is why Java ships ConcurrentSkipListMap and why RocksDB's default memtable is a skip list — many threads write to it simultaneously.
3. Range queries are trivial — the bottom level is already a sorted linked list.

Redis uses skip lists for sorted sets, and its author has explained the choice in terms of implementation simplicity, good range-query behaviour, and cache characteristics that were acceptable for the workload. It's a good example of choosing the structure that is easiest to keep correct rather than the one with the best textbook bound.

Probabilistic structures: paying accuracy for memory

Sometimes the right answer is to stop storing the data.

Bloom filter (Burton Bloom, 1970). A bit array plus k hash functions. Adding a key sets k bits. Querying checks those bits: if any is 0, the key is definitely absent; if all are 1, it is probably present. False positives are possible; false negatives are not. It cannot enumerate its contents and standard versions cannot delete.

The measured example later in this chapter stores one million keys in 1.14 MiB with a measured false-positive rate of 1.017% against a 1% target. Storing those keys in a hash set would cost tens of megabytes.

Where this earns its place: RocksDB and Cassandra attach a Bloom filter to each SSTable so a read can skip files that definitely don't contain the key, turning many disk reads into zero. CDNs use them to detect "one-hit wonders" — content requested exactly once — so it isn't wastefully written to cache. That technique is documented in Akamai's published account of the algorithms behind their delivery network.

HyperLogLog (Flajolet et al., 2007). Estimates the number of distinct items in a stream using a small fixed amount of memory, by tracking the longest run of leading zeros observed in hashed values across many registers. Redis implements it: PFADD / PFCOUNT use about 12 KB per counter with a standard error around 0.81%, regardless of whether you counted a thousand items or a billion. Counting unique daily visitors exactly would need to store every visitor ID; HyperLogLog needs 12 KB.

Count-Min sketch (Cormode and Muthukrishnan, 2005). Estimates frequencies rather than distinct counts, in sublinear space, never underestimating. Caffeine — the reference W-TinyLFU cache implementation on the JVM — uses a compact frequency sketch to decide whether an incoming item deserves to displace something already cached. That admission policy is why W-TinyLFU caches typically outperform plain LRU at the same memory budget.

When these are the wrong answer: any time a false positive has a real cost. "Probably in the cache" is fine — a miss just costs a fetch. "Probably has permission" is a security bug. "Probably already charged this customer" is a lawsuit.

Practical Examples

Three builds of increasing difficulty. All code below was executed before publication; the printed outputs are real.

Beginner: an O(1) LRU cache

The problem. You need an in-memory cache with a fixed capacity. When it's full, evict the least recently used entry.

Why the naive version fails. A dict alone can't tell you what was used least recently. Storing a timestamp with each entry and scanning for the minimum makes every eviction O(n) — and evictions happen on every insert once you're full, so a hot cache spends all its time scanning.

The insight. Use two structures. A hash map gives O(1) lookup by key. A doubly linked list gives O(1) reordering — you can unlink a node and move it to the front without touching anything else, provided you already have a pointer to it. The hash map is what gives you that pointer. Neither structure alone can do this; together they're O(1) for everything.

"""O(1) LRU cache: hash map for lookup, doubly linked list for recency order."""

from typing import Any, Hashable, Optional


class _Node:
    __slots__ = ("key", "value", "prev", "next")  # no per-instance dict: ~40% less memory

    def __init__(self, key: Hashable, value: Any) -> None:
        self.key = key
        self.value = value
        self.prev: Optional["_Node"] = None
        self.next: Optional["_Node"] = None


class LRUCache:
    def __init__(self, capacity: int) -> None:
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self._map: dict[Hashable, _Node] = {}
        # Sentinel head/tail remove every null check from the splice logic.
        self._head = _Node(None, None)   # most recently used side
        self._tail = _Node(None, None)   # least recently used side
        self._head.next = self._tail
        self._tail.prev = self._head
        self.hits = 0
        self.misses = 0

    def _unlink(self, node: _Node) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _push_front(self, node: _Node) -> None:
        node.prev = self._head
        node.next = self._head.next
        self._head.next.prev = node
        self._head.next = node

    def get(self, key: Hashable, default: Any = None) -> Any:
        node = self._map.get(key)
        if node is None:
            self.misses += 1
            return default
        self.hits += 1
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key: Hashable, value: Any) -> None:
        node = self._map.get(key)
        if node is not None:
            node.value = value
            self._unlink(node)
            self._push_front(node)
            return
        if len(self._map) >= self.capacity:
            victim = self._tail.prev          # O(1) because the list is doubly linked
            self._unlink(victim)
            del self._map[victim.key]         # keep both structures in sync — always
        node = _Node(key, value)
        self._map[key] = node
        self._push_front(node)

    def __len__(self) -> int:
        return len(self._map)

    def keys_mru_to_lru(self) -> list:
        out, cur = [], self._head.next
        while cur is not self._tail:
            out.append(cur.key)
            cur = cur.next
        return out


if __name__ == "__main__":
    cache = LRUCache(capacity=3)
    for k in ("a", "b", "c"):
        cache.put(k, k.upper())
    cache.get("a")            # 'a' becomes most recently used
    cache.put("d", "D")       # evicts 'b' (least recently used)
    print(cache.keys_mru_to_lru())
    print(cache.get("b", "<evicted>"))
    print(f"hits={cache.hits} misses={cache.misses}")

Output:

['d', 'a', 'c']
<evicted>
hits=1 misses=1

Line-by-line reasoning for the parts that matter:

• __slots__ tells Python not to give each node an instance dictionary. For a cache with a million entries this is a meaningful memory saving, and it's the kind of detail that shows up in real cache implementations.
• The sentinel head and tail nodes mean _unlink and _push_front never have to check for None. Removing branches from the hottest code path is a standard technique — the same trick appears in kernel linked lists.
• victim = self._tail.prev is O(1) only because the list is doubly linked. With a singly linked list you'd need to walk from the head to find the second-to-last node, and the whole design collapses to O(n).
• Deleting from self._map in the same operation as unlinking is not optional. Two structures representing one logical state is the most common source of cache bugs: a node in the map that isn't in the list is a memory leak, and a node in the list that isn't in the map is a phantom eviction.

What production adds on top of this: thread safety (a lock, or sharding by key hash to reduce contention), TTL expiry, size-aware eviction (weighing entries by byte size rather than count), and metrics. Real caches also often replace pure LRU with something smarter — see the note on W-TinyLFU above — because LRU is trivially defeated by a single large scan that evicts your entire working set.

Intermediate: a prefix-tree HTTP router

The problem. Map incoming request paths to handlers, supporting parameters (/users/:id) and catch-alls (/static/*filepath), with match cost that doesn't grow as you add routes.

Why the naive version fails. A list of compiled regexes is O(number of routes) per request, and regex matching has a much higher constant than string comparison. At 300 routes on a hot path, this is measurable.

The insight. Split the path into segments and store them in a tree. Matching walks down one level per segment. Cost depends on path depth (typically 2–5), not on route count.

"""Prefix-tree HTTP router: match cost depends on path depth, not route count."""

from dataclasses import dataclass, field
from typing import Callable, Optional


@dataclass
class Node:
    static: dict[str, "Node"] = field(default_factory=dict)
    param: Optional["Node"] = None      # ":id"   - matches exactly one segment
    param_name: str = ""
    wildcard: Optional["Node"] = None   # "*rest" - matches the remainder
    wildcard_name: str = ""
    handlers: dict[str, Callable] = field(default_factory=dict)  # method -> handler


class Router:
    def __init__(self) -> None:
        self.root = Node()

    def add(self, method: str, pattern: str, handler: Callable) -> None:
        node = self.root
        for segment in [s for s in pattern.strip("/").split("/") if s]:
            if segment.startswith(":"):
                if node.param is None:
                    node.param = Node()
                    node.param_name = segment[1:]
                elif node.param_name != segment[1:]:
                    # Fail loudly at registration, not silently at request time.
                    raise ValueError(
                        f"conflicting parameter names at {pattern!r}: "
                        f"{node.param_name!r} vs {segment[1:]!r}"
                    )
                node = node.param
            elif segment.startswith("*"):
                if node.wildcard is None:
                    node.wildcard = Node()
                    node.wildcard_name = segment[1:]
                node = node.wildcard
                break                    # a catch-all must be the final segment
            else:
                node = node.static.setdefault(segment, Node())
        if method in node.handlers:
            raise ValueError(f"duplicate route {method} {pattern}")
        node.handlers[method] = handler

    def find(self, method: str, path: str):
        segments = [s for s in path.strip("/").split("/") if s]
        return self._walk(self.root, method, segments, {})

    def _walk(self, node: Node, method: str, segments: list[str], params: dict):
        if not segments:
            handler = node.handlers.get(method)
            return (handler, params) if handler else (None, None)

        head, rest = segments[0], segments[1:]

        # 1. Static wins: it is the most specific match and a plain dict lookup.
        child = node.static.get(head)
        if child is not None:
            handler, matched = self._walk(child, method, rest, params)
            if handler:
                return handler, matched

        # 2. Then a single-segment parameter.
        if node.param is not None:
            handler, matched = self._walk(
                node.param, method, rest, {**params, node.param_name: head}
            )
            if handler:
                return handler, matched

        # 3. Finally the catch-all, which swallows every remaining segment.
        if node.wildcard is not None:
            handler = node.wildcard.handlers.get(method)
            if handler:
                return handler, {**params, node.wildcard_name: "/".join(segments)}

        return None, None


if __name__ == "__main__":
    r = Router()
    r.add("GET", "/users", lambda **kw: "list-users")
    r.add("GET", "/users/:id", lambda **kw: f"get-user {kw['id']}")
    r.add("GET", "/users/:id/orders/:order_id", lambda **kw: f"order {kw['order_id']}")
    r.add("GET", "/users/me", lambda **kw: "current-user")
    r.add("GET", "/static/*filepath", lambda **kw: f"file {kw['filepath']}")

    for path in ["/users", "/users/42", "/users/me",
                 "/users/42/orders/9", "/static/css/app.css", "/missing"]:
        handler, params = r.find("GET", path)
        print(f"{path:32} -> {handler(**params) if handler else '404'}")

Output:

/users                           -> list-users
/users/42                        -> get-user 42
/users/me                        -> current-user
/users/42/orders/9               -> order 9
/static/css/app.css              -> file css/app.css
/missing                         -> 404

The critical detail is the priority order in _walk. Static before parameter before wildcard. This is why /users/me resolves to the current-user handler rather than matching :id with the literal string "me". Get this ordering wrong and you ship a router where specific routes are silently shadowed by generic ones — a bug that only surfaces when someone registers a username called me.

The backtracking matters too. If /users/me/settings were requested and no static path existed past me, the walk falls back and tries :id with the value "me". Routers that don't backtrack will return a 404 for paths that a human would expect to match.

Where this differs from production routers. Real implementations like httprouter compress at the character level, not the segment level, so /api/v1/users and /api/v1/orders share the /api/v1/ edge as one node. That saves memory and comparisons at the cost of much fiddlier split logic. The segment-level version above is the right thing to understand first, and is perfectly adequate for most applications.

Advanced: dependency resolution with cycle reporting

The problem. Given packages, build targets, or database tables with dependencies, produce a valid execution order — and when no order exists, tell the user exactly which cycle is at fault.

Why the naive version fails. Recursive resolution without cycle tracking either infinite-loops or blows the stack. Reporting "circular dependency detected" without the path is nearly useless in a repository with 400 modules.

The insight. Two algorithms, used together:

• Kahn's algorithm (1962) for the ordering: repeatedly take nodes with no unmet dependencies, emit them, and decrement their dependents' counters. O(V + E).
• Three-colour DFS for diagnostics: mark nodes white (unvisited), grey (on the current path), black (fully explored). Reaching a grey node means you've found a back edge — a cycle — and the current path is the cycle.

"""Dependency resolution: deterministic topological order + readable cycle errors."""

import heapq
from collections import defaultdict


class CycleError(Exception):
    def __init__(self, cycle: list[str]) -> None:
        super().__init__(" -> ".join(cycle))
        self.cycle = cycle


class DependencyGraph:
    """Adjacency list. edges[a] holds every node that must run AFTER a."""

    def __init__(self) -> None:
        self.edges: dict[str, set[str]] = defaultdict(set)
        self.nodes: set[str] = set()

    def add(self, node: str, depends_on: list[str] | None = None) -> None:
        self.nodes.add(node)
        for dep in depends_on or []:
            self.nodes.add(dep)
            self.edges[dep].add(node)   # dep must be built before node

    def build_order(self) -> list[str]:
        """Kahn's algorithm. O(V + E). Ties broken by name for reproducible builds."""
        indegree = {n: 0 for n in self.nodes}
        for src, targets in self.edges.items():
            for dst in targets:
                indegree[dst] += 1

        ready = [n for n, d in indegree.items() if d == 0]
        heapq.heapify(ready)            # a heap, not a queue: deterministic output

        order: list[str] = []
        while ready:
            node = heapq.heappop(ready)
            order.append(node)
            for dst in sorted(self.edges[node]):
                indegree[dst] -= 1
                if indegree[dst] == 0:
                    heapq.heappush(ready, dst)

        # If we couldn't emit everything, the remainder is trapped in a cycle.
        if len(order) != len(self.nodes):
            raise CycleError(self._find_cycle())
        return order

    def parallel_stages(self) -> list[list[str]]:
        """Group nodes that can run concurrently. Stage i depends only on stages < i."""
        indegree = {n: 0 for n in self.nodes}
        for src, targets in self.edges.items():
            for dst in targets:
                indegree[dst] += 1

        stages, frontier, seen = [], sorted(n for n, d in indegree.items() if d == 0), 0
        while frontier:
            stages.append(frontier)
            seen += len(frontier)
            nxt = []
            for node in frontier:
                for dst in self.edges[node]:
                    indegree[dst] -= 1
                    if indegree[dst] == 0:
                        nxt.append(dst)
            frontier = sorted(nxt)
        if seen != len(self.nodes):
            raise CycleError(self._find_cycle())
        return stages

    def _find_cycle(self) -> list[str]:
        """Iterative DFS with three colours: white (unseen), grey (on stack), black."""
        WHITE, GREY, BLACK = 0, 1, 2
        colour = {n: WHITE for n in self.nodes}
        parent: dict[str, str | None] = {}

        for start in sorted(self.nodes):
            if colour[start] != WHITE:
                continue
            stack = [(start, iter(sorted(self.edges[start])))]
            colour[start] = GREY
            parent[start] = None
            while stack:
                node, children = stack[-1]
                advanced = False
                for child in children:
                    if colour[child] == GREY:            # back edge => cycle
                        cycle, cur = [child], node
                        while cur is not None and cur != child:
                            cycle.append(cur)
                            cur = parent[cur]
                        cycle.append(child)
                        return list(reversed(cycle))
                    if colour[child] == WHITE:
                        colour[child] = GREY
                        parent[child] = node
                        stack.append((child, iter(sorted(self.edges[child]))))
                        advanced = True
                        break
                if not advanced:
                    colour[node] = BLACK
                    stack.pop()
        return []


if __name__ == "__main__":
    g = DependencyGraph()
    g.add("app", depends_on=["ui", "api-client"])
    g.add("ui", depends_on=["design-tokens"])
    g.add("api-client", depends_on=["schema"])
    g.add("schema", depends_on=["design-tokens"])
    g.add("design-tokens")

    print("order :", g.build_order())
    print("stages:", g.parallel_stages())

    broken = DependencyGraph()
    broken.add("auth", depends_on=["session"])
    broken.add("session", depends_on=["user"])
    broken.add("user", depends_on=["auth"])
    try:
        broken.build_order()
    except CycleError as exc:
        print("cycle :", exc)

Output:

order : ['design-tokens', 'schema', 'api-client', 'ui', 'app']
stages: [['design-tokens'], ['schema', 'ui'], ['api-client'], ['app']]
cycle : auth -> user -> session -> auth

Three design decisions worth copying:

1. The heap instead of a plain queue. Any topological order is valid, but a stable one is what makes builds reproducible and diffs reviewable. Sorting ties by name costs O(log V) per pop and buys deterministic output. Build tools care about this a great deal.
2. parallel_stages is the version you actually deploy. A flat order tells you what to run; the staged version tells you what can run simultaneously. In the example, schema and ui are in the same stage — two CPU cores, half the wall-clock time. This is precisely how Bazel, Gradle, Turborepo, and Nx schedule work.
3. The DFS is iterative, not recursive. A recursive DFS on a dependency graph with 10,000 nodes in a deep chain will exhaust the stack. Using an explicit stack costs a few extra lines and removes a whole class of production failure. This applies to every graph traversal you write for real input.

Production Code Patterns

Two patterns that show up constantly in distributed systems and are almost never taught alongside data structures, even though they are data structure problems.

Consistent hashing: a sorted array and a binary search

The problem. You have N cache servers and want to spread keys across them. The obvious approach is server = hash(key) % N.

Why it fails. When N changes — a node dies, you scale up — nearly every key maps somewhere new. Every cache entry is suddenly in the wrong place. The cache hit rate collapses, every miss hits the database, and the database falls over. This failure mode has a name: a thundering herd caused by mass invalidation.

The fix, from Karger et al.'s 1997 paper and later made famous by Amazon's Dynamo: place both servers and keys on a circular hash space. A key belongs to the first server clockwise from it. Removing a server only affects the keys that were between it and its predecessor. Implementationally this is a sorted array plus binary search — not the exotic thing the name suggests.

"""Consistent hashing ring: a sorted array + binary search, not a magic algorithm."""

import bisect
import hashlib
from collections import Counter


class HashRing:
    def __init__(self, nodes: list[str], vnodes: int = 160) -> None:
        self.vnodes = vnodes
        self._ring: list[int] = []          # sorted hash positions
        self._owners: dict[int, str] = {}   # position -> physical node
        for node in nodes:
            self.add(node)

    @staticmethod
    def _hash(key: str) -> int:
        # Non-cryptographic use; only uniformity and stability across processes matter.
        return int.from_bytes(hashlib.blake2b(key.encode(), digest_size=8).digest(), "big")

    def add(self, node: str) -> None:
        # Each physical node gets many positions ("virtual nodes") so that
        # removing one node spreads its load across all survivors, not one neighbour.
        for i in range(self.vnodes):
            pos = self._hash(f"{node}#{i}")
            bisect.insort(self._ring, pos)
            self._owners[pos] = node

    def remove(self, node: str) -> None:
        for i in range(self.vnodes):
            pos = self._hash(f"{node}#{i}")
            idx = bisect.bisect_left(self._ring, pos)
            if idx < len(self._ring) and self._ring[idx] == pos:
                self._ring.pop(idx)
                del self._owners[pos]

    def get(self, key: str) -> str:
        if not self._ring:
            raise RuntimeError("empty ring")
        idx = bisect.bisect(self._ring, self._hash(key)) % len(self._ring)  # wrap around
        return self._owners[self._ring[idx]]


if __name__ == "__main__":
    keys = [f"session:{i}" for i in range(100_000)]

    ring = HashRing(["cache-a", "cache-b", "cache-c", "cache-d"])
    before = {k: ring.get(k) for k in keys}
    print("distribution:", dict(Counter(before.values())))

    ring.remove("cache-c")
    after = {k: ring.get(k) for k in keys}
    moved = sum(1 for k in keys if before[k] != after[k])
    print(f"keys remapped after losing 1 of 4 nodes: {moved / len(keys):.1%}")

    modulo_before = {k: f"cache-{'abcd'[HashRing._hash(k) % 4]}" for k in keys}
    modulo_after = {k: f"cache-{'abd'[HashRing._hash(k) % 3]}" for k in keys}
    moved_mod = sum(1 for k in keys if modulo_before[k] != modulo_after[k])
    print(f"same failure with hash % N:                {moved_mod / len(keys):.1%}")

Output:

distribution: {'cache-a': 23596, 'cache-b': 28773, 'cache-d': 26224, 'cache-c': 21407}
keys remapped after losing 1 of 4 nodes: 21.4%
same failure with hash % N:                74.8%

Losing one of four nodes moves 21% of keys with the ring, versus 75% with modulo. Ideally you'd move exactly 25% — the departed node's share — so 21% is close to optimal, and the small deviation is the virtual-node granularity showing up.

The virtual node count is a real tuning parameter, and the measurements make the tradeoff visible. Running the same distribution test at different vnodes settings:

More virtual nodes means better balance and more memory and slower ring rebuilds. Libraries commonly default to somewhere between 100 and a few hundred. If you see one server running hot in a consistently-hashed cluster, low virtual node count is the first thing to check.

Alternatives worth knowing: rendezvous hashing (highest random weight) computes hash(key, node) for every node and picks the max — no ring to maintain, at O(N) per lookup, which is fine for small N. Maglev hashing, published by Google in 2016 for their network load balancer, builds a fixed-size lookup table that gives near-perfect balance and O(1) lookups, at the cost of a rebuild when membership changes.

Bloom filter with correct sizing

The sizing formulas are the part people get wrong. For n expected items and target false-positive rate p:

• bits needed: m = -n·ln(p) / (ln 2)²
• optimal hash count: k = (m/n)·ln 2

"""Bloom filter: trade a known false-positive rate for a large memory win."""

import hashlib
import math


class BloomFilter:
    def __init__(self, expected_items: int, false_positive_rate: float = 0.01) -> None:
        self.m = math.ceil(-expected_items * math.log(false_positive_rate) / (math.log(2) ** 2))
        self.k = max(1, round((self.m / expected_items) * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)
        self.n = 0

    def _positions(self, key: str):
        # Kirsch-Mitzenmacher: two real hashes simulate k hashes without quality loss.
        digest = hashlib.blake2b(key.encode(), digest_size=16).digest()
        h1 = int.from_bytes(digest[:8], "big")
        h2 = int.from_bytes(digest[8:], "big") | 1     # force odd: guarantees full cycle
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, key: str) -> None:
        for pos in self._positions(key):
            self.bits[pos >> 3] |= 1 << (pos &#x26; 7)      # pos>>3 = byte, pos&#x26;7 = bit
        self.n += 1

    def __contains__(self, key: str) -> bool:
        return all(self.bits[pos >> 3] >> (pos &#x26; 7) &#x26; 1 for pos in self._positions(key))


if __name__ == "__main__":
    n, p = 1_000_000, 0.01
    bf = BloomFilter(n, p)
    print(f"n={n:,} target fp={p:.0%} -> {bf.m:,} bits ({bf.m / 8 / 1024 / 1024:.2f} MiB), k={bf.k}")

    for i in range(n):
        bf.add(f"user:{i}")

    probes = 100_000
    false_positives = sum(1 for i in range(n, n + probes) if f"user:{i}" in bf)
    print(f"measured false-positive rate: {false_positives / probes:.3%}")
    print("false negatives are impossible by construction")

Output:

n=1,000,000 target fp=1% -> 9,585,059 bits (1.14 MiB), k=7
measured false-positive rate: 1.017%
false negatives are impossible by construction

The measured rate lands within 2% of the target, which is what a correct implementation should do. The critical operational fact: the false-positive rate is only what you designed for if the item count stays near what you sized for. Put 5 million items into a filter sized for 1 million and the rate degrades badly — the bit array saturates. Bloom filters do not resize. If your item count is unpredictable, use a scalable variant or size for your ceiling.

Choosing a Structure: Decision Tree

Comparison Tables

Core operations

Deciding between the big three

Common Mistakes

1. Linear search inside a loop

# O(n * m) — this is the single most common performance bug in application code
for order in orders:                     # 10,000 orders
    if order.customer_id in vip_ids:     # vip_ids is a list of 5,000
        apply_discount(order)

Why it happens. in works on both lists and sets, so the code is correct and the bug is invisible in review and in a 20-row test fixture. It only appears at production scale.

Fix. vip_ids = set(vip_ids) before the loop. One line, ~9,500x on the measurement at the top of this chapter.

2. Using a mutable object as a hash key

key = ["user", 42]
cache[key] = value     # TypeError in Python; silent corruption in some other languages

Why it happens. The mental model "a key is just a value" ignores that the hash map stored the entry in a slot chosen by the key's hash. Mutate the key and the entry is now in the wrong slot — findable only by accident.

Fix. Use immutable keys: tuples, frozen dataclasses, strings. Python raises an error; Java and C# will happily let you do it and then lose the entry. If you must key on a mutable object, key on a stable identifier instead.

3. Recursive graph traversal on real data

A recursive DFS over a 50,000-node dependency graph will hit the stack limit. Python's default recursion limit is 1,000. Raising it is not a fix; it just moves the crash to a segfault.

Fix. Use an explicit stack, as in the _find_cycle implementation above. This is why production graph code looks more verbose than textbook code.

4. Building an index you never query

CREATE INDEX idx_a ON t (a);
CREATE INDEX idx_b ON t (b);
CREATE INDEX idx_c ON t (c);   -- "just in case"

Every index is a B-tree the database must maintain on every write. Unused indexes are pure cost: slower writes, more disk, more to keep in memory. PostgreSQL exposes pg_stat_user_indexes so you can see which indexes have never been scanned. Check it before adding more.

5. Assuming iteration order

Go randomises map iteration order deliberately. Python guarantees insertion order for dict (since 3.7) but not for set. Java's HashMap gives no guarantee at all, and its actual order changed between versions. Code that relies on undocumented order works until a runtime upgrade, then fails in a way that looks like data corruption.

Fix. Sort explicitly when order matters, or use a structure that documents it (LinkedHashMap, OrderedDict, BTreeMap).

6. Rebuilding the same structure every call

def is_allowed(role):
    permissions = load_permissions()   # parses config, builds a dict — every call
    return role in permissions

The lookup is O(1); the setup around it is O(n) and runs on every request. Build it once at startup or memoise it. This pattern hides inside ORM relationship loading, config parsing, and regex compilation.

7. Caching without bounds

cache = {}
def get_user(user_id):
    if user_id not in cache:
        cache[user_id] = db.fetch(user_id)   # never evicted
    return cache[user_id]

This is not a cache, it is a memory leak with good intentions. It works in testing and OOM-kills the pod at 3am on a Sunday. Every cache needs a bound: size, TTL, or both.

8. Reaching for a graph database too early

A graph problem does not require a graph database. Adjacency lists in your existing relational database, or a recursive CTE, handle a surprising amount of graph work. Dedicated graph databases earn their operational cost when traversals are deep, variable-length, and central to your product — not when you have an org chart with four levels.

Real Industry Examples

Every example below is drawn from published engineering documentation, papers, or open source you can read. Where a detail is version-specific, the version is stated.

Google — Swiss Tables and Maglev

Google's Abseil C++ library ships flat_hash_map, the open-addressed, SIMD-probed hash table design presented at CppCon 2017. The design has since been adopted well beyond Google: Rust's standard HashMap uses hashbrown, a Swiss Table port, and Go adopted the design for its built-in map in Go 1.24. That's a rare case of one hash table design becoming the industry default across three languages within a decade.

Separately, Google published Maglev, its software network load balancer, at NSDI 2016. Its hashing scheme builds a fixed-size lookup table rather than a ring, giving O(1) backend selection with very even distribution and minimal disruption when backends change.

Go — a runtime map rewrite, and what it cost

Go 1.24 replaced the map implementation wholesale. The Go team reported map operations up to 60% faster in microbenchmarks. Datadog, running the new runtime across a large fleet, published a two-part account: first a memory regression they helped diagnose and fix, then a substantial reduction in memory for a large in-memory routing map once the fix landed — on the order of hundreds of megabytes per process for one high-cardinality map.

The lesson for engineers is less about Swiss Tables and more about method: they measured the change in production, isolated the regression, worked with upstream, and only then quantified the win. That is the correct relationship to have with your runtime's internals.

Redis — different structure per access pattern

Redis is the clearest example of "pick the structure that matches the access pattern", because it exposes the choice as its API:

The small-collection encodings are the underrated part. Redis stores a hash of five fields as a flat listpack, and only promotes it to a real hash table when it exceeds configured thresholds. This is the "asymptotically worse wins at small n" principle, implemented as a production feature.

Meta — the social graph as an explicit graph store

Facebook published TAO (USENIX ATC 2013), a distributed data store built specifically for the social graph. It models data as objects (users, posts, comments) and associations (likes, friendships, tags) — nodes and edges — because the read pattern is overwhelmingly "give me the edges of this node, newest first". A general-purpose relational layout with joins did not serve that pattern at their read volume. The structure was chosen from the query shape, which is exactly the reasoning this chapter argues for.

Git — a content-addressed DAG

Git is a graph you use every day. Commits form a directed acyclic graph; each commit points to a tree; trees point to blobs and other trees. Everything is addressed by the hash of its content, so identical files are stored once no matter how many commits reference them, and any change to a file changes every hash above it.

This structure is why several operations are cheap in a way that surprises people coming from centralised version control: branching is writing a 41-byte file containing a commit hash, and git log is a graph traversal rather than a query against a server.

Databases — B+ trees everywhere, with different page sizes

PostgreSQL, MySQL/InnoDB, SQLite, and SQL Server all use B+ trees for their primary index structures, with page sizes tuned to their assumptions: PostgreSQL defaults to 8 KB blocks, InnoDB to 16 KB pages. InnoDB additionally uses a clustered index, meaning the table's rows physically live in the leaves of the primary key's B+ tree, and secondary indexes store the primary key rather than a row pointer. That's why an InnoDB secondary index lookup can require two tree descents, and why a large or randomly-ordered primary key is disproportionately expensive there.

RocksDB, Cassandra, ScyllaDB — LSM in practice

RocksDB (a Facebook fork of Google's LevelDB) is embedded inside a striking number of systems — it has been used as a storage engine in MySQL (MyRocks), in stream processors, and in countless internal services. Its default memtable is a skip list, chosen for concurrent writes; its SSTables carry Bloom filters to avoid pointless disk reads; compaction strategy is a first-class tuning knob because it directly sets your write amplification and latency profile. Cassandra and ScyllaDB use the same family of structures for the same reason: ingest-heavy workloads where sequential writes matter more than perfectly predictable reads.

Package managers — the same graph, four philosophies

Four teams, one underlying graph problem, four different answers about which cost to pay. That is what "engineering tradeoff" actually looks like.

VS Code — a tree because a string was too slow

VS Code's team published a detailed account of replacing their text buffer implementation. The original stored the document as an array of lines, which was fast for small files and became a problem for large ones — memory overhead from millions of small strings, and expensive resizes on sequential insertion. They moved to a piece tree: a balanced (red-black) tree of pieces, each pointing into a small number of append-only buffers. An edit modifies a few tree nodes instead of touching the document text.

It is a good case study because the writeup is honest about what they got wrong: their initial optimisation targets (insert, delete, search) turned out not to be the hot path once integrated — reading a line's content was.

Search and analytics — bitmaps and automata

Apache Lucene, which powers Elasticsearch and OpenSearch, compiles its term dictionary into finite state transducers — a trie that shares suffixes as well as prefixes — to keep large term dictionaries in memory. For document ID sets, Lucene and analytics engines including Apache Druid and ClickHouse use Roaring bitmaps, which switch representation per 64 K block (array, bitmap, or run-length) based on density. That last idea — change representation based on the data you actually have — is the same principle as Redis listpacks and Java's treeified buckets, applied at a different layer.

Best Practices

1. Choose from the access pattern, not from familiarity. Write down how the data will be read before you decide how to store it. "By ID" means hash map. "Most recent 20" means something ordered. "Everything under this prefix" means a trie. Most bad choices come from reaching for whatever you used last time.

2. Pre-size collections when you know the size. make(map[string]T, n), new ArrayList<>(n), HashMap::with_capacity(n). Free latency improvement, removes rehash spikes from your p99.

3. Use your standard library. std::unordered_map, Python's dict, Java's HashMap, Go's map — these have absorbed decades of tuning, security hardening, and platform-specific optimisation. Write your own only when you have measured that you need something the standard one can't do, and be prepared to maintain it.

4. Bound every cache. Size limit, TTL, or both. Unbounded caches are latent outages. Export hit rate as a metric — a cache with a 3% hit rate is pure overhead and should be deleted.

5. Never trust user input to be well-distributed. If untrusted data becomes hash keys, ensure your runtime uses randomised hashing, and cap the number of keys you'll accept from one request. Both defences are cheap; discovering you needed them during an incident is not.

6. Prefer iteration to recursion for anything with user-controlled depth. Graph traversals, tree walks, JSON parsers, and dependency resolvers all take input whose depth an attacker or a large monorepo controls.

7. Keep derived structures in sync in one place. When two structures represent one logical state — the map and the list in an LRU cache, an index and its table — every mutation must touch both. Put that in one method and never mutate the underlying structures directly from elsewhere.

8. Measure before and after, on realistic data. Structural changes have large constants. Benchmark with production-shaped data volumes and key distributions. A structure that wins on uniform random keys can lose badly on the clustered, prefix-heavy keys real systems produce.

9. Make output deterministic where humans will read it. Topological orders, map iteration in generated code, and cache dumps should be stably sorted. Reproducible builds and reviewable diffs depend on it.

10. Document the invariant, not the implementation. "Entries are ordered most-recently-used first" survives a refactor. "This is a doubly linked list" doesn't.

Interview Questions

Beginner

Q: What's the difference between an array and a hash map, and when would you use each?

An array stores elements in contiguous memory addressed by integer index — O(1) access by position, O(n) to find a value. A hash map stores key-value pairs at positions derived from hashing the key — O(1) average access by key, but no ordering and higher memory overhead. Use an array when you have a natural sequence or need to iterate everything; use a hash map when you look things up by identifier. In practice: a list of orders to render is an array; a lookup from customer ID to customer is a hash map.

Q: Why can't you use a list as a dictionary key in Python?

Because dictionaries place entries in a slot determined by the key's hash, and lists are mutable. Mutating a key after insertion would leave the entry stored in a slot inconsistent with its new hash, making it unfindable. Python enforces this by only allowing hashable (effectively immutable) types. Use a tuple.

Q: What does O(1) "amortised" mean?

Individual operations may be expensive, but the average cost over a sequence is constant. Appending to a dynamic array is O(1) amortised: most appends just write to the next slot, but occasionally the array is full and everything is copied to a larger one. Spread across all appends, the copies average out. It matters in latency-sensitive systems because the occasional expensive operation still shows up in your p99, even though the average looks fine.

Intermediate

Q: Design a cache with O(1) get and put, and LRU eviction.

Hash map from key to node, plus a doubly linked list ordered by recency. get looks up the node in the map, unlinks it, and moves it to the front. put inserts at the front and, if at capacity, removes the node before the tail sentinel and deletes its key from the map. Both structures are required: the map gives O(1) lookup, the doubly linked list gives O(1) reordering and O(1) access to the least recently used element. Full implementation is above.

Follow up with: thread safety (lock or shard), and the fact that pure LRU is defeated by a single sequential scan, which is why production caches often use LFU-style admission instead.

Q: Why do databases use B-trees instead of binary search trees?

Because the unit of I/O is a page, not a byte. A binary tree node holds one key, so reading it wastes most of an 8 KB page fetch. A B-tree node fills a page with hundreds of keys, so the tree is dramatically shallower — a billion rows in four levels instead of thirty. The top levels stay cached, so a lookup costs one or two real disk reads. The same reasoning applies in memory, where the page is a 64-byte cache line.

Q: How would you detect a cycle in a dependency graph, and report it usefully?

Depth-first search with three states per node: unvisited, on the current path, and fully explored. Reaching a node that's on the current path means a back edge, and the current path from that node forward is the cycle — report it. Implement it iteratively with an explicit stack, because real dependency graphs are deep enough to blow the call stack. Kahn's algorithm will also detect a cycle (fewer nodes emitted than exist) but doesn't tell you which nodes are involved, which is why production tools run both.

Q: When would you deliberately choose a worse asymptotic complexity?

When n is small and constants dominate — a linear scan over 16 contiguous elements beats a hash lookup. This isn't hypothetical: Redis stores small collections as flat listpacks, and Java converts a hash bucket to a tree only past 8 entries. Also when the "better" structure has a worse tail: a hash map's O(1) average hides an O(n) worst case that a tree's O(log n) doesn't have.

Senior

Q: Choose between a B-tree and an LSM tree for a new service, and justify it.

Start from the workload. Write-heavy append-mostly ingest (events, metrics, logs) favours LSM: writes are sequential, and read amplification is mitigated with Bloom filters. Read-heavy, transactional, range-scan-heavy workloads favour B-trees: predictable latency, no compaction competing for I/O. Then discuss the operational tradeoff: LSM latency is spiky because compaction runs in the background and competes for disk bandwidth, and space amplification varies with compaction strategy. State the uncertainty honestly — the magnitudes are workload-dependent and should be benchmarked rather than assumed. Default to a B-tree store unless the write profile clearly demands otherwise; predictable latency has real operational value.

Q: A service is intermittently CPU-bound while handling POST requests with large form bodies. What structural failure would you suspect?

Hash flooding. If the framework parses parameters into a hash map with a non-randomised hash function, an attacker can craft thousands of colliding keys and turn insertion into O(n²). Mitigations: randomised keyed hashing (SipHash), a cap on parameter count, and structural degradation limits like Java's treeified buckets. Verify what the runtime and framework actually do rather than assuming they're covered.

Q: You're sharding a cache across servers. Walk through the design.

Reject hash(key) % N immediately: any membership change remaps almost every key and causes a mass cache miss that lands on the database. Use consistent hashing with virtual nodes, or a Maglev-style lookup table. Discuss the virtual node count as a real balance-versus-memory knob — with four servers, 16 virtual nodes each gives a ~73% spread between busiest and quietest, while 1000 gives ~5%. Then cover what the structure doesn't solve: hot keys still overload one shard regardless of how evenly the key space is divided, so you may need replication of hot keys or client-side caching on top.

Q: When is an approximate answer acceptable, and how do you decide?

Ask what a wrong answer costs. Bloom filters, HyperLogLog, and Count-Min sketches trade a bounded error rate for order-of-magnitude memory savings. A false positive in a cache-admission filter costs one unnecessary lookup. A false positive in an authorisation check is a security incident. Distinct-visitor counts for a dashboard tolerate 0.81% error; billing does not. Also check the failure mode: Bloom filters degrade badly if you exceed the item count they were sized for, and they don't resize.

Exercises

Easy

1. Find the linear scan. Take a codebase you work on and search for in (Python), .includes( (JavaScript), or .contains( (Java) inside a loop. For each hit, determine whether the container is a list or a set. Fix one, and measure the before/after with a realistic input size.
2. Prove the resize cost. Insert one million integers into an empty hash map, then into one pre-sized for a million. Time both. Explain the difference in terms of rehashing.
3. Break iteration order. Write a Go program that iterates a map and prints the keys. Run it five times. Then do the same in Python. Explain why the languages differ and which behaviour is safer.
4. Size a Bloom filter. For 10 million items at a 0.1% false-positive rate, compute the memory required and the number of hash functions using the formulas above. Compare against storing the items in a hash set.

Medium

5. Add TTL to the LRU cache. Extend the implementation so entries expire after a configurable duration. Keep get and put O(1) on average. Decide between lazy expiry on access and an active sweeper, and justify your choice in a comment.
6. Extend the router. Add support for a trailing-slash redirect, a HEAD fallback to GET, and a 405 Method Not Allowed response when the path matches but the method doesn't. Note that the last one requires knowing which methods a node has — which is why handlers is a dict rather than a single callable.
7. Detect import cycles. Parse the import statements of a real Python or JavaScript project, build the graph, and report every cycle with its full path. Compare your output to what your bundler or linter reports.
8. Implement rendezvous hashing and compare it against the consistent hashing implementation above on the same 100,000 keys: distribution quality, keys remapped when a node is removed, and lookup cost as node count grows.

Hard

9. Build a mini key-value store with an LSM design. In-memory sorted memtable, flush to sorted files on disk when it exceeds a size threshold, Bloom filter per file, and a compaction pass that merges files and drops overwritten keys. Measure write throughput and read latency before and after compaction. This is the single most instructive project in this list.
10. Write a version solver. Given packages with version constraints, find a satisfying assignment. Start with naive backtracking, then add conflict learning: when a combination fails, record the incompatibility so you never explore it again. Compare the number of versions explored, with and without learning.
11. Implement a Swiss Table. Open addressing, a control byte array with 7 bits of hash, group-wise probing, tombstones on delete. Benchmark against your language's built-in map for lookup, insert, and delete separately — you should be able to reproduce the finding that deletes are the weak spot.

Projects

12. A build orchestrator. Take a monorepo, parse its package manifests into a DAG, compute parallel stages, hash each package's inputs for content-addressed caching, and skip any stage whose inputs are unchanged. You'll have rebuilt the core idea behind Bazel, Turborepo, and Nx.
13. A route-aware API gateway. Radix tree routing, per-route rate limiting backed by a sliding window, and an LRU response cache with proper invalidation. Load-test it and find which structure becomes the bottleneck first.

Cheat Sheet

Pick by access pattern

Complexity quick reference

k = key length

Red flags in code review

• in / .includes() / .contains() on a list inside a loop
• A dictionary that only grows
• Recursive traversal over user-supplied or repository-scale input
• hash(key) % number_of_servers
• A structure rebuilt inside a request handler
• Two structures representing one state, mutated in different places
• An index added "just in case"
• Sorting inside a loop that could sort once outside it

Glossary

Adjacency list — Graph representation where each node stores its neighbours. O(V + E) memory; the standard choice for sparse graphs.

Adjacency matrix — Graph representation as a V×V grid. O(1) edge checks, O(V²) memory. Only practical for small dense graphs.

Amortised complexity — Average cost per operation across a sequence, where individual operations may be much more expensive.

B-tree / B+ tree — A balanced tree with many keys per node, sized to a disk page or cache line. In a B+ tree all values live in the leaves, which are linked for range scans. The standard database index structure.

Bloom filter — Probabilistic set membership structure. Says "definitely not present" or "probably present". No false negatives; no deletions in the standard form.

Cache line — The unit of transfer between memory and CPU cache, typically 64 bytes. Reading adjacent data is nearly free; reading scattered data is not.

Chaining — Collision resolution where colliding entries are stored in a list hanging off the bucket.

Collision — Two different keys producing the same hash bucket. Normal and expected, not an error.

Compaction — Background process in an LSM tree that merges sorted files and discards obsolete entries.

Consistent hashing — Mapping keys and servers onto a hash ring so that adding or removing a server remaps only a small fraction of keys.

DAG (directed acyclic graph) — A directed graph with no cycles. Guarantees a valid topological order exists. Foundation of build systems, pipelines, and Git history.

Fanout — The number of children per node in a tree. High fanout means shallow trees means fewer I/O operations.

Hash flooding — Attack that sends deliberately colliding keys to degrade a hash map to linear behaviour and exhaust CPU.

HyperLogLog — Probabilistic structure estimating the number of distinct elements in fixed memory.

Index (database) — An auxiliary structure, usually a B+ tree, that makes lookups on specific columns fast at the cost of write overhead and storage.

Kahn's algorithm — Topological sort by repeatedly removing nodes with no remaining incoming edges. O(V + E).

Load factor — Entries divided by slots in a hash table. Drives when resizing happens.

LRU (least recently used) — Eviction policy discarding the entry unused for the longest time.

LSM tree (log-structured merge tree) — Storage design where writes go to memory and are flushed to immutable sorted files, merged by compaction. Optimised for write throughput.

Memtable — The in-memory sorted structure at the head of an LSM tree, typically a skip list.

Open addressing — Collision resolution where colliding entries go into other slots of the same array rather than into a chain.

Radix tree (compressed trie / PATRICIA) — A trie where chains of single-child nodes are merged into one edge labelled with a string.

Rehashing — Recomputing positions for every entry after a hash table resize. O(n), and a source of latency spikes.

Skip list — A sorted linked list with probabilistic express lanes. O(log n) expected, simpler to make concurrent than a balanced tree.

SSTable (sorted string table) — An immutable file of sorted key-value pairs, the on-disk unit of an LSM tree.

Tombstone — A marker meaning "deleted". Used in open-addressed hash tables to preserve probe chains, and in LSM trees to record deletions until compaction.

Topological sort — An ordering of a DAG's nodes such that every node comes after everything it depends on.

Trie (prefix tree) — A tree where the path from the root spells out the key. Lookup cost depends on key length.

Virtual node (vnode) — Multiple positions on a hash ring assigned to one physical server, so load spreads evenly and failures distribute across all survivors.

Write amplification — The ratio of bytes actually written to storage versus bytes the application asked to write.

FAQ

Do I need to memorise time complexities? Memorise the shape, not the table. You need to know that hash maps are constant-time on average, trees are logarithmic, and nested loops over the same data are quadratic. The rest you can derive or look up. What you cannot look up in the moment is the instinct that a particular loop is going to be a problem at scale.

Are data structure interviews still relevant if real work uses libraries? Partly. The specific exercises are often unrepresentative, but the underlying judgement is not: choosing between a set and a list, recognising a graph problem, knowing that an unbounded cache is a leak. Learn the structures for the work, and the interviews become a side effect.

Which language should I learn these in? The one you already use. The concepts are identical; only the syntax and the standard library names change. Python is used here because it reads clearly, but a Go, Java, or TypeScript engineer should implement these in their own language — you learn more fighting your own type system than reading someone else's.

When should I write my own data structure instead of using the standard library? Rarely, and only after measuring. Legitimate reasons: you need an operation the standard one doesn't expose (like O(1) access to the least recently used element), you need different memory characteristics, or you're building infrastructure where the structure is the product. Illegitimate reason: you think you can beat a structure that thousands of engineer-hours have been spent tuning.

Is Big-O still useful given how fast modern hardware is? More useful, not less — because data volumes grew faster than clock speeds did. Hardware speed changes the constant factor; it does not change the fact that a quadratic algorithm on ten million records is not going to finish. What modern hardware did change is that memory layout now matters as much as asymptotics, which is why cache-friendly designs like Swiss Tables and B-trees dominate.

What should I learn after this? Concurrent data structures (lock-free queues, concurrent hash maps), persistent/immutable structures (HAMTs, used by Clojure and Immutable.js), and the storage engine internals covered in Designing Data-Intensive Applications. Reading real source code — Redis's dict.c and t_zset.c are unusually approachable — teaches more than any additional textbook.

Should I use a graph database for my graph problem? Usually not at first. Adjacency lists in a relational database, plus recursive CTEs, cover a lot of ground. Graph databases earn their operational cost when deep, variable-length traversals are central to the product, not when you have a hierarchy a few levels deep.

FAQ Schema (JSON-LD)

{
  "@context": "https://schema.org",
  "@type": "FAQPage",
  "mainEntity": [
    {
      "@type": "Question",
      "name": "Do I need to memorise time complexities?",
      "acceptedAnswer": {
        "@type": "Answer",
        "text": "Memorise the shape rather than the table. Knowing that hash maps are constant-time on average, trees are logarithmic, and nested loops over the same data are quadratic covers most practical decisions. The rest can be derived or looked up."
      }
    },
    {
      "@type": "Question",
      "name": "Which data structures are actually used in production code?",
      "acceptedAnswer": {
        "@type": "Answer",
        "text": "Hash maps for caches and key lookups, B+ trees for database indexes, LSM trees for write-heavy stores, radix trees for HTTP and IP routing, heaps for schedulers and priority queues, and directed acyclic graphs for build systems and dependency resolution."
      }
    },
    {
      "@type": "Question",
      "name": "What is the difference between a B-tree and an LSM tree?",
      "acceptedAnswer": {
        "@type": "Answer",
        "text": "A B-tree updates pages in place, giving predictable read latency and good range scans, and is used by PostgreSQL, MySQL InnoDB, and SQLite. An LSM tree buffers writes in memory and flushes them as immutable sorted files merged by background compaction, giving much higher write throughput at the cost of read amplification and latency spikes. RocksDB, Cassandra, and ScyllaDB use LSM trees."
      }
    },
    {
      "@type": "Question",
      "name": "Why is consistent hashing better than hash modulo N?",
      "acceptedAnswer": {
        "@type": "Answer",
        "text": "With hash modulo N, changing the number of servers remaps almost every key, causing mass cache misses. Consistent hashing places servers and keys on a hash ring so that removing one server of four remaps roughly a quarter of keys instead of about three quarters, protecting the backing store from a thundering herd."
      }
    },
    {
      "@type": "Question",
      "name": "When should I use a Bloom filter?",
      "acceptedAnswer": {
        "@type": "Answer",
        "text": "Use a Bloom filter when a membership test must be cheap in memory and a false positive is harmless, such as skipping disk reads for keys that are definitely absent. One million keys fit in about 1.14 MiB at a 1 percent false-positive rate. Never use one where a false positive has a real cost, such as authorisation or billing."
      }
    },
    {
      "@type": "Question",
      "name": "When should I write my own data structure instead of using the standard library?",
      "acceptedAnswer": {
        "@type": "Answer",
        "text": "Only after measuring, and only when you need an operation the standard library does not expose, different memory characteristics, or when the structure itself is the product. Standard library implementations have absorbed decades of tuning and security hardening."
      }
    }
  ]
}

References

Papers

• Bayer, R. and McCreight, E. (1970). Organization and Maintenance of Large Ordered Indices. The original B-tree paper.
• Bloom, B. H. (1970). Space/Time Trade-offs in Hash Coding with Allowable Errors. Communications of the ACM.
• Karger, D. et al. (1997). Consistent Hashing and Random Trees. ACM STOC.
• Thaler, D. and Ravishankar, C. (1998). Using Name-Based Mappings to Increase Hit Rates. IEEE/ACM Transactions on Networking. (Rendezvous hashing.)
• O'Neil, P., Cheng, E., Gawlick, D., O'Neil, E. (1996). The Log-Structured Merge-Tree (LSM-Tree). Acta Informatica.
• Pugh, W. (1990). Skip Lists: A Probabilistic Alternative to Balanced Trees. Communications of the ACM.
• Bagwell, P. (2001). Ideal Hash Trees. EPFL. (Hash array mapped tries.)
• Pagh, R. and Rodler, F. (2001). Cuckoo Hashing.
• Flajolet, P., Fusy, É., Gandouet, O., Meunier, F. (2007). HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm.
• Cormode, G. and Muthukrishnan, S. (2005). An Improved Data Stream Summary: The Count-Min Sketch and its Applications. Journal of Algorithms.
• Aumasson, J.-P. and Bernstein, D. J. (2012). SipHash: a fast short-input PRF.
• Leis, V., Kemper, A., Neumann, T. (2013). The Adaptive Radix Tree: ARTful Indexing for Main-Memory Databases. IEEE ICDE.
• Bronson, N. et al. (2013). TAO: Facebook's Distributed Data Store for the Social Graph. USENIX ATC.
• Eisenbud, D. E. et al. (2016). Maglev: A Fast and Reliable Software Network Load Balancer. USENIX NSDI.
• Athanassoulis, M. et al. (2016). Designing Access Methods: The RUM Conjecture. EDBT.
• Einziger, G., Friedman, R., Manes, B. (2017). TinyLFU: A Highly Efficient Cache Admission Policy.
• Chambi, S. et al. (2016). Better bitmap performance with Roaring bitmaps. Software: Practice and Experience.
• Bast, H. et al. (2016). Route Planning in Transportation Networks. Survey of shortest-path techniques used in production routing.
• DeCandia, G. et al. (2007). Dynamo: Amazon's Highly Available Key-value Store. SOSP.
• Maggs, B. and Sitaraman, R. (2015). Algorithmic Nuggets in Content Delivery. ACM SIGCOMM CCR.

Official documentation and engineering write-ups

• Go Blog — Faster Go maps with Swiss Tables: https://go.dev/blog/swisstable
• Datadog Engineering — How Go 1.24's Swiss Tables saved us hundreds of gigabytes: https://www.datadoghq.com/blog/engineering/go-swiss-tables/
• Abseil — Swiss Tables design notes: https://abseil.io/about/design/swisstables
• VS Code Blog — Text Buffer Reimplementation: https://code.visualstudio.com/blogs/2018/03/23/text-buffer-reimplementation
• PostgreSQL Documentation — Index Types and B-Tree Indexes: https://www.postgresql.org/docs/current/indexes-types.html
• MySQL Documentation — InnoDB Index Types: https://dev.mysql.com/doc/refman/8.4/en/innodb-index-types.html
• Redis Documentation — Data types and Memory optimization: https://redis.io/docs/latest/develop/data-types/
• RocksDB Wiki — RocksDB Overview and Compaction: https://github.com/facebook/rocksdb/wiki
• uv Documentation — Resolver internals: https://docs.astral.sh/uv/reference/internals/resolver/
• PubGrub — Version solving algorithm: https://github.com/dart-lang/pub/blob/master/doc/solver.md
• Git Documentation — Git Internals: Git Objects: https://git-scm.com/book/en/v2/Git-Internals-Git-Objects
• MDN Web Docs — Map and Set: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map
• Python Documentation — Data model and PYTHONHASHSEED: https://docs.python.org/3/reference/datamodel.html
• Caffeine — Efficiency and design notes: https://github.com/ben-manes/caffeine/wiki/Efficiency
• Apache Lucene — Finite state transducers in the terms dictionary: https://lucene.apache.org/core/

Books

• Kleppmann, M. Designing Data-Intensive Applications (2nd edition, 2025). Chapter on storage and retrieval covers B-trees versus LSM trees better than any other single source.
• Petrov, A. Database Internals (O'Reilly, 2019). Detailed treatment of B-trees, LSM trees, and distributed storage.
• Sedgewick, R. and Wayne, K. Algorithms (4th edition). The standard reference, with excellent visualisations.
• Cormen, T. et al. Introduction to Algorithms (4th edition, 2022). The formal reference. Use it as a dictionary, not a novel.
• Gregg, B. Systems Performance (2nd edition, 2020). For the measurement discipline that should accompany every structural change.

Further Reading

• Read source code. Redis's dict.c, t_zset.c, and rax.c are unusually readable for production C. Go's runtime/map_swiss.go documents its design decisions in comments. Java's HashMap source has explanatory notes about the treeification thresholds.
• Concurrent structures. Java's ConcurrentHashMap and ConcurrentSkipListMap, Go's sync.Map, and the Rust crossbeam crate. Concurrency changes every tradeoff in this chapter.
• Persistent (immutable) structures. Bagwell's HAMT paper, then Clojure's persistent vectors and Immutable.js. Essential background for functional programming and for understanding how React-era state management avoids copying.
• Storage engines. Build the mini-LSM from the exercises, then read the RocksDB tuning guide. Nothing teaches write amplification like watching your own compaction thrash.
• Cache policies. The TinyLFU paper and the Caffeine efficiency wiki, which contains hit-rate comparisons across policies on real traces.