Java: How to get set of keys having same value in hashmap

Question

I have a hashmap as below:

1->x

2->y

3->x

4->z

Now i want to know all keys whose value is x (ans: [1,3] ). what is best way to do?

Brute force way is to just iterate over map and store all keys in array whose value is x.

Is there any efficient way for this.

Thanks

Answer 1

A hashmap is a structure that is optimized for associative access of the values using the keys, but is in no way better in doing the reverse then an array for instance. I don't think you can do any better then just iterate. Only way to improve efficiency is if you have a reverse hash map as well(i.e. hash map where you hold an array of keys pointing to a given value for all values).

Answer 2

You can use a MultiMap to easily get all those duplicate values.

Map<Integer, String> map = new HashMap<Integer, String>();
map.put(1, "x");
map.put(2, "y");
map.put(2, "z");
map.put(3, "x");
map.put(4, "y");
map.put(5, "z");
map.put(6, "x");
map.put(7, "y");

System.out.println("Original map: " + map);

Multimap<String, Integer> multiMap = HashMultimap.create();
for (Entry<Integer, String> entry : map.entrySet()) {
  multiMap.put(entry.getValue(), entry.getKey());
}
System.out.println();

for (Entry<String, Collection<Integer>> entry : multiMap.asMap().entrySet()) {
  System.out.println("Original value: " + entry.getKey() + " was mapped to keys: "
      + entry.getValue());
}

Prints out:

Original map: {1=x, 2=z, 3=x, 4=y, 5=z, 6=x, 7=y}

Original value: z was mapped to keys: [2, 5]
Original value: y was mapped to keys: [4, 7]
Original value: x was mapped to keys: [1, 3, 6]

Per @noahz's suggestion, forMap and invertFrom takes fewer lines, but is arguably more complex to read:

HashMultimap<String, Integer> multiMap =
    Multimaps.invertFrom(Multimaps.forMap(map), 
        HashMultimap.<String, Integer> create());

in place of:

Multimap<String, Integer> multiMap = HashMultimap.create();
for (Entry<Integer, String> entry : map.entrySet()) {
  multiMap.put(entry.getValue(), entry.getKey());
}