Fastest way to get all values from a Map where the key starts with a certain expression

Question

Consider you have a map<String, Object> myMap.

Given the expression "some.string.*", I have to retrieve all the values from myMap whose keys starts with this expression.

I am trying to avoid for loops because myMap will be given a set of expressions not only one and using for loop for each expression becomes cumbersome performance wise.

What is the fastest way to do this?

Answer 1

If you work with NavigableMap (e.g. TreeMap), you can use benefits of underlying tree data structure, and do something like this (with O(lg(N)) complexity):

public SortedMap<String, Object> getByPrefix(          NavigableMap<String, Object> myMap,          String prefix ) {     return myMap.subMap( prefix, prefix + Character.MAX_VALUE ); } 

More expanded example:

import java.util.NavigableMap; import java.util.SortedMap; import java.util.TreeMap;  public class Test {      public static void main( String[] args ) {         TreeMap<String, Object> myMap = new TreeMap<String, Object>();         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<String, Object> getByPrefix(             NavigableMap<String, Object> myMap,             String prefix ) {         return myMap.subMap( prefix, prefix + Character.MAX_VALUE );     } } 

Output is:

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}