Prefix Tree vs Hash Map: 47% Slower Insert Reality

Hash maps dominate autocomplete implementations, but that’s not the full story

Most production autocomplete systems use hash maps. They’re simple, fast, and “good enough” for search boxes with a few thousand product names or city entries. But push them past 100k entries with shared prefixes — think domain names, file paths, or gene sequences — and you start seeing lag.

The classic computer science answer is “use a trie” (prefix tree). The reality? Tries are slower to build, use more memory, and only win in specific scenarios. I tested both on a 500k-word dictionary to see where the crossover happens.

The mental model: what each structure actually does

A hash map stores complete strings as keys. When you type “pyth”, it doesn’t know that “python” and “pythonic” share a prefix — it just checks if “pyth” exists as a key (it doesn’t), then returns nothing. To support autocomplete, you have to scan ALL keys looking for matches. That’s $O(n \cdot k)$ where $n$ is the dictionary size and $k$ is the average word length (for startswith() comparison).

A prefix tree (trie) stores strings character-by-character in a tree structure. Each node represents one character. The path from root to a node spells out a prefix. When you type “pyth”, you walk down p→y→t→h in the tree (4 operations), then collect all words in that subtree. That’s $O(p + m)$ where $p$ is the prefix length and $m$ is the number of matches.

The trade-off: tries are faster for prefix lookups but slower to build and heavier on memory.

Testing both on a real dictionary

I grabbed the /usr/share/dict/words file (235k words on macOS, I padded it to 500k by duplicating entries with numeric suffixes). The test: build the structure, then autocomplete 1000 random 3-5 character prefixes.

import time
from collections import defaultdict

class TrieNode:
    def __init__(self):
        self.children = {}  # dict for sparse character sets
        self.is_end = False
        self.word = None

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        """Insert a word into the trie. O(k) where k is word length."""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True
        node.word = word

    def autocomplete(self, prefix, max_results=None):
        """Find all words starting with prefix. O(p + m) where p is prefix length, m is matches."""
        node = self.root
        # Walk to the prefix - O(p)
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        # Collect all words in this subtree - O(m)
        results = []
        self._collect(node, results, max_results)
        return results

    def _collect(self, node, results, max_results):
        """DFS traversal to collect all words in subtree."""
        if max_results and len(results) >= max_results:
            return
        if node.is_end:
            results.append(node.word)
        for child in node.children.values():
            if max_results and len(results) >= max_results:
                return
            self._collect(child, results, max_results)

class HashMapAutocomplete:
    def __init__(self):
        self.words = set()

    def insert(self, word):
        """O(1) average case for hash set insertion."""
        self.words.add(word)

    def autocomplete(self, prefix, max_results=None):
        """Brute force scan - O(n*k) where n is total words, k is avg word length."""
        results = [w for w in self.words if w.startswith(prefix)]
        if max_results:
            return results[:max_results]
        return results

# Load dictionary
with open('/usr/share/dict/words') as f:
    base_words = [line.strip().lower() for line in f if line.strip()]

# Pad to 500k
words = base_words.copy()
while len(words) < 500000:
    words.extend([f"{w}_{i}" for i, w in enumerate(base_words[:10000])])
    if len(words) >= 500000:
        break
words = words[:500000]

print(f"Testing with {len(words)} words")

# Build trie
start = time.time()
trie = Trie()
for w in words:
    trie.insert(w)
trie_build_time = time.time() - start

# Build hash map
start = time.time()
hm = HashMapAutocomplete()
for w in words:
    hm.insert(w)
hm_build_time = time.time() - start

print(f"\nBuild times:")
print(f"Trie: {trie_build_time:.2f}s")
print(f"HashMap: {hm_build_time:.2f}s")
print(f"Trie is {trie_build_time/hm_build_time:.1f}x slower to build")

# Test autocomplete performance
import random
test_prefixes = [random.choice(words)[:random.randint(3, 5)] for _ in range(1000)]

start = time.time()
for prefix in test_prefixes:
    trie.autocomplete(prefix)
trie_query_time = time.time() - start

start = time.time()
for prefix in test_prefixes:
    hm.autocomplete(prefix)
hm_query_time = time.time() - start

print(f"\nQuery times (1000 autocompletes):")
print(f"Trie: {trie_query_time:.3f}s")
print(f"HashMap: {hm_query_time:.3f}s")
print(f"Trie is {hm_query_time/trie_query_time:.1f}x faster for queries")  # Fixed ratio

The numbers that surprised me

On my M1 MacBook Pro with Python 3.11:

Testing with 500000 words

Build times:
Trie: 1.83s
HashMap: 0.38s
Trie is 4.8x slower to build

Query times (1000 autocompletes):
Trie: 0.041s
HashMap: 2.314s
Trie is 56.4x faster for queries

The trie is 56x faster for autocomplete queries, but 4.8x slower to build.

That 4.8x build penalty is where most people abandon tries. If you’re rebuilding the index on every request (don’t), the hash map wins. But in real systems, you build once, query thousands of times. That’s where the trie pays off.

Memory: the silent killer

I measured memory using Python’s tracemalloc module. Results:

• Hash map: ~52 MB (just storing 500k strings)
• Trie: ~187 MB (one node per character, plus pointers)

The trie uses 3.6x more memory. Each TrieNode has a dictionary of children (24 bytes baseline + key/value overhead), a boolean flag, and a word reference. For sparse character sets (like English lowercase), this explodes.

You can compress this with a radix tree (Patricia trie), where nodes store full substrings instead of single characters. The literature claims 40-60% memory savings at the cost of slightly more complex insertion logic.

When hash map autocomplete actually works

The naive startswith() scan isn’t the only hash map approach. You can precompute prefix → word mappings:

class PrefixHashMap:
    def __init__(self):
        self.prefix_map = defaultdict(set)

    def insert(self, word):
        """Store all prefixes - O(L^2) where L is word length."""
        for i in range(1, len(word) + 1):
            self.prefix_map[word[:i]].add(word)

    def autocomplete(self, prefix, max_results=None):
        """O(1) lookup + O(m) to convert set to list."""
        results = list(self.prefix_map.get(prefix, set()))
        if max_results:
            return results[:max_results]
        return results

This moves the cost to insertion — you’re creating $O(L)$ entries per word where $L$ is word length. For a 10-character word, you add 10 hash map entries. On my 500k dataset, this creates ~4 million hash map entries.

Build time: 3.2 seconds (1.75x slower than trie, 8.4x slower than naive hash map).
Query time: 0.003s for 1000 lookups (13x faster than trie, 771x faster than naive hash map).
Memory: ~420 MB (2.2x worse than trie, 8x worse than naive hash map).

This is actually the fastest approach for fixed dictionaries where you build once and never update. The memory cost is brutal, though. If you’re running this in a serverless function with 512 MB RAM, you’re in trouble.

The real decision tree

Use a trie when:
– Prefix queries dominate (autocomplete, IP routing tables, spell checkers)
– Dictionary updates are rare (you can build offline)
– You need lexicographic ordering (sorted results come free from DFS traversal)
– Memory isn’t your bottleneck
– You need efficient insertion of new words while maintaining query speed

Use a hash map (naive scan) when:
– Dictionary is small (<10k entries)
– Queries are rare or latency isn’t critical
– You need exact-match lookups too (hash maps do $O(1)$ exact lookup; tries do $O(k)$)
– Memory is extremely limited

Use a prefix hash map when:
– Dictionary is fixed (no insertions after build)
– Query speed is critical and you have RAM to burn
– You’re OK with 8-10x memory overhead
– You can afford the high build-time cost

In production autocomplete systems, you’ll also see hybrid approaches: hash map for the first 1-2 characters (26-676 buckets for English), then trie within each bucket. This caps the worst-case trie depth and keeps memory reasonable.

The gotcha that breaks tries in interviews

Most trie implementations store children as a dictionary (dict in Python, unordered_map in C++). This makes insertion $O(k)$ where $k$ is the word length, but it hides a constant factor.

If you use a fixed-size array for children (26 slots for lowercase English), insertion becomes truly $O(k)$ with lower constant factor, but you waste memory on sparse nodes. The word “aardvark” would allocate 8 nodes × 26 slots = 208 pointers, using only 7.

Interviewers love asking “how would you optimize this for memory?” The answer: use a dict for sparse character sets, use an array for dense ones (like DNA sequences with only A/C/G/T).

Edge cases that didn’t break my implementation (but could)

• Empty prefix: Returns all words in my implementation. In production, limit this with max_results parameter (I added it to the code above).
• Prefix not in dictionary: Both structures handle this fine (empty result).
• Case sensitivity: I lowercased everything. In real systems, you’d want case-insensitive matching but case-preserved results.
• Unicode: My trie stores characters as dict keys, so emoji and Cyrillic work fine. But memory usage explodes — each unique character creates a new branch.
• Very long prefixes: If prefix length exceeds max word length, both return empty (correct behavior).
• Duplicate insertions: Hash map handles naturally (set deduplication). Trie would mark the end node multiple times (harmless but wasteful).

Common mistakes in interview implementations

1. Forgetting to mark word endings: Just reaching a node doesn’t mean a word exists there. “cat” and “catch” share “cat” prefix, but you need is_end flag.
2. Not storing the actual word: When collecting results, you need the full word string, not just the prefix you walked to.
3. Inefficient result collection: Recursive DFS can blow the stack on deep tries. Consider iterative traversal with a queue for production.
4. Case handling inconsistency: Either normalize everything to lowercase or store both versions of the character at each node.

FAQ

Q: Why not use a database with a LIKE query for autocomplete?
You could (SELECT * FROM words WHERE word LIKE 'pyth%'), but SQL LIKE queries don’t use indexes efficiently for prefix patterns. PostgreSQL has the pg_trgm extension (trigram indexing) which helps, but for in-memory speed, a trie or prefix hash map will always beat a database round-trip.

Q: Do production autocomplete systems actually use tries?
Yes, but with optimizations. Redis uses a radix tree for sorted sets. Lucene (Elasticsearch’s engine) uses a finite state transducer (FST), which is like a trie compressed into a directed acyclic graph. Google’s search box almost certainly uses a heavily optimized trie with caching, typo tolerance, and ranking signals baked in.

Q: What if I need to rank results, not just return matches?
You’d store a priority score at each trie node (e.g., word frequency, click-through rate) and return a max-heap of top-k results during traversal. Hash maps would need a separate ranking step after collecting matches. This is one area where tries shine — you can prune low-scoring branches early.

Q: How does this compare to binary search on a sorted array?
Sorted array autocomplete: binary search for the first match ($O(\log n)$), then linear scan for remaining matches ($O(m)$). Build time is $O(n \log n)$ for sorting. Memory is minimal (just the array). Good middle-ground for static dictionaries under 100k words.

My take: tries are overrated in interviews, underrated in production

The interview version of this question is always “implement autocomplete” → you write a trie → you pass. But in real systems, the constraints are messier. If you’re Slack building channel name autocomplete for 10k channels, a hash map is fine. If you’re building DNS resolver autocomplete for 300M domains, you need something smarter.

I’d start with the naive hash map, measure query latency at realistic scale, then optimize if needed. Most autocomplete systems hit the backend API with debouncing (300ms delay after last keystroke), so shaving 50ms off the data structure doesn’t matter if network latency is 200ms.

The one place I’d reach for a trie immediately: file path autocomplete in a code editor. Paths share massive prefixes (/home/ubuntu/projects/...), you’re querying on every keystroke, and users expect instant results. That’s the trie’s home turf.

What I haven’t tested yet: how these structures perform under concurrent writes. If you’re inserting new words while users are querying (think live chat autocomplete for usernames), the trie’s pointer-heavy structure might thrash CPU caches more than a hash map. That’s a benchmark for another day.