The idea: the same words, stored two ways
A trie and a hash map both answer "is this word stored?" in time that does not grow with the number of words. They get there in opposite ways. The trie cuts each word into letters and shares the letters that words have in common. The hash map turns the whole word into one number and uses it to jump to a slot. This page stores the same 8 words, cat car cart care can do dog dot, in both, and runs every query in both at once, one unit of work per step.
The scoreboard counts what each lane does. Memory hops are pointer dereferences: going to a child node, to a slot, or to the next entry of a chain. Each one can be a cache miss, which costs far more than reading a letter. Chars read counts letters looked at, for hashing or comparing. Memory cells counts pointer-sized cells the structure holds.
The trie: one node per prefix
The root stands for the empty prefix. Each node has 26 child slots, one per letter, and a flag that says "a word ends here" (green on the canvas). To find cart, start at the root and follow c, a, r, t: one hop per letter, then check the flag. A missing child means the word is not stored, and the search stops early. See Trie for insert and delete.
The hash map: hash, jump, compare
The hash map here works like Java's HashMap with its default capacity of 16. It computes h = key.hashCode() from every letter, spreads it with h ^ (h >>> 16), and keeps the low 4 bits as the slot index. Words that land in the same slot form a chain. A lookup reads the slot, then compares the word with each entry of the chain using equals. With a good hash the chains are short, so a lookup is about 2 hops whatever the length of the word. See How Java's HashMap works for resizing and treeified bins.
Exact lookup: the hash map wins
Demo: find "cart". The hash map reads the letters twice, once to hash and once in equals (8 chars), but makes only 2 hops: the slot and one entry. The trie reads each letter once (4 chars) but makes 4 hops, one node per letter. Hops are what cost time on real hardware, so for exact lookups of whole keys a hash map is usually faster, and the gap grows with longer keys.
On a miss the trie stops at the first missing letter: looking up cow stops after c, because c has no o child (1 hop, 2 chars). The hash map hashes all of cow (3 chars) and finds slot 10 empty (1 hop). For long keys that differ early, the trie reads much less.
Prefix search: the trie wins
Demo: prefix "ca*". The trie walks down 2 nodes to ca. Every word in that subtree starts with "ca", so it collects the subtree: 7 hops for 5 words. The hash map has no idea where words that start with "ca" are, because a good hash sends similar keys to unrelated slots. It reads all 16 slots and all 8 entries: 24 hops. That cost grows with the size of the whole map, while the trie's grows only with the prefix and the answer. This is why autocomplete, spell checkers and IP routing tables use tries.
Sorted order: the trie wins
Demo: sorted list. Visiting the trie's children in letter order lists the words already sorted: can car care cart cat do dog dot, 11 hops. The hash map's slot order is unrelated to the words (can car cat dot do dog cart care), so it reads all 24 cells and then sorts. A sorted map or a trie gives ordered iteration; a hash map does not.
Memory: the hash map wins
Demo: memory, build from empty. The trie shares prefixes, so it stores only 11 letters for 25 letters of words. But each of its 12 nodes reserves 26 child slots, and only 11 of those 312 slots are used. The hash map pays 16 slots plus one 4-field entry (hash, key, value, next) per word: 48 cells, plus the key strings themselves.
Real tries cut this down: children in a small sorted array or a hash map, a radix tree that merges chains of single children into one edge, or a ternary search tree.
A bad hash function
Demo: bad hash, find "can". With the hash "first letter only", every word starting with c lands in slot 3 and every d-word in slot 4. Finding can now reads the slot and walks the whole chain cat → car → cart → care → can: 6 hops, against the trie's 3. A hash map is only as good as its hash function; the trie has no hash function to get wrong. Java's HashMap turns a chain of 8 or more into a red-black tree to limit the damage.
When to pick which
| Need | Trie | Hash map |
|---|---|---|
| Exact lookup of a whole key | one hop per letter | about 2 hops |
| A key that is not stored | stops at the first missing letter | hashes the whole key first |
| All keys with a prefix (autocomplete) | walk to the prefix, collect the subtree | scan every slot |
| Keys in sorted order | free, by walking in letter order | collect, then sort |
| Memory | many mostly empty nodes | compact |
| Keys that are not strings | needs a way to cut them into digits | any key with hash and equals |
| Worst case | no collisions: always one hop per letter | a bad hash or attack puts keys in one chain |
What the page leaves out
The words are fixed and short, so the page only looks up; insert is shown once, in the memory demo, and delete is not shown. The counters are a model: real costs depend on caches, memory allocators and string layout. The hash map never resizes (8 words stay under the threshold of 12) and never treeifies a bin. Compact tries (children in sorted arrays, bitmaps, radix trees, double-array tries, DAWGs that also share suffixes), hash maps with open addressing, and concurrent versions of both are not shown.