Trie vs HashMap
Use a hash structure for exact-word lookups, which it answers in O(1) and a trie cannot beat. Use a trie the moment the question involves prefixes, because a hash scatters words by hash and loses every relationship between them.
A hash set answers is this exact word present faster than anything else, and that is the only question it answers. A trie stores words as paths of characters, so every word beginning with app lives under one node, three steps from the root. The choice is not about speed in general but about which question you need answered.
Side by side
| Dimension | Trie | HashMap |
|---|---|---|
| Exact lookup | O(L) for a word of length L | O(1) average, O(L) to hash the word |
| Prefix query | O(L), then the subtree below | O(n), every entry has to be tested |
| Memory | High, 26 references per node | Lower, one entry per word |
| Sorted output | Free, walk the children in order | Not available without sorting |
| Longest matching prefix | Natural, the walk stops where it stops | Not available |
| n, the number of words | Does not appear in the cost | Appears in any prefix work |
When to pick each
Trie
- Autocomplete, where the input is a prefix and the output is everything under it.
- Word games on a grid, where a trie prunes a branch the moment no stored word continues that way.
- Routing and dictionary problems that need the longest prefix that matches, such as IP tables or word-break segmentation.
HashMap
- Membership and nothing else: is this word in the dictionary.
- Keys that are not strings, or strings with no shared structure such as random identifiers.
- Memory-constrained code, where 26 references per node is the cost you cannot pay.
Treating a trie as a faster hash map. It is not: the lookup is O(L) rather than O(1) and it uses several times the memory, so swapping one in for exact lookups makes the code slower and larger. The value is entirely in the prefix relationships, and if the problem never asks about a prefix, the trie is paying rent on a feature nobody uses.
Questions people ask
Why is a trie lookup independent of how many words are stored?
Because the walk is driven by the word you are looking up, not by the dictionary. Each character is one array index into the current node's children, so a five-letter word costs five steps whether the trie holds ten words or ten million. The number of stored words only affects memory and the size of a prefix subtree.
How much memory does a trie really use?
A node with a 26-slot array of references costs over a hundred bytes on a 64-bit JVM, most of it null in an English dictionary. Swapping the array for a HashMap per node cuts that substantially and slows each step a little, which is the usual production compromise. For an interview, say the array version and name the swap as the fix if memory comes up.
What is the isEnd flag for?
Telling a stored word apart from a prefix on the way to one. After inserting apple, the path for app exists, so a search for app completes the walk and would return true without the flag. Marking the final node of each inserted word is what makes search and startsWith different functions rather than the same one.