java - 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 " + getByPrefix( myMap, "111" ) );
        System.out.println( "123 " + getByPrefix( myMap, "123" ) );
        System.out.println( "123-- " + getByPrefix( myMap, "123--" ) );
        System.out.println( "12 " + 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}