How does a trie compare to a hash table for prefix search?
Updated Feb 20, 2026
Short answer
A trie answers a prefix query in O(p + m) — the prefix length plus the number of matches — because every key sharing the prefix lives in one subtree. A hash table cannot do better than O(n·k), scanning every stored key, because hashing deliberately destroys similarity between related strings. For exact lookup the hash table wins; for prefix work it is the wrong structure entirely.
Deep explanation
| Operation | Trie | Hash table |
|---|---|---|
| Exact lookup | O(k) | O(k) average |
| Insert | O(k) | O(k) average |
| Prefix search | O(p + m) | O(n·k) — full scan |
| Ordered iteration | yes, free | no |
| Memory | high (node per char) | lower |
| Cache behaviour | poor (pointer chasing) | good |
Why the hash table fails at prefixes. A hash function's entire purpose is to scatter similar inputs to unrelated buckets — "interview" and "interval" land nowhere near each other. There is no way to enumerate keys sharing a prefix except to examine all of them. The property that makes hashing fast for exact lookup makes it useless for prefixes.
Why the trie succeeds. Shared prefixes are physically shared — one path of nodes. Reaching that path is p steps, and everything beneath it is exactly the matching set.
But the trie is not free. For exact lookup both are O(k), and the hash table is usually faster in wall-clock terms: one hash computation and a probe into contiguous memory, against k pointer dereferences that each likely miss cache. Memory is worse too — a node per character with a children map, versus one entry per key.
Middle grounds worth knowing:
- A sorted array with binary search answers prefix queries in O(log n + m), since keys sharing a prefix are contiguous. Far less memory than a trie, but insertion is O(n).
- A radix tree compresses single-child chains, keeping the prefix behaviour with a fraction of the nodes.
So the decision is: prefix or ordering requirements → trie or radix tree; static dataset with prefix queries → sorted array; exact lookup only → hash table.
Real-world example
Ten million product names, with a type-ahead box:
# Trie: reaches the 'wire' subtree in 4 steps, collects matches beneath ittrie.starts_with('wire') # ~4 + m operations
# Hash table: no alternative but a full scan[k for k in products if k.startswith('wire')] # 10,000,000 comparisonsAt every keystroke. The hash table version cannot meet an interactive latency budget at that size, while the trie's cost is governed by the number of results shown — typically ten.
Common mistakes
- - Using a hash table for autocomplete and scanning all keys per keystroke, which does not scale.
- - Assuming the trie is faster across the board
- for exact lookup a hash table usually wins on cache behaviour.
- - Ignoring the trie's memory overhead on large sparse key sets — a compressed radix tree is often the practical choice.
- - Overlooking a sorted array plus binary search for static data, which gives prefix queries at a fraction of the memory.
- - Storing a fixed-size child array per node for a large alphabet, wasting memory on mostly-empty slots.
Follow-up questions
- Why can't a hash table support prefix search efficiently?
- How does a sorted array compare for prefix queries?
- When is a radix tree preferable to a plain trie?
- How would you rank autocomplete suggestions by popularity?