Trie vs Hash Map for Prefix Matching in DSA Java - Trade-offs & Analysis

Mental Model

A trie stores words by shared prefixes in a tree, making prefix search fast. A hash map stores whole words as keys, so prefix search needs extra work.

Analogy: Imagine a phone book organized by first letters (trie) versus a pile of index cards sorted by full names (hash map). Finding all names starting with 'Jo' is easier in the phone book because you open the 'J' section and then 'O' subsection.

Trie:
root
 ↓
 j -> o -> h -> n -> null
      ↓
      e -> null

Hash Map:
{ "john" : value, "joe" : value, "jane" : value }

Dry Run Walkthrough

Input: words: ["john", "joe", "jane"], prefix: "jo"

Goal: Find all words starting with prefix "jo" using trie and hash map

Step 1: Insert "john" into trie by creating nodes j -> o -> h -> n

root -> j -> o -> h -> n -> null

Why: Build trie nodes for each letter to share prefixes

Step 2: Insert "joe" into trie by adding e node after o

root -> j -> o -> h -> n -> null
               ↓
               e -> null

Why: Share prefix j -> o, add new branch for 'e'

Step 3: Insert "jane" into trie by creating a new branch after j: a -> n -> e

root -> j -> o -> h -> n -> null
      ↓         ↓
      a -> n -> e null  e -> null

Why: Add new branch for different prefix after j

Step 4: Search prefix "jo" in trie by following j -> o nodes

At node o (prefix 'jo')

Why: Locate node where prefix ends to find all words below

Step 5: Collect all words under node o: "john", "joe"

Found words: john, joe

Why: All words below prefix node share that prefix

Step 6: Search prefix "jo" in hash map by checking each key

Keys: john, joe, jane

Why: Hash map keys are full words, no prefix structure

Step 7: Check keys starting with "jo": john and joe match

Matched keys: john, joe

Why: Prefix search requires scanning all keys

Result:

Trie words with prefix 'jo': john, joe
Hash map words with prefix 'jo': john, joe

Annotated Code

DSA Java

import java.util.*;

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isWord = false;
}

class Trie {
    private TrieNode root = new TrieNode();

    public void insert(String word) {
        TrieNode curr = root;
        for (char c : word.toCharArray()) {
            curr.children.putIfAbsent(c, new TrieNode()); // create node if missing
            curr = curr.children.get(c); // move to child node
        }
        curr.isWord = true; // mark end of word
    }

    public List<String> startsWith(String prefix) {
        List<String> result = new ArrayList<>();
        TrieNode curr = root;
        for (char c : prefix.toCharArray()) {
            if (!curr.children.containsKey(c)) return result; // prefix not found
            curr = curr.children.get(c); // move to prefix end
        }
        dfs(curr, new StringBuilder(prefix), result); // collect all words below
        return result;
    }

    private void dfs(TrieNode node, StringBuilder path, List<String> result) {
        if (node.isWord) result.add(path.toString()); // found a word
        for (char c : node.children.keySet()) {
            path.append(c); // add char
            dfs(node.children.get(c), path, result); // recurse
            path.deleteCharAt(path.length() - 1); // backtrack
        }
    }
}

public class PrefixMatchComparison {
    public static void main(String[] args) {
        String[] words = {"john", "joe", "jane"};
        String prefix = "jo";

        // Using Trie
        Trie trie = new Trie();
        for (String w : words) trie.insert(w);
        List<String> trieResult = trie.startsWith(prefix);
        System.out.println("Trie words with prefix '" + prefix + "': " + String.join(", ", trieResult));

        // Using Hash Map
        Map<String, Integer> map = new HashMap<>();
        for (String w : words) map.put(w, 1);
        List<String> mapResult = new ArrayList<>();
        for (String key : map.keySet()) {
            if (key.startsWith(prefix)) mapResult.add(key); // check prefix
        }
        System.out.println("Hash map words with prefix '" + prefix + "': " + String.join(", ", mapResult));
    }
}

curr.children.putIfAbsent(c, new TrieNode()); // create node if missing

create child node if it doesn't exist to build prefix path

curr = curr.children.get(c); // move to child node

advance current node to next letter node

curr.isWord = true; // mark end of word

mark node as end of a valid word

if (!curr.children.containsKey(c)) return result; // prefix not found

stop if prefix path missing in trie

dfs(curr, new StringBuilder(prefix), result); // collect all words below

start depth-first search to find all words with prefix

if (node.isWord) result.add(path.toString()); // found a word

add word to result when end node reached

if (key.startsWith(prefix)) mapResult.add(key); // check prefix

check each hash map key for prefix match

Output

Trie words with prefix 'jo': john, joe

Hash map words with prefix 'jo': john, joe

Complexity Analysis

Time: Trie prefix search: O(m + k) where m is prefix length and k is number of matched words; Hash map prefix search: O(n * m) where n is number of keys and m is prefix length because each key is checked

Space: Trie uses O(total letters in all words) for nodes; Hash map uses O(n) for storing keys

vs Alternative: Trie is faster for prefix queries because it avoids scanning all keys; hash map is simpler but slower for prefix search

Edge Cases

Empty word list

Trie remains empty, prefix search returns empty list; hash map is empty, prefix search returns empty list

DSA Java

if (!curr.children.containsKey(c)) return result; // prefix not found

Prefix not present in any word

Trie search returns empty list immediately; hash map scan finds no matches

DSA Java

if (!curr.children.containsKey(c)) return result; // prefix not found

Words with shared prefix only partially matching

Trie correctly finds only words with exact prefix; hash map filters keys correctly

DSA Java

if (key.startsWith(prefix)) mapResult.add(key); // check prefix

When to Use This Pattern

When a problem asks for fast prefix queries on many words, reach for the trie pattern because it stores prefixes efficiently and avoids scanning all words.

Common Mistakes

Mistake: Trying to use a hash map for prefix search without scanning all keys
Fix: Use a trie to store prefixes or scan all keys explicitly in hash map

Mistake: Not marking end of word in trie nodes, causing incorrect results
Fix: Set isWord = true at the last node of each inserted word

Summary

Trie stores words by shared prefixes for fast prefix search; hash map stores full words as keys requiring scanning.

Use trie when you need efficient prefix queries over many words; use hash map for exact word lookups.

The key insight is that trie nodes represent prefixes directly, enabling quick traversal to all words sharing that prefix.

Practice

1. Which data structure is generally more efficient for prefix matching in a large set of strings?

easy

A. Array, because it stores elements in order and allows binary search

B. Trie, because it stores characters in a tree structure allowing fast prefix search

C. Hash Map, because it stores keys with direct access and no traversal

D. Linked List, because it allows sequential access to all elements

Solution

1. Step 1: Understand prefix matching requirement

   Prefix matching means finding all strings starting with a given prefix quickly.

2. Step 2: Compare Trie and Hash Map for prefix search

   Trie stores characters in nodes linked by edges, allowing traversal by prefix. Hash Map requires checking all keys or storing prefixes separately, which is less efficient.

3. Final Answer:

   Trie, because it stores characters in a tree structure allowing fast prefix search -> Option B

4. Quick Check:

   Trie = Fast prefix search [OK]

Hint: Trie is designed for prefix search, hash map is not [OK]

Common Mistakes:

• Thinking hash map can do prefix search directly
• Confusing array or linked list with prefix search efficiency

2. Which of the following is the correct way to check if a prefix exists in a Trie in Java?

easy

A. Use a loop to traverse nodes for each character of the prefix and check if nodes exist

B. Use HashMap.containsKey(prefix) directly on the Trie root

C. Use binary search on the Trie nodes array

D. Use recursion to check if prefix is a substring of any word

Solution

1. Step 1: Understand Trie prefix search method

   To check prefix, we traverse the Trie nodes character by character along the prefix path.

2. Step 2: Evaluate options for prefix check

   Use a loop to traverse nodes for each character of the prefix and check if nodes exist correctly describes traversal. Use HashMap.containsKey(prefix) directly on the Trie root is incorrect because HashMap.containsKey checks full keys, not prefixes. Use binary search on the Trie nodes array and D do not apply to Trie structure.

3. Final Answer:

   Use a loop to traverse nodes for each character of the prefix and check if nodes exist -> Option A

4. Quick Check:

   Traverse nodes for prefix = Use a loop to traverse nodes for each character of the prefix and check if nodes exist [OK]

Hint: Traverse Trie nodes for each prefix character [OK]

Common Mistakes:

• Using HashMap.containsKey for prefix check
• Trying binary search on Trie nodes
• Confusing substring with prefix

3. Given the following Java Trie code snippet, what will be the output after inserting words "cat", "car", "dog" and checking prefix "ca"?

Trie trie = new Trie();
trie.insert("cat");
trie.insert("car");
trie.insert("dog");
boolean result = trie.startsWith("ca");
System.out.println(result);

medium

A. Compilation error

B. false

C. true

D. Runtime exception

Solution

1. Step 1: Insert words into Trie

   Words "cat", "car", and "dog" are inserted, creating nodes for 'c', 'a', 't', 'r', 'd', 'o', 'g'.

2. Step 2: Check prefix "ca"

   Prefix "ca" matches nodes 'c' and 'a' in the Trie, so startsWith returns true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Prefix "ca" exists = true [OK]

Hint: Inserted words with prefix "ca" means startsWith("ca") is true [OK]

Common Mistakes:

• Assuming startsWith returns false if prefix is not a full word
• Confusing startsWith with search for full word
• Expecting compilation or runtime errors

4. Consider this Java code snippet using a HashMap to store words and check prefixes:

HashMap map = new HashMap<>();
map.put("apple", true);
map.put("app", true);
boolean prefixExists = map.containsKey("ap");
System.out.println(prefixExists);

What is the output and why?

medium

A. false, because "ap" is not a key in the map

B. true, because "ap" is a prefix of "app" and "apple"

C. Compilation error due to wrong HashMap usage

D. Runtime exception due to null key

Solution

1. Step 1: Understand HashMap key storage

   HashMap stores exact keys "apple" and "app", but not "ap".

2. Step 2: Check containsKey("ap")

   containsKey checks for exact key match, so returns false for "ap".

3. Final Answer:

   false, because "ap" is not a key in the map -> Option A

4. Quick Check:

   HashMap exact key check = false for "ap" [OK]

Hint: HashMap keys must match exactly, no prefix matching [OK]

Common Mistakes:

• Assuming containsKey checks prefixes
• Expecting true because "ap" is prefix of stored keys
• Confusing HashMap with Trie behavior

5. You need to implement a system that supports fast prefix queries on millions of words and also allows quick insertion and deletion. Which data structure is best suited and why?

hard

A. ArrayList, because it allows fast insertion and deletion at the end

B. Hash Map, because it provides constant time insertion and deletion

C. Balanced Binary Search Tree, because it keeps data sorted for prefix search

D. Trie, because it supports efficient prefix queries and dynamic updates

Solution

1. Step 1: Analyze prefix query requirement

   Fast prefix queries require a data structure that can traverse prefixes efficiently.

2. Step 2: Compare data structures for insertion, deletion, and prefix search

   Trie supports prefix queries efficiently and allows insertion/deletion by node updates. Hash Map is fast for exact keys but not prefix queries. Balanced BST supports sorted data but prefix search is slower. ArrayList is inefficient for prefix queries and deletions.

3. Final Answer:

   Trie, because it supports efficient prefix queries and dynamic updates -> Option D

4. Quick Check:

   Trie = best for prefix queries + updates [OK]

Hint: Trie handles prefix queries and updates efficiently [OK]

Common Mistakes:

• Choosing Hash Map for prefix queries
• Assuming balanced BST is best for prefix search
• Ignoring deletion complexity in ArrayList