Choosing a Data Structure — Arrays, Hashes, Trees and Heaps

What arrays, hash tables, trees and heaps each make fast, and what each one gives up in return. A pick-by-use-case table, plus which structures actually show up in tokenizers, vector search and KV caches.

The metaphor: kitchen storage is decided by how you take things out

The same jar goes in a different place depending on how you use it. Salt and pepper live on the counter beside the stove — instant to grab, but they eat surface area and the counter degrades into clutter as the collection grows. Dry goods go into labelled drawers — one motion if you know the name, but useless for "show me everything expiring soon". The front shelf of the fridge holds whatever expires next, so exactly one item is always ready to hand.

Choosing a data structure works the same way. There is no universal container: every one of them makes something fast by giving something else up. Design is picking the sacrifice that your access pattern never notices.

The intuition: four tools and their terms of trade

Four structures cover most situations. For each, read what it abandoned before you read what it made fast.

Array (dynamic array, list)

Fetching element $i$ is $O(1)$. Elements sit contiguously in memory, which makes a front-to-back sweep the fastest operation available anywhere — the cache effect from the complexity article is at maximum here. Appending is amortized $O(1)$ when capacity doubles on growth.

What it gives up is insertion and deletion in the middle: everything after the gap shifts, so $O(n)$. Search by value is $O(n)$ too, or $O(\log n)$ by binary search if the array is kept sorted.

Hash table (dict, set)

Crush the key into a number and put the value directly on that numbered shelf. Insert, lookup and delete are all $O(1)$ on average — the cost of one operation is the same whether you hold a million entries or ten million.

The mechanism turns on the load factor.

Read that in words: take the count of things you have put in and divide it by the count of shelves you have to put them on. Two hundred entries spread over four hundred buckets is $\alpha = 0.5$ — half the table standing empty, on purpose.

$\alpha$ is how crowded the shelves are. The more crowded, the more often two keys land on the same shelf — a collision — and performance decays. So implementations grow the table and reinsert everything once $\alpha$ passes a threshold. "Average $O(1)$" is a speed you buy by permanently carrying empty space.

What it gives up is order. No range queries, no "next largest key", no sorted traversal. On top of that the worst case is $O(n)$, and the memory overhead per entry is not small.

Tree (balanced BST, B-tree)

Search, insert and delete are all $O(\log n)$, and order survives. Since each comparison splits the remaining $n$ into two, the height is

$$h \approx \log_2 n$$

which says the height $h$ is however many times you can halve the number of entries $n$ before a single item is left. Or, in words: every time the collection doubles, you pay exactly one more comparison — not twice as much work.

So a million entries are reached in about twenty comparisons. Multiply $n$ by a thousand and $h$ grows by ten — that is what a logarithm buys you.

Because the ordering is intact, "everything between 100 and 200", "the next key above this one" and "walk the whole thing in sorted order" all come free. Constants are heavier than a hash table's, so if you do not need order there is no reason to pay them.

The B-tree used in database indexes is the same idea tuned to the memory hierarchy: pack many keys into one node so the fan-out is large and the tree is short. A node maps onto the unit a disk or page read fetches anyway, so the count of slow accesses drops.

Heap (priority queue)

Reading the minimum (or maximum) is $O(1)$; pushing and popping are $O(\log n)$.

What it gives up is global order. A heap is not sorted; it only guarantees that a parent is smaller than its children. It cannot hand you the third-smallest element directly, and searching for an arbitrary value is $O(n)$.

When you only ever want "the next one" — maintaining a top-k list, scheduling tasks, picking the next node in Dijkstra's algorithm — a heap is the cheapest option precisely because it never sorts the rest.

Pick by use case

A trie merges shared prefixes into single branches, so each character read narrows the candidates — ideal for completion and dictionary lookup. A Bloom filter answers "definitely not present" exactly and "probably present" approximately, trading correctness for a dramatic reduction in memory.

The single most common fix, in code

Most performance bugs are a linear scan hiding inside a loop.

# O(n*m): `x in b` rescans b from the top every time
def common_slow(a, b):
    return [x for x in a if x in b]

# O(n+m): build the set once
def common_fast(a, b):
    bs = set(b)                       # O(m) to construct
    return [x for x in a if x in bs]  # membership is O(1) on average

The difference is one line: whether set(b) gets built first. At $n = m = 10^4$ the first version does about a hundred million operations and the second about twenty thousand. That is what "the data structure matters" means in concrete terms.

Which of these show up in AI systems

Tokenizers. The vocabulary is a string-to-ID hash table. Longest-match schemes such as SentencePiece and WordPiece become naturally fast when the vocabulary sits in a trie, since each character read prunes the candidate set. BPE implementations typically look up merge priorities in a hash map and pull the next pair to merge off a heap. Three structures live inside one tokenizer.

Vector search. Closeness between embeddings is measured with a dot product (cosine similarity once the vectors are normalized). Get a feel for that quantity first.

Scoring all $N$ vectors costs $O(Nd)$ with $d$ dimensions, which stops being practical at million-scale. So the index becomes a graph — HNSW connects near neighbours with edges and walks those edges downhill toward the target — or a partition into clusters that narrows the candidate set first. You abandon the exhaustive comparison, accept an approximate answer, and get a search that behaves logarithmically. Another trade, same shape as all the others (RAG fundamentals).

KV caches. An array that grows by one entry per generated token. Reserving contiguous space for something whose final length is unknown fragments memory, so serving engines slice it into fixed-size pages and indirect through a page table, exactly like OS virtual memory. The textbook chapter walks straight into the inference stack.

Beam search keeps its top-k on a heap; deduplication in data pipelines runs on hashing, with approximate variants at scale. No exotic inventions — the same four tools.

Four things that matter in practice

1. Write it with arrays and dicts first Introduce a clever structure once the profiler points at it. Usually those two suffice, and when they do not, you will choose the replacement far better for having seen the actual pattern.

2. Decide up front whether you need order That single question is the hash-versus-tree fork. Discovering you need range queries later means swapping the structure wholesale.

3. Turn one-at-a-time lookups into batched ones When the other side is storage or an API, round trips dominate everything a data structure could do. Collect the keys, fetch once, build a dict from the response, then proceed.

4. Memory is part of the complexity A hash table buys its speed with permanent empty space. Past tens of millions of entries, per-entry overhead becomes the binding constraint. Dropping to a sorted array with binary search cuts the memory and charges you $O(\log n)$ instead — the time-space trade again.

Summary

• Every structure makes something fast by giving something up; choose the one whose sacrifice your workload never hits
• Array = contiguous and index-fast / hash = $O(1)$ average but unordered / tree = $O(\log n)$ with order intact / heap = fast for exactly one element
• A hash table's $O(1)$ is purchased with the memory that keeps the load factor $\alpha$ low
• Replacing a linear scan inside a loop with a set or dict turns $O(n^2)$ into $O(n)$
• AI systems use the same toolkit: tries and heaps in tokenizers, graph indexes in vector search, page tables in KV caches

Next: the most systematic version of "keep a table so you never recompute" — dynamic programming (Dynamic Programming From Scratch).