Card 05/ 07
Trie vs Hash Set of Words
A hash set answers "is this a word?" as fast; only a trie answers "does any word start with this?".
A trie and a hash set can both hold a list of words and answer whether a given word is in it, at about the same cost. This card covers where they part: questions about prefixes, the opening letters of a word, which a trie answers by walking a few nodes and a hash set answers only by checking its words one by one, and the memory the trie spends to do it.
A trie is a tree with one node per letter, in which words that share a beginning share a path from the root. A hash set stores each word in a slot chosen by a hash of the whole word, so it can find a word it is given but keeps no link between words that start alike. The table compares them for n words, a word or prefix of L letters, and m matching words.
| Operation | Trie | Hash set of words |
|---|---|---|
| Is this exact word stored? | O(L), a walk plus the end-of-word mark | O(L) on average, to hash the word |
| Insert or remove a word | O(L) | O(L) on average |
| Does any word start with this prefix? | O(L), a walk with no mark needed | O(n × L), every word checked in the worst case |
| List every word with this prefix | O(L + m), the walk then the nodes below it | O(n × L), every word checked |
| List every word in alphabetical order | One visit of every node, children in letter order | A sort, O(n log n) comparisons |
| Memory | One node per distinct prefix, each with its own map of children | One entry per word |
A run checked the gap on three word lists, every four-, five- and six-letter word over the letters a to h, asking whether any word starts with hhh, which some do, and with hhz, which none do. The hash set's words were checked in alphabetical order, so the words starting with hhh came near the end.
| Words stored | Trie steps, hhh | Set words checked, hhh | Trie steps, hhz | Set words checked, hhz |
|---|---|---|---|---|
| 4,096 | 3 | 4,089 | 3 | 4,096 |
| 32,768 | 3 | 32,705 | 3 | 32,768 |
| 262,144 | 3 | 261,633 | 3 | 262,144 |
The trie took three steps every time, one per letter of the prefix, however many words it held. The hash set's work grew with the list, and a prefix that matched nothing cost it every word.
The trie pays in memory. For the 32,768 five-letter words, the run measured about 3.4 MiB for the hash set and about 6.4 MiB for the trie. Shared prefixes had cut the trie to 37,448 nodes for 163,840 letters, but each node is an object with its own dictionary, so even a list this heavily shared took more memory as a trie.
A rule of thumb: if every question is "is this exact word stored?", use the hash set, which is built into every language and smaller. If any question is about a beginning, such as autocomplete, a spelling suggestion or routing by a path's leading parts, use the trie.
← → move through sections and cards