What happens when a duplicate key is put into a HashMap?

Question

If I pass the same key multiple times to HashMap’s put method, what happens to the original value? And what if even the value repeats? I didn’t find any documentation on this.

Case 1: Overwritten values for a key

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","not one");
mymap.put("1","surely not one");
System.out.println(mymap.get("1"));

We get surely not one.

Case 2: Duplicate value

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","not one");
mymap.put("1","surely not one");
// The following line was added:
mymap.put("1","one");
System.out.println(mymap.get("1"));

We get one.

But what happens to the other values? I was teaching basics to a student and I was asked this. Is the Map like a bucket where the last value is referenced (but in memory)?

Teerell

BTW, this is an excellent opportunity to show off the multi-hashmap that is part of the Jakarta collections classes (commons.apache.org/collections). It will let you have any number of values associated with the same key for those times when you need that. – Taurus

possible duplicate of HashMap with multiple values under the same key – Irita

Duplicate keys are not allowed on a Map. If you need to add value for the same key refer https://mcmap.net/q/36396/-what-happens-when-a-duplicate-key-is-put-into-a-hashmap – Anoxemia

Answer 1

By definition, the put command replaces the previous value associated with the given key in the map (conceptually like an array indexing operation for primitive types).

The map simply drops its reference to the value. If nothing else holds a reference to the object, that object becomes eligible for garbage collection. Additionally, Java returns any previous value associated with the given key (or null if none present), so you can determine what was there and maintain a reference if necessary.

More information here: HashMap Doc

Laceylach

Thanks for this. Reading though the Java documentation this is not mentioned clearly. I am guessing the author of the doc assumed this to be a tacit assumption of all hash map implementations. – Cozen

I was reading the Java implementation and seems that when you insert a new key-value pair, it needs to iterate over all elements in the bucket to know if the key exists or not, so it can't just add one element at the end of the bucket. This makes the insertion not 100% O(1) – Amiss

Answer 2

You may find your answer in the javadoc of Map#put(K, V) (which actually returns something):

public V put(K key,
             V value)

Associates the specified value with the specified key in this map (optional operation). If the map previously contained a mapping for this key, the old value is replaced by the specified value. (A map m is said to contain a mapping for a key k if and only if m.containsKey(k) would return true.)

Parameters:
key - key with which the specified value is to be associated.
value - value to be associated with the specified key.

Returns:
previous value associated with specified key, or null if there was no mapping for key. (A null return can also indicate that the map previously associated null with the specified key, if the implementation supports null values.)

So if you don't assign the returned value when calling mymap.put("1", "a string"), it just becomes unreferenced and thus eligible for garbage collection.

Hi

The returned value is the previous value (or null) as documented just above in the javadoc so, yes, this is what I mean. Can it really be misinterpreted? – Hi

this is very helpful. – Northwesterly

Answer 3

it's Key/Value feature and you could not to have duplicate key for several values because when you want to get the actual value which one of values is belong to entered key
in your example when you want to get value of "1" which one is it ?!
that's reasons to have unique key for every value but you could to have a trick by java standard lib :

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class DuplicateMap<K, V> {

    private Map<K, ArrayList<V>> m = new HashMap<>();

    public void put(K k, V v) {
        if (m.containsKey(k)) {
            m.get(k).add(v);
        } else {
            ArrayList<V> arr = new ArrayList<>();
            arr.add(v);
            m.put(k, arr);
        }
    }

     public ArrayList<V> get(K k) {
        return m.get(k);
    }

    public V get(K k, int index) {
        return m.get(k).size()-1 < index ? null : m.get(k).get(index);
    }
}

and you could to use it in this way:

    public static void main(String[] args) {
    DuplicateMap<String,String> dm=new DuplicateMap<>();
    dm.put("1", "one");
    dm.put("1", "not one");
    dm.put("1", "surely not one");
    System.out.println(dm.get("1"));
    System.out.println(dm.get("1",1));
    System.out.println(dm.get("1", 5));
}

and result of prints are :

[one, not one, surely not one]
not one
null

Kirk

Great answer! good job. You literally save my programming life :) . – Staton

Thanks from me as well! I did have to add a "remove" method to it to perform the same functionality as a normal Map but worked great! – Nonjuror

@Nonjuror your welcome dude , but this is not technical solution , that's what you can to do by java standard lib , in technically problem you must be watch on your problem , if you need to have this behavior i'm sure it's not solution because of Key/Value concept , and must be think about problem and find logical way to resolving . anyway my details is just fun way to do with java and in production , problems and pathway of resolve is very different to fun work ! but you could to use it when Key/Value behavior is not your problem and finding to have a data structure like that . – Kirk

Answer 4

It replaces the existing value in the map for the respective key. And if no key exists with the same name then it creates a key with the value provided. eg:

Map mymap = new HashMap();
mymap.put("1","one");
mymap.put("1","two");

OUTPUT key = "1", value = "two"

So, the previous value gets overwritten.

Beeson

Answer 5

The prior value for the key is dropped and replaced with the new one.

If you'd like to keep all the values a key is given, you might consider implementing something like this:

import org.apache.commons.collections.MultiHashMap;
import java.util.Set;
import java.util.Map;
import java.util.Iterator;
import java.util.List;
public class MultiMapExample {

   public static void main(String[] args) {
      MultiHashMap mp=new MultiHashMap();
      mp.put("a", 10);
      mp.put("a", 11);
      mp.put("a", 12);
      mp.put("b", 13);
      mp.put("c", 14);
      mp.put("e", 15);
      List list = null;

      Set set = mp.entrySet();
      Iterator i = set.iterator();
      while(i.hasNext()) {
         Map.Entry me = (Map.Entry)i.next();
         list=(List)mp.get(me.getKey());

         for(int j=0;j<list.size();j++)
         {
          System.out.println(me.getKey()+": value :"+list.get(j));
         }
      }
   }
}

Indiscrete

This solution is depricated. MultiHashMap is part of apache.commons.collections and not java. – Transliterate

Answer 6

Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the old value is replaced.

Wiretap

Answer 7

To your question whether the map was like a bucket: no.

It's like a list with name=value pairs whereas name doesn't need to be a String (it can, though).

To get an element, you pass your key to the get()-method which gives you the assigned object in return.

And a Hashmap means that if you're trying to retrieve your object using the get-method, it won't compare the real object to the one you provided, because it would need to iterate through its list and compare() the key you provided with the current element.

This would be inefficient. Instead, no matter what your object consists of, it calculates a so called hashcode from both objects and compares those. It's easier to compare two ints instead of two entire (possibly deeply complex) objects. You can imagine the hashcode like a summary having a predefined length (int), therefore it's not unique and has collisions. You find the rules for the hashcode in the documentation to which I've inserted the link.

If you want to know more about this, you might wanna take a look at articles on javapractices.com and technofundo.com

regards

Shawnee

Answer 8

Maps from JDK are not meant for storing data under duplicated keys.

• At best new value will override the previous ones.

• Worse scenario is exception (e.g when you try to collect it as a stream):

No duplicates:

Stream.of("one").collect(Collectors.toMap(x -> x, x -> x))

Ok. You will get: $2 ==> {one=one}

Duplicated stream:

Stream.of("one", "not one", "surely not one").collect(Collectors.toMap(x -> 1, x -> x))

Exception java.lang.IllegalStateException: Duplicate key 1 (attempted merging values one and not one) | at Collectors.duplicateKeyException (Collectors.java:133) | at Collectors.lambda$uniqKeysMapAccumulator$1 (Collectors.java:180) | at ReduceOps$3ReducingSink.accept (ReduceOps.java:169) | at Spliterators$ArraySpliterator.forEachRemaining (Spliterators.java:948) | at AbstractPipeline.copyInto (AbstractPipeline.java:484) | at AbstractPipeline.wrapAndCopyInto (AbstractPipeline.java:474) | at ReduceOps$ReduceOp.evaluateSequential (ReduceOps.java:913) | at AbstractPipeline.evaluate (AbstractPipeline.java:234) | at ReferencePipeline.collect (ReferencePipeline.java:578) | at (#4:1)

To deal with duplicated keys - use other package, e.g: https://google.github.io/guava/releases/19.0/api/docs/com/google/common/collect/Multimap.html

There is a lot of other implementations dealing with duplicated keys. Those are needed for web (e.g. duplicated cookie keys, Http headers can have same fields, ...)

Good luck! :)

Menton

is the "override" operation costly? – Depressive

It can be solved using JDK only. Collectors.toMap() has third argument - merge function. If we want to simply override last duplicate element: Stream.of("one", "two", "one").collect(Collectors.toMap(x -> x, x -> x, (key1, key2) -> key2)). link – Dejesus

Also your second code example is not correct. This input: "one", "not one", "surely not one" will not produce any duplicate key errors because of all strings different. – Dejesus

Hi @stand alone. Please read carefully the mapping function (toMap). – Menton

Hi @WitoldKaczurba. Please compile your code before posting. – Dejesus

HI @stand alone. Not sure about your comment. Used REPL and it does what it written. – Menton

Answer 9

I always used:

HashMap<String, ArrayList<String>> hashy = new HashMap<String, ArrayList<String>>();

if I wanted to apply multiple things to one identifying key.

public void MultiHash(){
    HashMap<String, ArrayList<String>> hashy = new HashMap<String, ArrayList<String>>();
    String key = "Your key";

    ArrayList<String> yourarraylist = hashy.get(key);

    for(String valuessaved2key : yourarraylist){
        System.out.println(valuessaved2key);
    }

}

you could always do something like this and create yourself a maze!

public void LOOK_AT_ALL_THESE_HASHMAPS(){
    HashMap<String, HashMap<String, HashMap<String, HashMap<String, String>>>> theultimatehashmap = new HashMap <String, HashMap<String, HashMap<String, HashMap<String, String>>>>();
    String ballsdeep_into_the_hashmap = theultimatehashmap.get("firststring").get("secondstring").get("thirdstring").get("forthstring");
}

Unrest

Answer 10

BTW, if you want some semantics such as only put if this key is not exist. you can use concurrentHashMap with putIfAbsent() function. Check this out:

https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentHashMap.html#put(K,%20V)

concurrentHashMap is thread safe with high performance since it uses "lock striping" mechanism to improve the throughput.

Gripsack

Answer 11

Yes, this means all the 1 keys with value are overwriten with the last added value and here you add "surely not one" so it will display only "surely not one".

Even if you are trying to display with a loop, it will also only display one key and value which have same key.

Libbie

Answer 12

Duplicate keys are not allowed on a Map.

    HashMap<Integer, String> mymap = new HashMap<Integer, String>();
    mymap.put("1","one");
    mymap.put("1", "not one");
    mymap.put("1", "surely not one");
    System.out.println("\nHashMap object output :" + hm);

HashMap object output :{1=surely not one}

The reason, HashMap stores key, value pairs and does not allow duplicate keys. If the key is duplicate then the old key is replaced with the new value.

If you need to store value for the same key use this.

Multimap<Integer , String> mymap = ArrayListMultimap.create();
 mymap.put("1","one");
 mymap.put("1", "not one");
 mymap.put("1", "surely not one");
 mymap.put("2","two");
 System.out.println("\nHashMap object output :" + hm);

HashMap object output :{1=[one, not one, geeks, surely not one], 2=[two]}

Anoxemia

Answer 13

         HashMap<Emp, Emp> empHashMap = new HashMap<Emp, Emp>();

         empHashMap.put(new Emp(1), new Emp(1));
         empHashMap.put(new Emp(1), new Emp(1));
         empHashMap.put(new Emp(1), new Emp());
         empHashMap.put(new Emp(1), new Emp());
         System.out.println(empHashMap.size());
    }
}

class Emp{
    public Emp(){   
    }
    public Emp(int id){
        this.id = id;
    }
    public int id;
    @Override
    public boolean equals(Object obj) {
        return this.id == ((Emp)obj).id;
    }

    @Override
    public int hashCode() {
        return id;
    }
}


OUTPUT : is 1

Means hash map wont allow duplicates, if you have properly overridden equals and hashCode() methods.

HashSet also uses HashMap internally, see the source doc

public class HashSet{
public HashSet() {
        map = new HashMap<>();
    }
}

Unwitnessed