Why This Matters
Exact lookup and prefix lookup look similar until you need all words starting with "pre". A hash table answers "is this exact key present?" A trie answers questions about shared prefixes.
Decision Rule
Use a hash table for exact membership, counting, and key-value lookup. Use a trie when the query depends on prefixes, character-by-character transitions, or shared string structure.
Comparison Table
| Need | Hash table | Trie |
|---|---|---|
| Exact lookup | average O(1) | O(length of key) |
| Prefix lookup | not natural without scanning keys | natural |
| Memory layout | buckets and collision handling | nodes per character or compressed edge |
| Ordering | usually none | lexical traversal possible |
| Common use | counts, caches, dictionaries | autocomplete, word search, routing, prefix matching |
Worked Example
For words cat, car, and cart, a trie shares the prefix ca. To autocomplete ca, walk to that node and enumerate descendants.
A hash table can tell whether cat exists quickly, but finding all keys with prefix ca requires scanning keys or maintaining an additional index.
Common Mistakes
| Mistake | Correction |
|---|---|
| Using a trie for simple exact integer lookup. | A hash table is usually simpler and faster. |
| Saying hash tables cannot support prefix search at all. | They can with extra indexes, but prefix search is not their native operation. |
| Ignoring trie memory cost. | A naive trie can allocate many small nodes. |
Diagnostic Questions
| Question | Answer signal |
|---|---|
| Which structure is native for autocomplete? | Trie. |
| Which structure is native for counting frequencies? | Hash table. |
| What does a trie node represent? | A prefix state in a set of strings. |
Exercises
- Beginner: Insert
to,tea, andteninto a trie by hand. - Beginner: Use a hash table to count letters in a word.
- Beginner: Decide which structure fits exact username lookup.
- Intermediate: Implement
starts_with(prefix)on a trie. - Intermediate: Explain why a compressed trie can reduce node count.
- Challenge: Build a word-search solver using a trie and DFS on a grid.
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- MIT OpenCourseWare. 6.006 Hashing materials, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/