Trie vs Hash Set: Which One for Prefix Search?

Tries have a reputation as the "advanced" answer to string questions, and hash sets as the plain one. That framing leads people to reach for a trie when a set would do, and — more often — to force a set into a job it cannot do well. The real rule is simpler and has nothing to do with sophistication: it depends on which question you are going to ask.

The problem it solves

You have a large collection of words: a dictionary, a list of product names, every username. Two kinds of question come in.

• Exact: is "cart" in the collection?
• Prefix: which stored words start with "ca"? Is there any word starting with "ca"? What is the longest stored word that is a prefix of this input?

A hash set is built for the first question and answers it in one hash and one bucket probe. For the second, it has nothing to offer. Hashing deliberately scatters "car" and "cart" into unrelated buckets — that scattering is what makes it fast — so the only way to find every word beginning with "ca" is to look at every stored word.

The intuition

A trie stores words as paths of characters from a shared root. Words with a common prefix share the nodes for that prefix: "car", "cart" and "cat" all pass through c then a. The prefix is not something you search for; it is a location in the structure.

So a prefix query becomes: walk down len(prefix) edges, then read the subtree below. The cost depends on the length of the prefix and the number of matches — not on how many unrelated words are stored elsewhere. Ten million words starting with other letters are simply never visited.

A hash set answers "is this exact key here?" A trie answers "what lives under this prefix?" Pick by the question, not by the data.

The price is memory. Each character becomes a node, and a node is a map from characters to children. A set stores each word once, as one compact string.

Watch it run

The hash set sits beside the trie, holding the same four words. The exact lookup is one bucket for the set. Then the prefix query: the set has to check every key, while the trie takes two hops to the ca node and reads only that branch — the dog branch is never touched.

The code

Here is a small trie whose nodes are plain dictionaries, tested on about 38,000 random words over an eight-letter alphabet — enough overlap that prefixes are genuinely shared.

class Trie:
    def __init__(self):
        self.root, self.nodes = {}, 1
    def add(self, word):
        node = self.root
        for ch in word:
            if ch not in node:
                node[ch] = {}
                self.nodes += 1
            node = node[ch]
        node["$"] = True                       # a word ends here
    def starting_with(self, prefix):
        node = self.root
        for ch in prefix:                      # walk the prefix: len(prefix) hops
            if ch not in node:
                return []
            node = node[ch]
        out, stack = [], [(node, prefix)]
        while stack:                           # then read only this subtree
            node, word = stack.pop()
            for ch, child in node.items():
                if ch == "$":
                    out.append(word)
                else:
                    stack.append((child, word + ch))
        return sorted(out)

import random, sys
random.seed(4)
words = {"".join(random.choices("abcdefgh", k=random.randint(3, 9)))
         for _ in range(50_000)}
trie = Trie()
for w in words:
    trie.add(w)

by_set = sorted(w for w in words if w.startswith("bad"))   # checks every key
by_trie = trie.starting_with("bad")
print(len(words), len(by_trie), by_set == by_trie)        # 38601 69 True

def trie_bytes(node):
    return sys.getsizeof(node) + sum(trie_bytes(c) for k, c in node.items() if k != "$")
set_bytes = sys.getsizeof(words) + sum(sys.getsizeof(w) for w in words)
print(trie.nodes, round(trie_bytes(trie.root) / set_bytes, 1))   # 95533 5.3

ok = all(trie.starting_with(p) == sorted(w for w in words if w.startswith(p))
         for p in ("".join(random.choices("abcdefgh", k=random.randint(0, 4)))
                   for _ in range(300)))
print(ok)                                                 # True

Both approaches return the same 69 words for "bad". The set checked all 38,601 keys to find them; the trie walked three edges and visited the 69 matches plus the nodes between them. The random check at the end compares the two on 300 prefixes, including the empty one, and they agree on all of them.

The second line is the bill. The trie holds 95,533 nodes, and as Python dictionaries they take about 5.3 times the memory of the set with its strings. A leaner implementation — fixed-size child arrays, or a compressed radix tree that merges single-child chains — narrows that gap, but a trie is rarely smaller than the set it replaces.

There is also a third option that interviews rarely mention and real systems use often: a sorted list. Every word with a given prefix sits in one contiguous run, and two binary searches find its ends.

import bisect
ordered = sorted(words)                                   # the third option
lo = bisect.bisect_left(ordered, "bad")
hi = bisect.bisect_left(ordered, "bae")
print(ordered[lo:hi] == by_trie)                          # True

O(log n) to find the run, no per-character nodes at all. Its weakness is insertion: adding a word to a sorted list is O(n), so it suits collections that are built once and queried many times.

The complexity

With n words, L the length of the query and k the number of matches:

• Hash set, exact lookup: O(L) to hash the query, then O(1) expected.
• Hash set, prefix query: O(n · L) — every key is checked.
• Trie, exact lookup: O(L) hops.
• Trie, prefix query: O(L) to reach the prefix, plus the size of the subtree below it for the k matches.
• Sorted list, prefix query: O(L log n) to find the run, plus k to read it.
• Memory: the set stores total characters once; the trie stores one node per distinct prefix, each far heavier than a character.

Where it goes wrong

• A trie for exact membership only. If nothing ever asks about prefixes, the trie is slower to build, uses several times the memory, and wins nothing. Use the set.
• A set of every prefix. Storing each word's prefixes in a second set does answer "does any word start with p?" in O(1). It cannot list the matches, though, and it stores 95,532 separate strings here — the trie's node count, as whole strings rather than single characters.
• Forgetting the end marker. Without the "$" flag, a trie holding "cart" will claim "car" is a word because the path exists.
• Recursion depth. Recursive traversal of a trie over long keys can hit Python's recursion limit; the explicit stack above avoids it.

For the problems where tries genuinely earn their memory, see prefix search and autocomplete and word search with a trie.

How to say it in an interview

"If the only question is exact membership, a hash set is the right tool — expected O(1) and far less memory. The moment I need prefixes — autocomplete, 'does any word start with this', longest-prefix match — hashing has destroyed the order I need, so I'd use a trie: O(L) to reach the prefix and then only the matching subtree. If the word list is static, a sorted array with binary search gives the same prefix ranges with almost no overhead."

Naming the third option is the part that shows you have thought about trade-offs rather than memorised a data structure.