When does a trie beat a hash table for prefix lookups?

Category: DSA Patterns

Answer

A hash table answers “is word W in the set” in O(|W|). A trie answers “are there words with prefix P” in O(|P|) and lets you walk all extensions. Use a trie for autocomplete, IP routing, or word games.

Concrete examples from the fca project context

Example 1

Autocomplete: walk P down the trie, then DFS to gather top-K children.

Example 2

Word search II (board + dictionary): build a trie of dictionary words; DFS the board, prune at trie.

Example 3

IP routing: longest-prefix match routes 10.0.0.0/8 to the right netmask.

Data flow / flow chart

root -> a -> p -> p -> l -> e
           |             => words with prefix "app"
           a -> p -> e -> n -> d

Takeaway

Trie when you ask “what starts with P?”; hashmap when you ask “is X present?”.