How to remove duplicate key-value pairings in a map

2
votes

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.

3
javamapkey-value
Do you want to add pairs from map1 to map2 and avoid overwrting the values in map2? - svz
can you post your requested out-pot? - elyashiv
Why doesn't your algorithm produce a map2 of {1:2,4:4}? Why do you choose 2? Does it not matter? - cheeken
Two keys in map1 have a value of 4, [2,4] and [4,4]. The other map would only have the first two keys from map1, [1,2] [2,4]. It would have to be 2:4 because it goes through each key sequentially, so when it hits 4:4 it would count as a duplicate. - nitiger

3 Answers

4
votes

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.

0
votes

Check out Guava BiMap.. This is what you need..

Although your problem is solved, you can take a look at the below code, to use Guava API for what you want to do: -

public void removeDuplicateValue() {
    Map<Integer, String> existingMap = new HashMap<Integer, String>();
    existingMap.put(1, "a");
    existingMap.put(2, "b");

    // Create a new BiMap
    BiMap<Integer, String> biMap = HashBiMap.create();

    for (Integer val: existingMap.keySet()) {

        // forcePut will add a key-value pair, and overwrite the duplicate value.
        biMap.forcePut(val, existingMap.get(val));
    }

    // Create Inverse Map for newly created BiMap.
    BiMap<String, Integer> inverseBiMap = biMap.inverse();

    for(String val: inverseBiMap.keySet()) {
        System.out.println(val + ":" + biMap.get(val));
    }
}
0
votes

Try this one.. 

 Map<String, String> myMap1 = new TreeMap<String, String>();
 myMap1.put("1", "One");
 myMap1.put("2", "Two");
 myMap1.put("3", "One");
 myMap1.put("4", "Three");
 myMap1.put("5", "Two");
 myMap1.put("6", "Three");

 Set<String> mySet = new HashSet<String>();

 for (Iterator itr = myMap1.entrySet().iterator(); itr.hasNext();)
 {
    Map.Entry<String, String> entrySet = (Map.Entry) itr.next();

    String value = entrySet.getValue();

    if (!mySet.add(value))
    {
        itr.remove();               
    }
 } 

  Map<String, String> myMap2 = new TreeMap<String, String>(myMap1);   

  System.out.println("Result :"+myMap2);

Result :{1=One, 2=Two, 4=Three}