What is the best way to search prefixes in a Map implementation?

Question

LinkedHashMap.put("a.a1","11");        
LinkedHashMap.put("a.a12","12");        
LinkedHashMap.put("b.b1","13");        
LinkedHashMap.put("c.c1","14");        
LinkedHashMap.put("c.c1","15");          

A search on "a." key should return two values.

Which data structure in java should we be using as Trie DS implementation is not available. The next best which i could think of was only LinkedHashMap

Answer 1

You're looking for the Apache Patricia Trie. It is the exact data-structure for your use case.

From their docs:

A PATRICIA Trie is a compressed Trie. Instead of storing all data at the edges of the Trie (and having empty internal nodes), PATRICIA stores data in every node. This allows for very efficient traversal, insert, delete, predecessor, successor, prefix, range, and select(Object) operations. All operations are performed at worst in O(K) time, where K is the number of bits in the largest item in the tree. In practice, operations actually take O(A(K)) time, where A(K) is the average number of bits of all items in the tree.

Most importantly, PATRICIA requires very few comparisons to keys while doing any operation. While performing a lookup, each comparison (at most K of them, described above) will perform a single bit comparison against the given key, instead of comparing the entire key to another key.

In particular, the prefixMap(prefix) operation returns a SortedMap view with all the entries that match the given prefix.

Again, from the docs:

For example, if the Trie contains 'Anna', 'Anael', 'Analu', 'Andreas', 'Andrea', 'Andres', and 'Anatole', then a lookup of 'And' would return 'Andreas', 'Andrea', and 'Andres'.