Which data structure for which problem

Most data structure material is organised by the structure: here is the tree, here is the heap, here are the operations.

That is useful for studying and useless for deciding. In practice, you have a problem, not a structure. This article flips the order.

"I need to find by exact key, very fast"#

Hash table. Constant time to insert, look up and remove.

The cost: no ordering at all. You lose ranges, sorting, smallest, largest, previous and next.

And two details that show up in production: when the table fills up it doubles and rehashes everything, which explains that sporadic latency spike. And the quality of the hash function matters: a bad hash concentrates collisions and degrades to linear time.

"I need ranges, ordering or neighbours"#

Balanced search tree. Logarithmic for everything, and ordering comes free.

AVL is more rigidly balanced, better for read-heavy work. Red-black is looser, with fewer rotations on writes: it is what most standard libraries use.

Skip list is an elegant alternative: linked lists at several levels, with probabilistic balancing. Performance close to a tree, a far simpler implementation, and easier to make concurrent. It is what Redis uses for sorted sets.

And on disk, the answer is a B+tree, for the reasons in the previous article.

"I always need the smallest (or the largest)"#

Heap, or priority queue. Insert and remove the extreme in logarithmic time; peek at the extreme in constant time.

Where it shows up: task schedulers, Dijkstra's algorithm, "the top N" of a stream, system timers.

A useful detail: to keep the top N of a huge stream, you use a heap of size N: constant memory, independent of the size of the stream.

"I need autocomplete or prefixes"#

Trie, the prefix tree. Each node is a character; shared paths save space and prefix search is natural.

The cost is memory, and it is significant. Compressed variants (radix tree, PATRICIA tree) solve part of that.

Where it shows up: autocomplete, IP routing, word dictionaries.

"I need to know whether I have seen this before, with little memory"#

Bloom filter. It answers "definitely not" or "maybe". About ten bits per element for a one per cent false positive rate.

The mental pattern: a cheap filter before the expensive operation. Before going to disk, before calling the API, before querying the remote cache.

Where it shows up: LSM-trees, CDNs, malicious URL checks in the browser.

"I need to count distinct things at an absurd scale"#

HyperLogLog. It estimates cardinality (how many unique values) with about two per cent error using a few kilobytes, regardless of whether the set has a thousand or a billion elements.

Counting unique visitors exactly requires storing every identifier. HyperLogLog trades precision for memory, and for product metrics that trade is almost always a good one.

Count-Min Sketch is the cousin: it estimates the frequency of each item, also in fixed space. It is for finding the most frequent items in a stream: the most viewed products, the most active IPs.

Both overestimate and never underestimate, which is a useful property to know when reading the number.

"I need to compare two large sets and find the difference"#

Merkle tree. A tree of hashes, where each node is the hash of its children. Comparing the roots tells you whether anything changed. Descending the branches that diverge tells you exactly what, without comparing everything.

Where it shows up: replica synchronisation in Cassandra and DynamoDB, Git, blockchains, file sync.

"I need relationships"#

Graph, and the choice of representation matters more than it seems.

Adjacency list (each node stores its neighbours): memory efficient for sparse graphs, which is almost always the case. It is the default choice.

Adjacency matrix: answers "is there an edge between A and B" in constant time, and takes quadratic space. Only worth it for dense, small graphs.

"I need a high-throughput queue between threads"#

Ring buffer: a fixed-size circular array. No allocation, no garbage, and friendly to the processor's cache because the memory is contiguous.

Combined with atomic operations, it enables a lock-free queue. It is the basis of the LMAX Disruptor, which processed millions of messages per second on a single thread.

1. Hash tableexact keyConstant time. The cost is losing all ordering: ranges, sorting, previous and next.
2. Balanced treeranges and orderLogarithmic for everything, and ordering comes free. On disk it becomes a B+tree.
3. Heapthe extremeSmallest or largest in constant time. The top N of a stream fits in a heap of size N.
4. TrieprefixesAutocomplete and IP routing. The cost is memory, and it is significant.
5. Bloom filterhave I seen this?Definitely not, or maybe. A cheap filter before the expensive operation.
6. HyperLogLoghow many uniqueCardinality within 2% using a few kilobytes, whether it is a thousand or a billion elements.
7. Merkle treewhat changedCompare the roots, descend only the diverging branches. It is Git and replica sync.

What you already use underneath#

It is worth noticing how much of this is already in your day:

→ Your language's dictionary is a hash table.

→ Your database index is a B+tree.

→ Redis sorted sets are skip lists.

→ Git is a Merkle tree with content hashes.

→ IP routing is a trie.

→ The operating system scheduler uses a heap or a tree.

→ Cassandra uses an LSM-tree with Bloom filters and Merkle trees.

You will implement almost none of them. But knowing the names changes how you read documentation, choose a tool and explain a decision.

The question that solves an interview, and a project#

When somebody asks you to pick a structure, the good answer does not start with a name. It starts with three questions:

1. Which operations are frequent? Lookup by key, by range, insert, delete, "the largest"?

2. Does it fit in memory, or does it go to disk? That completely changes the criterion.

3. Do I need an exact answer, or does an approximation work? If an approximation works, probabilistic structures change the order of magnitude of the cost.

With those three answered, the structure almost picks itself. And you demonstrate the thing that actually matters: that you can reason about the trade-off, not just recite the big O.