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

Solution 1

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

Solution 2

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).

Solution 3

If Java 8 is an option, you could try a streaming approach:

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

Map<String, ArrayList<Integer>> reverseMap = new HashMap<>(
    map.entrySet().stream()
        .collect(Collectors.groupingBy(Map.Entry::getValue)).values().stream()
        .collect(Collectors.toMap(
                item -> item.get(0).getValue(),
                item -> new ArrayList<>(
                    item.stream()
                        .map(Map.Entry::getKey)
                        .collect(Collectors.toList())
                ))
        ));

System.out.println(reverseMap);

Which results in:

{x=[1, 3], y=[2], z=[4]}

If Java 7 is preferred:

Map<String, ArrayList<Integer>> reverseMap = new HashMap<>();

for (Map.Entry<Integer,String> entry : map.entrySet()) {
    if (!reverseMap.containsKey(entry.getValue())) {
        reverseMap.put(entry.getValue(), new ArrayList<>());
    }
    ArrayList<Integer> keys = reverseMap.get(entry.getValue());
    keys.add(entry.getKey());
    reverseMap.put(entry.getValue(), keys);
}

As an interesting aside, I experimented with the time required for each algorithm when executing large maps of (index,random('a'-'z') pairs.

              10,000,000        20,000,000
Java 7:         615 ms            11624 ms         
Java 8:        1579 ms             2176 ms

Solution 4

If you are open to using a library, use Google Guava's Multimaps utilities, specifically forMap() combined with invertFrom()

Solution 5

Yup, just brute force. You can make it fast by also storing a Multimap from Value -> Collection of Key, at the expense of memory and runtime cost for updates.

View more solutions