How to remove duplicate key-value pairings in a map

Question

I'm stuck on how to transfer key-value pairs from map1 into map2 only if each key has a unique value in map1.

Let's say I have the following maps:

• map1: [1,2] [2,4] [4,4]
• map2: [1,2] [2,4]

I suppose the algorithm would be:

1. Loop through entries in the first map.
2. Add a key to map2.
3. Add a value to a set which checks against the values of map2
4. If the values are duplicate the value doesn't get added to the set and disregard adding its corresponding key to map2.

Code snippet:

public static <K,V> Map<K,V> unique (Map<K,V> m) {
  Map<K,V> newMap = new ArrayMap<K,V>();

  //Remember all values in the newMap.
  Set<V> holding = new ArraySet<V>(newMap.values());

  for (Map.Entry<K, V> graphEntry : m.entries()) {
     //not sure.
  }

  return newMap;  
}

Is my idea of how its supposed to be done on the right track? Quite lost here.

Solution

From a Map<K, V> create a Map<V, K> that will add the item if and only if the key is not in the map. Using this Map<V, K>, recreate your Map<K, V>.

public static <K, V> Map<K, V> createMap(Map<K, V> m) {
    Map<K, V> map = new HashMap<K, V>();
    Map<V, K> tmpMap = new HashMap<V, K>();
    for(Map.Entry<K, V> entry : m.entrySet()) {
        if (!tmpMap.containsKey(entry.getValue())) {
            tmpMap.put(entry.getValue(), entry.getKey());
        }
    }
    for(Map.Entry<V, K> entry : tmpMap.entrySet()) {
        map.put(entry.getValue(), entry.getKey());
    }
    return map;
}

If you need to keep the preserver order of the data, use LinkedHashMap instead of HashMap.