Invert Map | Values ---> Keys

Question

I want to be able to inverse a given HashMap that has multiple keys can point to the same value.

HashMap<String, String> cities = new HashMap<String, String>();

        cities.put("Manchester", "UK");
        cities.put("London", "UK");

static HashMap<String, String> inverseMap(HashMap map) {
       // something that has "UK" point to both "Manchester" and "London"

      // if it can be done without using any special Java 8 feature, that would be great
}

I am unsure where to start.

Answer 1

Do it like this. Basically, it employs a merge function which concatenates values for a duplicate key.

• Create a new map
• Use the values of the old map for the keys to the new
• If the new map does not have a value for the key, put the value in the new map
• Otherwise, concatenate the value to the old value for that key

        HashMap<String, String> cities = new HashMap<String, String>();

        cities.put("Manchester", "UK");
        cities.put("London", "UK");
        cities.put("New York", "US");
        cities.put("Chicago", "US");

        Map<String,String> inverted = new HashMap<>();
        for (String key : cities.keySet()) {
            String newKey = cities.get(key);
            String value = inverted.get(newKey);
            if (value == null) {
                inverted.put(newKey, key);
            } else {
                value = value + ", " + key;
                inverted.put(newKey, value);
            }

        }
        for (Entry<String,String> e : inverted.entrySet()) {
            System.out.println(e.getKey() + " -> " + e.getValue());
        }

It prints

UK -> Manchester, London
US -> New York, Chicago

Since you didn't specify how to handle duplicate keys. I could also have stored it in a Map<String,List<String>>