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!

Have a look at the `Apache Common Collection` library. They have a `BidiMap` - a bidirectional map, and a `MultiValueMap` - decorates another map, allowing it to have more than one value for a key. These and others may be of use or interest. — Brett Walker, Jun 16 '15 at 12:16
@BrettWalker Thank you for the response, can't we use the java api's for the same? I want to avoid the use of any extra libraries. — HitchHiker, Jun 16 '15 at 12:19
I can understand not wanting to include additional libraries, if you can avoid it. But the two suggestions I mad are not trivial and what you are asking is not found in the Java Collections. — Brett Walker, Jun 16 '15 at 12:26
@BrettWalker Oh i guess i will have to do it the hard way :) — HitchHiker, Jun 16 '15 at 12:29

score 1 · Accepted Answer · answered Jun 16 '15 at 12:32

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;
}

answered Jun 16 '15 at 12:32

Thank you for the solution! I am trying it out now, i hope this will make the task easier :) – HitchHiker Jun 16 '15 at 12:46
@vaishnavee If two states have same city name, The inverted map must be Map>. Be careful! – Jun 16 '15 at 12:52
Yes that would be mostly the case and i will have to handle it for some generalized data, but in my application there is no need for that as there is definitely no duplication :) and the solution worked smoothly! thank you – HitchHiker Jun 16 '15 at 12:56

Thomas · Answer 2 · 2015-06-16T12:19:49.547

0

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.

edited Jun 16 '15 at 12:19

answered Jun 16 '15 at 12:13

Thomas

87,414
12
119
157

I feel this question may help the OP: http://stackoverflow.com/questions/1383797/java-hashmap-how-to-get-key-from-value – Adam Jun 16 '15 at 12:21
@Thomas Thank you for the response, I already said that there is no duplication of key-value in the data that i am working on. Is it not possible to use only Java Collection API's? – HitchHiker Jun 16 '15 at 12:22
@WhyCry Yes that was the same answer that i was referring to, but it did not explain the List value part – HitchHiker Jun 16 '15 at 12:23
@vaishnavee there is a way, it's just not that easy. You'd have to maintain the two maps yourself, e.g. by writing your own version of `BidiMap` etc. – Thomas Jun 16 '15 at 12:24
@Thomas well i am new to all this... but i guess i will have to try still try it :) – HitchHiker Jun 16 '15 at 12:29

score 0 · Answer 3 · answered Jun 16 '15 at 12:30

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.

Search for key in Map when the values are in ArrayList

3 Answers3