Tries

A trie is the one common structure with no equivalent in java.util, and it exists for a question a hash table cannot answer: what starts with this?

#The question a HashSet cannot answer

Two hundred thousand words. Find every one beginning with payme:

###   HashSet, scanning everything :   10.5 ms  (1 found)
###   Trie, walking the prefix     :    0.0 ms  (1 found)
###   same answer? true

The numbers are small; the shape is the point. The HashSet had to look at all two hundred thousand — a hash table can tell you whether a key is present and nothing at all about keys that are similar, so "starts with" degrades to a full scan. Its cost depends on the size of the set.

The trie followed five characters and stopped. Its cost depends on the length of the prefix, not the size of the dictionary, plus the number of matches it then collects.

Put that in an autocomplete firing on every keystroke, for every user, and the difference stops being 10 milliseconds.

#What it is

A tree where the path is the key. Each edge is one character; each node is a prefix.

        (root)
         /  \
        p    t
       /      \
      a        o
     / \        \
    y   c        p ●
   /     \
  ● (pay)  k ● (pack)
 /
m
|
e ● (payme)

The ● marks a node where a word ends, which is a flag on the node rather than a separate kind of node. That flag is necessary: without it a trie cannot distinguish "pay is a word" from "pay is only a prefix of payment".

class Node {
    Map<Character, Node> next = new HashMap<>();
    boolean word;
}
 
void insert(Node n, String w) {
    for (char c : w.toCharArray()) n = n.next.computeIfAbsent(c, k -> new Node());
    n.word = true;
}

Search is the same walk without the computeIfAbsent: follow characters, and if you fall off the tree the word is not there.

#The costs, honestly

Time is the good news. Insert and search are O(m) where m is the length of the word — independent of how many words the trie holds. A trie with ten words and one with ten million answer a five-character query in the same number of steps.

Space is the bad news, and it is why tries are rarer than the time complexity suggests. That Node above is an object with a HashMap in it. A map costs at least 48 bytes empty, plus an entry per child, plus a boxed Character key for each. A word of ten characters can cost several hundred bytes of structure — for a word that is ten bytes of text.

The standard mitigations, in the order you would reach for them:

• An array instead of a map, when the alphabet is small and fixed: Node[] next = new Node[26]. Faster and no boxing, and it wastes 26 slots on every node — which is a win only when nodes are dense.
• A radix tree (or Patricia trie), which collapses each chain of single-child nodes into one edge holding a whole substring. This is what production implementations use, and it removes most of the waste.
• Do not use a trie, which is the right answer more often than the structure's fame suggests.

#When it is actually worth it

• Autocomplete and type-ahead. The case it is famous for, and the honest one.
• Routing tables. Matching the longest prefix is exactly a trie walk — which is what IP routing does, and what an HTTP router does with paths.
• Dictionary work where you need all words with a prefix, or need to say "no word starts with this" early — a word-game solver, a spell checker.

And when it is not:

• Exact lookup only. A HashSet is faster and far smaller.
• Ranges over sortable keys. A TreeMap's subMap already does that, is in the library, and is tested.
• A small dictionary. Ten thousand words scanned with startsWith is a millisecond, and a millisecond is not worth a hand-written structure.

#The one in the library, sort of

Java has no trie, but TreeMap gets you part of the way:

TreeMap<String, V> map = ...;
SortedMap<String, V> withPrefix = map.subMap(prefix, prefix + Character.MAX_VALUE);

Because the map is sorted, every key with that prefix sits in one contiguous range, and subMap gives you it in O(log n) plus the number of matches. That is not as good as a trie's O(m) and it is already written, already tested, and needs no new class — which for most applications is the better trade.

Reach for a real trie when the dictionary is large, the queries are many, and you have measured that subMap is not enough.