从键中以某个表达式开始的Map获取所有值的最快方法
考虑你有一个map myMap 。
给定表达式"some.string.*" ，我必须从myMap检索其键以此表达式开头的所有值。
我试图避免for loop s因为myMap将被赋予一组表达式，而不仅仅是一个表达式，并且每个表达式使用for loop变得非常麻烦。
最快的方法是什么？
如果您使用NavigableMap （例如TreeMap ），您可以使用底层树数据结构的好处，并执行类似这样的操作（具有O(lg(N))复杂度）：
public SortedMap getByPrefix( NavigableMap myMap, String prefix ) { return myMap.subMap( prefix, prefix + Character.MAX_VALUE ); }
更多扩展示例：
import java.util.NavigableMap; import java.util.SortedMap; import java.util.TreeMap; public class Test { public static void main( String[] args ) { TreeMap myMap = new TreeMap(); myMap.put( "111-hello", null ); myMap.put( "111-world", null ); myMap.put( "111-test", null ); myMap.put( "111-java", null ); myMap.put( "123-one", null ); myMap.put( "123-two", null ); myMap.put( "123--three", null ); myMap.put( "123--four", null ); myMap.put( "125-hello", null ); myMap.put( "125--world", null ); System.out.println( "111 \t" + getByPrefix( myMap, "111" ) ); System.out.println( "123 \t" + getByPrefix( myMap, "123" ) ); System.out.println( "123-- \t" + getByPrefix( myMap, "123--" ) ); System.out.println( "12 \t" + getByPrefix( myMap, "12" ) ); } private static SortedMap getByPrefix( NavigableMap myMap, String prefix ) { return myMap.subMap( prefix, prefix + Character.MAX_VALUE ); } }
输出是：
111 {111-hello=null, 111-java=null, 111-test=null, 111-world=null} 123 {123--four=null, 123--three=null, 123-one=null, 123-two=null} 123-- {123--four=null, 123--three=null} 12 {123--four=null, 123--three=null, 123-one=null, 123-two=null, 125--world=null, 125-hello=null}
我最近写了一个MapFilter来满足这样的需求。 您还可以过滤过滤后的地图，这些地图非常有用。
如果你的表达式有像“some.byte”和“some.string”这样的共同根，那么首先通过公共根进行过滤（在这种情况下是“some。”）将为你节省大量时间。 有关一些简单的例子，请参阅main 。
请注意，对过滤后的地图进行更改会更改基础地图。
public class MapFilter implements Map { // The enclosed map -- could also be a MapFilter. final private Map map; // Use a TreeMap for predictable iteration order. // Store Map.Entry to reflect changes down into the underlying map. // The Key is the shortened string. The entry.key is the full string. final private Map> entries = new TreeMap<>(); // The prefix they are looking for in this map. final private String prefix; public MapFilter(Map map, String prefix) { // Store my backing map. this.map = map; // Record my prefix. this.prefix = prefix; // Build my entries. rebuildEntries(); } public MapFilter(Map map) { this(map, ""); } private synchronized void rebuildEntries() { // Start empty. entries.clear(); // Build my entry set. for (Map.Entry e : map.entrySet()) { String key = e.getKey(); // Retain each one that starts with the specified prefix. if (key.startsWith(prefix)) { // Key it on the remainder. String k = key.substring(prefix.length()); // Entries k always contains the LAST occurrence if there are multiples. entries.put(k, e); } } } @Override public String toString() { return "MapFilter(" + prefix + ") of " + map + " containing " + entrySet(); } // Constructor from a properties file. public MapFilter(Properties p, String prefix) { // Properties extends HashTable so it implements Map. // I need Map so I wrap it in a HashMap for simplicity. // Java-8 breaks if we use diamond inference. this(new HashMap<>((Map) p), prefix); } // Helper to fast filter the map. public MapFilter filter(String prefix) { // Wrap me in a new filter. return new MapFilter<>(this, prefix); } // Count my entries. @Override public int size() { return entries.size(); } // Are we empty. @Override public boolean isEmpty() { return entries.isEmpty(); } // Is this key in me? @Override public boolean containsKey(Object key) { return entries.containsKey(key); } // Is this value in me. @Override public boolean containsValue(Object value) { // Walk the values. for (Map.Entry e : entries.values()) { if (value.equals(e.getValue())) { // Its there! return true; } } return false; } // Get the referenced value - if present. @Override public T get(Object key) { return get(key, null); } // Get the referenced value - if present. public T get(Object key, T dflt) { Map.Entry e = entries.get((String) key); return e != null ? e.getValue() : dflt; } // Add to the underlying map. @Override public T put(String key, T value) { T old = null; // Do I have an entry for it already? Map.Entry entry = entries.get(key); // Was it already there? if (entry != null) { // Yes. Just update it. old = entry.setValue(value); } else { // Add it to the map. map.put(prefix + key, value); // Rebuild. rebuildEntries(); } return old; } // Get rid of that one. @Override public T remove(Object key) { // Do I have an entry for it? Map.Entry entry = entries.get((String) key); if (entry != null) { entries.remove(key); // Change the underlying map. return map.remove(prefix + key); } return null; } // Add all of them. @Override public void putAll(Map m) { for (Map.Entry e : m.entrySet()) { put(e.getKey(), e.getValue()); } } // Clear everything out. @Override public void clear() { // Just remove mine. // This does not clear the underlying map - perhaps it should remove the filtered entries. for (String key : entries.keySet()) { map.remove(prefix + key); } entries.clear(); } @Override public Set keySet() { return entries.keySet(); } @Override public Collection values() { // Roll them all out into a new ArrayList. List values = new ArrayList<>(); for (Map.Entry v : entries.values()) { values.add(v.getValue()); } return values; } @Override public Set> entrySet() { // Roll them all out into a new TreeSet. Set> entrySet = new TreeSet<>(); for (Map.Entry> v : entries.entrySet()) { entrySet.add(new Entry<>(v)); } return entrySet; } /** * An entry. * * @param The type of the value. */ private static class Entry implements Map.Entry, Comparable> { // Note that entry in the entry is an entry in the underlying map. private final Map.Entry> entry; Entry(Map.Entry> entry) { this.entry = entry; } @Override public String getKey() { return entry.getKey(); } @Override public T getValue() { // Remember that the value is the entry in the underlying map. return entry.getValue().getValue(); } @Override public T setValue(T newValue) { // Remember that the value is the entry in the underlying map. return entry.getValue().setValue(newValue); } @Override public boolean equals(Object o) { if (!(o instanceof Entry)) { return false; } Entry e = (Entry) o; return getKey().equals(e.getKey()) && getValue().equals(e.getValue()); } @Override public int hashCode() { return getKey().hashCode() ^ getValue().hashCode(); } @Override public String toString() { return getKey() + "=" + getValue(); } @Override public int compareTo(Entry o) { return getKey().compareTo(o.getKey()); } } // Simple tests. public static void main(String[] args) { String[] samples = { "Some.For.Me", "Some.For.You", "Some.More", "Yet.More"}; Map map = new HashMap(); for (String s : samples) { map.put(s, s); } Map all = new MapFilter(map); Map some = new MapFilter(map, "Some."); Map someFor = new MapFilter(some, "For."); System.out.println("All: " + all); System.out.println("Some: " + some); System.out.println("Some.For: " + someFor); Properties props = new Properties(); props.setProperty("namespace.prop1", "value1"); props.setProperty("namespace.prop2", "value2"); props.setProperty("namespace.iDontKnowThisNameAtCompileTime", "anothervalue"); props.setProperty("someStuff.morestuff", "stuff"); Map filtered = new MapFilter(props, "namespace."); System.out.println("namespace props " + filtered); } }
map的键集没有特殊的结构，所以我认为你必须检查每个键。 所以你找不到比单循环更快的方法……
我使用此代码进行速度试用：
public class KeyFinder { private static Random random = new Random(); private interface Receiver { void receive(String value); } public static void main(String[] args) { for (int trials = 0; trials < 10; trials++) { doTrial(); } } private static void doTrial() { final Map map = new HashMap(); giveRandomElements(new Receiver() { public void receive(String value) { map.put(value, null); } }, 10000); final Set expressions = new HashSet (); giveRandomElements(new Receiver() { public void receive(String value) { expressions.add(value); } }, 1000); int hits = 0; long start = System.currentTimeMillis(); for (String expression : expressions) { for (String key : map.keySet()) { if (key.startsWith(expression)) { hits++; } } } long stop = System.currentTimeMillis(); System.out.printf("Found %s hits in %s ms\n", hits, stop - start); } private static void giveRandomElements(Receiver receiver, int count) { for (int i = 0; i < count; i++) { String value = String.valueOf(random.nextLong()); receiver.receive(value); } } }
输出是：
Found 0 hits in 1649 ms Found 0 hits in 1626 ms Found 0 hits in 1389 ms Found 0 hits in 1396 ms Found 0 hits in 1417 ms Found 0 hits in 1388 ms Found 0 hits in 1377 ms Found 0 hits in 1395 ms Found 0 hits in 1399 ms Found 0 hits in 1357 ms
这计算10000个随机密钥中的多少个以1000个随机字符串值（10M检查）中的任何一个开头。
所以在简单的双核笔记本电脑上大约需要1.4秒; 这对你来说太慢了吗？