java - 在 Map 实现中搜索前缀的最佳方法是什么？

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”。键应返回两个值。

我们应该使用 Java 中的哪种数据结构，因为 Trie DS 实现不可用。我能想到的下一个最好的就是 LinkedHashMap

Answer 1

您正在寻找 Apache Patricia Trie .它是您的用例的确切数据结构。

来自他们的文档:

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.

特别是 prefixMap(prefix) operation返回一个 SortedMap View ，其中包含与给定前缀匹配的所有条目。

同样，来自文档:

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'.