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

dictionary, java

Solution

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}

Problem

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 loop`s 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?

Original source