Search for key in Map when the values are in ArrayList

Question

I am new to the collections in Java , I have a HashMap<String, List<String>>. I want to search for a key from the Map when a value is given.

The map stores the data of a state as key and its cities as the list. So it is assumed that there is no duplicate key or value.

Some of the previous answers pointed out the solutions for many:many and one:one relations of key-value in map, but I don't understand how to check for value in the List.

Do I iterate over the whole map and for each key get the list and search in the list? or is there any other way of doing this?

Please suggest some method. Thank you!

Answer 1

You should make inverted map (city -> state map).

public Map<String, String> invertedMap(Map<String, List<String>> map) {
    Map<String, String> inverted = new HashMap<>();
    for (Entry<String, List<String>> e : map.entrySet())
        for (String city : e.getValue())
            inverted.put(city, e.getKey() /* state */);
    return inverted;
}

Answer 2

A map is meant to allow fast access to a value by using a key. Doing it the other way round would require you to iterate over all values and look for that. Additionally you need to be aware that the same (or an equal) value could be stored for multiple keys.

In order to efficiently search for all the states for a given city name you could employ an inverse map where the city name is the key and the value is a collection of states (assuming there are several cities each in a different state - e.g. there seem to be multiple Springfield in the US).

An easy way to create such an inverted map would be to use Guava's Multimap for the initial map (state -> cities) and then use Multimaps.invertFrom(intialMap);.

Edit: In reference to Brett Walker's comment, Apache Commons Collections' BidiMap seems to follow a similar approach, i.e. the AbstractDualBidiMap implementation internally uses two maps as described above.

Answer 3

I would use the BidiMap from the Apache Common Collection library as a starting point.

For the List<String> part I would look at using the MultiValueMap as it decorates another map, allowing it to have more than one value for a key.

I've used the BidiMap bit not the MultiValueMap. I'm thinking that both would be useful.