Core Data Structures

Tries

A trie (prefix tree) stores strings character by character along root-to-node paths, so every node represents a shared prefix. Lookup, insert, and prefix search all cost O(L) — proportional to key length, not to how many keys are stored.

Each edge is labeled with one character; a path from the root spells out a prefix, and marked nodes indicate a complete stored word
Search/insert/delete are O(L) where L is the key length — independent of how many other keys are in the trie
Shared prefixes are stored once, which can save substantial memory over storing full strings redundantly
Natural fit for autocomplete, spell-checkers, and IP routing (longest-prefix match)
A hash table beats a trie for plain exact-match lookup; a trie wins when you need prefix queries a hash table cannot answer at all

A minimal trie: insert and prefix search

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isWord;
}

class Trie {
    private final TrieNode root = new TrieNode();

    void insert(String word) {                  // O(L)
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            cur = cur.children.computeIfAbsent(c, k -> new TrieNode());
        }
        cur.isWord = true;
    }

    boolean startsWith(String prefix) {          // O(L) — a hash table cannot do this
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            cur = cur.children.get(c);
            if (cur == null) return false;
        }
        return true;
    }
}

Trie vs. hash table vs. sorted array for string keys
Operation	Trie	Hash table	Sorted array + binary search
Exact lookup	O(L)	O(L) avg (hashing the string)	O(L log n) — L per comparison
Prefix search ("all words starting with...")	O(L + results)	Not supported directly	O(L log n), then linear scan
Memory for many shared prefixes	Shared — often compact	One full copy per key	One full copy per key

The reason a trie answers prefix queries that a hash table structurally cannot: a hash function scrambles a key into an index with no relationship to keys that merely start with it. A trie's structure preserves that relationship directly — every prefix of a stored word is, by construction, a path from the root, so "does any word start with this prefix" is just "does this path exist," answered in O(L) regardless of how many words share or diverge from that prefix.