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

Mental Model

A trie stores words by their letters 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 letter shelves (trie), so you quickly find all names starting with 'A'. A hash map is like a pile of cards with full names, so to find names starting with 'A', you must check each card.

Trie:
root
 ├─ a
 │   ├─ p
 │   │   ├─ p
 │   │   │   └─ l
 │   │   │       └─ e (word end)
 └─ b
     └─ a
         └─ t (word end)

Hash Map:
{ "apple": true, "bat": true }

(No structure for prefixes)

Dry Run Walkthrough

Input: words: ["apple", "bat"], prefix to search: "ap"

Goal: Show how trie quickly finds words starting with 'ap' and hash map needs to check all keys

Step 1: Insert 'apple' into trie by creating nodes for each letter

root -> a -> p -> p -> l -> e[word end]

Why: Build path for 'apple' letter by letter to enable prefix search

Step 2: Insert 'bat' into trie by creating nodes for each letter

root -> a -> p -> p -> l -> e[word end]
root -> b -> a -> t[word end]

Why: Add another word path to trie for prefix matching

Step 3: Search prefix 'ap' in trie by following nodes 'a' then 'p'

At node 'p' after root -> a -> p

Why: Prefix 'ap' found quickly by following edges

Step 4: Collect all words under node 'p' in trie: 'apple'

Found word 'apple' under prefix 'ap'

Why: All words starting with 'ap' are under this node

Step 5: In hash map, check each key: 'apple' and 'bat' for prefix 'ap'

Check 'apple' (matches), check 'bat' (no match)

Why: Hash map stores full words, so prefix search requires checking all keys

Result:

Trie structure:
root -> a -> p -> p -> l -> e[word end]
root -> b -> a -> t[word end]
Words with prefix 'ap': apple

Hash Map keys: apple, bat
Words with prefix 'ap': apple

Annotated Code

DSA Rust

use std::collections::HashMap;

#[derive(Debug)]
struct TrieNode {
    children: HashMap<char, Box<TrieNode>>,
    is_word: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode {
            children: HashMap::new(),
            is_word: false,
        }
    }
}

struct Trie {
    root: TrieNode,
}

impl Trie {
    fn new() -> Self {
        Trie {
            root: TrieNode::new(),
        }
    }

    fn insert(&mut self, word: &str) {
        let mut node = &mut self.root;
        for ch in word.chars() {
            node = node.children.entry(ch).or_insert_with(|| Box::new(TrieNode::new())).as_mut();
        }
        node.is_word = true;
    }

    fn starts_with(&self, prefix: &str) -> Vec<String> {
        let mut node = &self.root;
        for ch in prefix.chars() {
            if let Some(next_node) = node.children.get(&ch) {
                node = next_node;
            } else {
                return vec![];
            }
        }
        let mut results = Vec::new();
        Self::collect_words(node, prefix.to_string(), &mut results);
        results
    }

    fn collect_words(node: &TrieNode, prefix: String, results: &mut Vec<String>) {
        if node.is_word {
            results.push(prefix.clone());
        }
        for (ch, child) in &node.children {
            let mut new_prefix = prefix.clone();
            new_prefix.push(*ch);
            Self::collect_words(child, new_prefix, results);
        }
    }
}

fn main() {
    let words = vec!["apple", "bat"];
    let prefix = "ap";

    // Build trie
    let mut trie = Trie::new();
    for word in &words {
        trie.insert(word);
    }

    // Search prefix in trie
    let trie_results = trie.starts_with(prefix);
    println!("Trie words with prefix '{}': {:?}", prefix, trie_results);

    // Hash map stores full words
    let mut map: HashMap<String, bool> = HashMap::new();
    for word in &words {
        map.insert(word.to_string(), true);
    }

    // Search prefix in hash map by checking all keys
    let mut map_results = Vec::new();
    for key in map.keys() {
        if key.starts_with(prefix) {
            map_results.push(key.clone());
        }
    }
    println!("HashMap words with prefix '{}': {:?}", prefix, map_results);
}

node = node.children.entry(ch).or_insert_with(|| Box::new(TrieNode::new())).as_mut();

advance or create node for each letter in insert

node.is_word = true;

mark node as end of word

if let Some(next_node) = node.children.get(&ch) { node = next_node; } else { return vec![]; }

advance node for each prefix letter or stop if missing

Self::collect_words(node, prefix.to_string(), &mut results);

collect all words under prefix node recursively

if node.is_word { results.push(prefix.clone()); }

add word to results when end of word reached

for key in map.keys() { if key.starts_with(prefix) { map_results.push(key.clone()); } }

check each hash map key for prefix match

Output

Trie words with prefix 'ap': ["apple"]

HashMap words with prefix 'ap': ["apple"]

Complexity Analysis

Time: Trie prefix search is O(m + k) where m is prefix length and k is number of matched words because we follow prefix nodes and collect matches; Hash map prefix search is O(n * m) because we check all n keys each of length m for prefix.

Space: Trie uses O(N * L) space for N words of average length L due to nodes; Hash map uses O(N * L) space for storing all keys but no extra structure for prefixes.

vs Alternative: Trie is faster for prefix queries because it avoids checking all keys; hash map is simpler but slower for prefix search since it must scan all keys.

Edge Cases

Empty prefix

Trie returns all words; hash map returns all keys

DSA Rust

if let Some(next_node) = node.children.get(&ch) { ... } else { return vec![]; }

Prefix not in any word

Trie returns empty list immediately; hash map returns empty after checking all keys

DSA Rust

if let Some(next_node) = node.children.get(&ch) { ... } else { return vec![]; }

Words with shared prefixes

Trie shares nodes for common prefixes, saving space; hash map stores full keys separately

DSA Rust

node = node.children.entry(ch).or_insert_with(|| Box::new(TrieNode::new())).as_mut();

When to Use This Pattern

When a problem asks for fast prefix searches or autocomplete, reach for the trie pattern because it organizes words by letters enabling quick prefix lookup.

Common Mistakes

Mistake: Trying to do prefix search directly on hash map keys without scanning all keys
Fix: Use trie to follow prefix nodes or scan all keys explicitly in hash map

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

Summary

Trie stores words letter by letter enabling fast prefix search; hash map stores full words needing full scan for prefix.

Use trie when you need efficient prefix queries or autocomplete; use hash map for exact word lookups.

The key insight is trie nodes represent prefixes directly, so prefix search is just following nodes, not scanning all words.

Practice

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

easy

A. Linked List, because it allows easy insertion and deletion

B. Hash Map, because it provides constant time lookup for any key

C. Array, because it stores elements in contiguous memory

D. Trie, because it stores common prefixes once and allows fast prefix queries

Solution

1. Step 1: Understand prefix matching requirements

   Prefix matching needs to find all strings starting with a given prefix efficiently.

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

   Trie stores common prefixes once and allows traversal by characters, making prefix queries fast. Hash Map is good for exact key lookup but not for prefix searches.

3. Final Answer:

   Trie, because it stores common prefixes once and allows fast prefix queries -> Option D

4. Quick Check:

   Prefix matching = Trie [OK]

Hint: Prefix queries need shared paths, so Trie is best [OK]

Common Mistakes:

• Thinking Hash Map supports prefix queries efficiently
• Confusing exact lookup with prefix search
• Assuming arrays or lists are good for prefix matching

2. Which Rust code snippet correctly declares a HashMap to store strings as keys and integers as values?

easy

A. let map = HashMap::new();

B. let map: HashMap = HashMap::new();

C. let map: std::collections::HashMap = std::collections::HashMap::new();

D. let map = HashMap();

Solution

1. Step 1: Check correct HashMap declaration syntax in Rust

   Rust requires specifying types inside angle brackets and calling HashMap::new() without parameters.

2. Step 2: Validate each option

   let map: std::collections::HashMap = std::collections::HashMap::new(); correctly declares a HashMap with String keys and i32 values using full path and new().

3. Final Answer:

   let map: std::collections::HashMap = std::collections::HashMap::new(); -> Option C

4. Quick Check:

   Correct Rust HashMap syntax = let map: std::collections::HashMap = std::collections::HashMap::new(); [OK]

Hint: Use HashMap::new() with type annotations for keys and values [OK]

Common Mistakes:

• Using parentheses instead of ::new()
• Swapping key and value types
• Omitting type annotations when needed

3. Given the following Rust code using a Trie for prefix matching, what will be the output?

struct TrieNode {
    children: std::collections::HashMap,
    is_end: bool,
}

impl TrieNode {
    fn new() -> Self {
        TrieNode { children: std::collections::HashMap::new(), is_end: false }
    }
}

fn main() {
    let mut root = TrieNode::new();
    // Insert "cat"
    let mut node = &mut root;
    for c in "cat".chars() {
        node = node.children.entry(c).or_insert(TrieNode::new());
    }
    node.is_end = true;

    // Check prefix "ca"
    let mut node = &root;
    let mut found = true;
    for c in "ca".chars() {
        if let Some(next) = node.children.get(&c) {
            node = next;
        } else {
            found = false;
            break;
        }
    }
    println!("{}", found);
}

medium

A. false

B. Compilation error

C. true

D. Runtime panic

Solution

1. Step 1: Analyze TrieNode struct definition

   TrieNode { children: HashMap, ... } creates a recursive type without indirection (e.g., Box<TrieNode>). Rust cannot compute the size of TrieNode, resulting in a compilation error.

2. Step 2: Confirm error prevents execution

   Code fails to compile, so no output or runtime behavior occurs.

3. Final Answer:

   Compilation error -> Option B

4. Quick Check:

   Recursive TrieNode without Box = compile error [OK]

Hint: Rust recursive structs require Box or Rc for children [OK]

Common Mistakes:

• Assuming prefix must be a complete word
• Confusing is_end with prefix existence
• Ignoring Rust recursive type size requirements

4. The following Rust code attempts to use a HashMap for prefix matching but has a bug. What is the bug?

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("apple", 1);
    map.insert("app", 2);

    let prefix = "ap";
    let mut found = false;
    for key in map.keys() {
        if key.starts_with(prefix) {
            found = true;
            break;
        }
    }
    println!("{}", found);
}

medium

A. Inefficient prefix search due to linear scan over keys

B. Using &str keys without lifetime causes compilation error

C. HashMap keys are unordered, so starts_with check is invalid

D. No bug; code works correctly for prefix matching

Solution

1. Step 1: Analyze prefix matching approach

   The code scans all keys linearly and checks if they start with the prefix, which works but is inefficient for large data.

2. Step 2: Identify the bug type

   There is no syntax or runtime error, but the approach is inefficient compared to Trie which supports fast prefix queries.

3. Final Answer:

   Inefficient prefix search due to linear scan over keys -> Option A

4. Quick Check:

   Linear scan for prefix = inefficient [OK]

Hint: HashMap needs full key; prefix search requires scanning all keys [OK]

Common Mistakes:

• Thinking code has syntax or runtime errors
• Assuming HashMap keys are ordered
• Ignoring performance implications

5. You need to implement a system in Rust that supports fast insertion and prefix search for millions of words. Which approach is best and why?

// Option A: Use a Trie with HashMap children
// Option B: Use a HashMap storing all words as keys
// Option C: Use a sorted Vec and binary search for prefix
// Option D: Use a LinkedList of words and scan linearly

hard

A. Trie, because it shares prefixes and allows O(k) prefix search where k is prefix length

B. HashMap, because it provides O(1) exact lookup but slow prefix search

C. Sorted Vec, because binary search helps but prefix search needs extra logic

D. LinkedList, because insertion is fast but prefix search is very slow

Solution

1. Step 1: Evaluate insertion and prefix search efficiency

   Trie allows insertion and prefix search in O(k) time, where k is prefix length, by sharing common prefixes.

2. Step 2: Compare other data structures

   HashMap is fast for exact keys but slow for prefix search. Sorted Vec requires complex prefix range search. LinkedList is slow for prefix search.

3. Final Answer:

   Trie, because it shares prefixes and allows O(k) prefix search where k is prefix length -> Option A

4. Quick Check:

   Fast prefix search = Trie [OK]

Hint: Prefix search speed depends on prefix length, Trie is best [OK]

Common Mistakes:

• Choosing HashMap for prefix search
• Ignoring complexity of prefix range search in sorted Vec
• Underestimating LinkedList search cost