Java Determine If String Starts With Key In Map

I want to determine if a given String startsWith any key in a Map.

The simple solution is to iterate through entire the keySet.

private static Map<String, String> someMap;

private static void method(String line) {
    for (String key : someMap.keySet()) {
        if (line.startsWith(key)) {
            // do something with someMap.get(key);
        }
    }
}

My question is: Is there is a better data structure to handle this problem?

Answer

This can’t be done directly with an HashMap: the problem is that HashMap uses an hash calculated on the key to manage its position inside the collection. So there is no way to search for a String key which starts with a specific substring since there is no correlation between two similar String values and their hashes.

But nothing is lost, if you switch to a TreeMap<String,String> the problem can be solved easily. A TreeMap is still an associative container but it stores entries by using a red-black tree in a sorted order.

This means that elements inside a TreeMap are always sorted. In addition to this it gives you some functionalities like:

• Map.Entry<K,V> ceilingEntry(K key): Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.

• Map.Entry<K,V> floorEntry(K key): Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.

Now, not only you can search for a specific key by using a substring of its value, but you also do it in an efficient way. Mind that this works thanks to the implementation of compareTo of String class.

So your problem becomes trivial:

TreeMap<String, Object> map = new TreeMap<String, Object>();

map.put("baz", new Object());
map.put("foo", new Object());
map.put("fooz", new Object());
map.put("fo", new Object());

Map.Entry<String, Object> test = map.ceilingEntry("fo");
bool containsSubStringKey = test != null && test.getKey().startsWith("fo");