带密钥查找的java键值对作为“startswith”

我正在寻找一个存储键值对的集合，其中值应该基于键startswith的条件返回。例如
对于给定的集合：(a,123) (ab,234) (abcd,5434)带密钥查找的java键值对作为“startswith”

如果我做map.get(a)它应该给我的{123,234,5434}阵列，同样的，如果我这样做map.get(ab)它应该给我{234,5434}但在这种情况下，不{123}。

因此，它会查找所有具有完全匹配关键字或开头的值。
有什么建议吗？如果有东西已经存在，或者我可以写点什么？
谢谢！

2015-05-19 Dadu

+13

听起来有点像[线索]（ http://en.wikipedia.org/wiki/Trie）。 – Kevin

特别是，您可以使用Apache Commons Collections ['Trie']（https://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/Trie.html ）它可以做你想要的。他们有一个['PatriciaTrie']（https://commons.apache.org/proper/commons-collections/javadocs/api-release/org/apache/commons/collections4/trie/PatriciaTrie.html）实现 –

可以使用tailMap法TreeMap<String,Integer>做到这一点的串模式特殊的迭代器，并遍历而关键的结果匹配输入：

TreeMap<String,Integer> map = new TreeMap<String,Integer>(); 
map.put("a", 123); 
map.put("ab", 234); 
map.put("abcd", 5434); 
String myKey = "ab"; 
for (Map.Entry<String,Integer> e : map.tailMap(myKey).entrySet()) { 
    if (!e.getKey().startsWith(myKey)) { 
     break; 
    } 
    System.out.println(e.getValue()); 
}

Demo.

来源

2015-05-19 15:48:42 dasblinkenlight

使用一个TreeMap，并创建一个映射在你的TreeMap和搜索你正在寻找

来源

2015-05-19 15:47:46 ControlAltDel

但是wouldn'这种方法是一种线性时间搜索......这种方式在维护地图中的键值对时失败了。 –

搜索时间当然要取决于有多少元素符合你的字符串。但是使用TreeMap结构，可以快速消除大量元素。例如，如果您的搜索字符串以'a'开头，则树会有100万个元素（甚至是第一个字母分布），那么只需5次分支移动就会降低到大约31250个元素（百万）。 – ControlAltDel

+1同意。它将是线性的，但不一定是O（keyset.size（））。在大多数情况下，它的线性范围要小得多。 –

只是一个小的触摸上dasblinkenlight的解决方案：的Java 8个流API提供了关于环一个良好的感觉：

TreeMap<String,Integer> map = new TreeMap<String,Integer>(); 
    map.put("a", 123); 
    map.put("ab", 234); 
    map.put("abcd", 5434); 
    String myKey = "ab"; 

    Collection<Integer> matchValues = map.tailMap(myKey).entrySet() 
     .stream() 
     .filter(e -> e.getKey().startsWith(myKey)) 
     .map(e -> e.getValue()) 
     .collect(Collectors.toList());

来源

2015-05-19 16:18:05

我同意当然，我只是没有足够的代表评论... –

它是50.我当时低于那个数字。 –

继slanec的评论，我看着PatriciaTrie从Apache的百科全书Collections4它确实有一个方法，不正是OP问了：

import org.apache.commons.collections4.*; 
import org.apache.commons.collections4.trie.*; 

Trie<String,Integer> t = new PatriciaTrie<>(); 
t.put("a", 123); 
t.put("ab", 234); 
t.put("abcd", 5434); 
System.out.println(t.prefixMap("ab").values());

来源

2015-05-20 06:15:29

带密钥查找的java键值对作为“startswith”

回答

相关问题