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

Mental Model

A trie stores words by their letters step-by-step, making prefix search fast. A hash map stores whole words as keys, so prefix search needs checking many keys.

Analogy: Imagine a library organized by shelves for each letter (trie), so you quickly find all books starting with 'A'. A hash map is like a pile of books with labels; to find all starting with 'A', you check each label one by one.

Trie:
root
 ↓
 a -> p -> p -> l -> e
     ↓
     r -> t

Hash Map:
{ "apple": true, "app": true, "art": true }

Dry Run Walkthrough

Input: words: ["app", "apple", "art"], prefix: "ap"

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

Step 1: Insert "app" into trie letter by letter

root -> a -> p -> p [end]
Hash Map: {"app": true}

Why: Build trie nodes for each letter to represent the word

Step 2: Insert "apple" into trie continuing from "app"

root -> a -> p -> p -> l -> e [end]
Hash Map: {"app": true, "apple": true}

Why: Extend trie nodes for new letters after existing prefix

Step 3: Insert "art" into trie starting from root

root -> a -> p -> p -> l -> e [end]
       ↓
       r -> t [end]
Hash Map: {"app": true, "apple": true, "art": true}

Why: Add new branch for different prefix starting with 'a'

Step 4: Search trie for prefix "ap" by following nodes a -> p

At node 'p' after root -> a -> p
Hash Map: keys checked one by one

Why: Reach prefix node to collect all words below

Step 5: Collect all words under trie node 'p': "app", "apple"

Found words: "app", "apple"
Hash Map: check keys starting with "ap"

Why: Trie allows direct access to prefix subtree

Step 6: In hash map, check each key if it starts with "ap"

Keys: "app" (yes), "apple" (yes), "art" (no)
Found words: "app", "apple"

Why: Hash map needs to scan all keys for prefix match

Result:

Trie words with prefix 'ap': app -> apple
Hash Map words with prefix 'ap': app, apple

Annotated Code

DSA Go

package main

import (
	"fmt"
)

// TrieNode represents each node in the trie
type TrieNode struct {
	children map[rune]*TrieNode
	isEnd    bool
}

// Trie structure with root node
type Trie struct {
	root *TrieNode
}

// NewTrie creates a new empty trie
func NewTrie() *Trie {
	return &Trie{root: &TrieNode{children: make(map[rune]*TrieNode)}}
}

// Insert adds a word to the trie
func (t *Trie) Insert(word string) {
	curr := t.root
	for _, ch := range word {
		if curr.children[ch] == nil {
			curr.children[ch] = &TrieNode{children: make(map[rune]*TrieNode)}
		}
		curr = curr.children[ch] // advance curr to next node
	}
	curr.isEnd = true // mark end of word
}

// collectWords collects all words under given node with prefix
func (t *Trie) collectWords(node *TrieNode, prefix string, results *[]string) {
	if node.isEnd {
		*results = append(*results, prefix) // found a word
	}
	for ch, child := range node.children {
		t.collectWords(child, prefix+string(ch), results) // recurse children
	}
}

// StartsWith finds all words starting with prefix
func (t *Trie) StartsWith(prefix string) []string {
	curr := t.root
	for _, ch := range prefix {
		if curr.children[ch] == nil {
			return []string{} // prefix not found
		}
		curr = curr.children[ch] // advance curr to prefix node
	}
	results := []string{}
	t.collectWords(curr, prefix, &results) // collect all words below prefix
	return results
}

func main() {
	words := []string{"app", "apple", "art"}
	prefix := "ap"

	// Build trie
	trie := NewTrie()
	for _, w := range words {
		trie.Insert(w)
	}

	// Search trie
	trieResults := trie.StartsWith(prefix)
	fmt.Print("Trie words with prefix '", prefix, "': ")
	for i, w := range trieResults {
		if i > 0 {
			fmt.Print(" -> ")
		}
		fmt.Print(w)
	}
	fmt.Println()

	// Hash map approach
	hashMap := make(map[string]bool)
	for _, w := range words {
		hashMap[w] = true
	}

	fmt.Print("Hash Map words with prefix '", prefix, "': ")
	first := true
	for k := range hashMap {
		if len(k) >= len(prefix) && k[:len(prefix)] == prefix {
			if !first {
				fmt.Print(", ")
			}
			fmt.Print(k)
			first = false
		}
	}
	fmt.Println()
}

curr = curr.children[ch] // advance curr to next node

advance curr to next node -- build path for word

curr.isEnd = true // mark end of word

mark node as end of a valid word

if curr.children[ch] == nil { return []string{} }

stop if prefix path missing

curr = curr.children[ch] // advance curr to prefix node

follow prefix path in trie

t.collectWords(curr, prefix, &results) // collect all words below prefix

gather all words starting with prefix

for k := range hashMap { if len(k) >= len(prefix) && k[:len(prefix)] == prefix { ... } }

check each key for prefix match in hash map

Output

Trie words with prefix 'ap': app -> apple

Hash Map words with prefix 'ap': app, apple

Complexity Analysis

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

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

vs Alternative: Trie is faster for prefix queries because it directly follows prefix nodes; hash map is slower as it scans all keys for prefix matches

Edge Cases

Empty word list

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

DSA Go

if curr.children[ch] == nil { return []string{} }

Prefix not present in any word

Trie search returns empty list immediately; hash map finds no keys starting with prefix

DSA Go

if curr.children[ch] == nil { return []string{} }

Words with shared prefixes

Trie shares nodes for common prefix letters; hash map stores all keys separately

DSA Go

curr = curr.children[ch] // advance curr to next node

When to Use This Pattern

When a problem asks for fast prefix search or autocomplete, reach for the trie pattern because it stores words letter-by-letter allowing quick prefix traversal, unlike hash maps which require scanning all keys.

Common Mistakes

Mistake: Trying to use hash map keys directly for prefix search without scanning all keys
Fix: Implement a loop to check each key's prefix or use a trie for efficient prefix queries

Summary

Compares trie and hash map for finding words by prefix.

Use trie when you need fast prefix search; use hash map for exact word lookup.

Trie stores words letter-by-letter enabling direct prefix traversal; hash map stores whole words requiring full key scans for prefix.