How does Commons Collections' Trie support prefix-based lookups?

The Trie<K,V> interface, implemented by PatriciaTrie, organizes entries so that keys sharing a common prefix share the same internal path through the structure, rather than being scattered across independent hash buckets the way a HashMap would store them.

Trie<String, String> contacts = new PatriciaTrie<>();
contacts.put("mark", "Mark Twain");
contacts.put("martin", "Martin Fowler");
contacts.put("mary", "Mary Shelley");

SortedMap<String, String> matches = contacts.prefixMap("mar");
// {mark=Mark Twain, martin=Martin Fowler}

prefixMap(String prefix) returns a live SortedMap view containing only the entries whose keys start with the given prefix, computed by walking down the shared path segments that all matching keys have in common, rather than scanning every stored key one by one to check if it starts with the prefix.

This makes lookup cost proportional to the prefix length and the number of matches, not the total number of entries stored - a meaningful difference from a plain HashMap, which offers no structural shortcut for "give me everything starting with X" and would require an O(n) scan over every key to answer the same query. That's what makes PatriciaTrie well suited to autocomplete and prefix-search style features.