在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." key应该返回两个值.

我们应该使用哪种数据结构作为Trie DS实现不可用.我能想到的下一个最好的只是LinkedHashMap

Answer 1

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

从他们的文档:

PATRICIA Trie是一个压缩的Trie.PATRICIA不是将所有数据存储在Trie的边缘(并且具有空的内部节点),而是将数据存储在每个节点中.这允许非常有效的遍历,插入,删除,前驱,后继,前缀,范围和选择(对象)操作.所有操作在O(K)时间内最差地执行,其中K是树中最大项目中的位数.实际上,操作实际上需要O(A(K))时间,其中A(K)是树中所有项目的平均位数.

最重要的是,PATRICIA在进行任何操作时都需要很少地与键进行比较.在执行查找时,每次比较(最多K个,如上所述)将对给定键执行单个位比较,而不是将整个键与另一个键进行比较.

特别是,该prefixMap(prefix)操作返回一个SortedMap视图,其中包含与给定前缀匹配的所有条目.

再次,从文档:

例如,如果Trie包含'Anna','Anael','Analu','Andreas','Andrea','Andres'和'Anatole',则查找'And'将返回'Andreas',' Andrea'和'Andres'.

Answer 2

有另一个按前缀索引的映射。特别是使用 Guava Multimap，它允许将键映射到集合值。