Infinite loop when using a key multiple times in HashMap

Question

HashMap falls into an infinite loop.

I am not able to understand why HashMap throws stackoverflow error when the same key is used multiple times.

Code:

import java.util.HashMap;

public class Test {
    public static void main(String[] args) {
        HashMap hm = new HashMap();

        hm.put(hm, "1");
        hm.put(hm, "2");
    }
} 

Error:

Exception in thread "main" java.lang.StackOverflowError

Answer 1

It is not possible to add to a Map itself as a key. From javadoc:

A special case of this prohibition is that it is not permissible for a map to contain itself as a key.

---

The problem is that you are using as key not a standard object (any object with well defined equals and hashCode methods, that is not the map itself), but the map itself.

The problem is on how the hashCode of the HashMap is calculated:

public int hashCode() {
   int h = 0;
   Iterator<Entry<K,V>> i = entrySet().iterator();
   while (i.hasNext())
       h += i.next().hashCode();
   return h;
}

As you can see, to calculate the hashCode of the map, it iterates over all the elements of the map. And for each element, it calculates the hashCode. Because the only element of the map has as key is the map itself, it becomes a source of recursion.

Replacing the map with another object that can be used as key (with well defined equals and hashCode) will work:

import java.util.HashMap;

 public class Test {
   public static void main(String[] args) {
     HashMap hm = new HashMap();

     String key = "k1";
     hm.put(key, "1");
     hm.put(key, "2");
   }
} 

Answer 2

Problem is not that hash map blows up the stack for "same key" entered twice, but because your particular choice of map key. You are adding hash map to itself.

To explain better - part of Map contract is that keys must not change in a way that affects their equals (or hashCode for that matter) methods.

When you added map to itself as a key, you changed key (map) in a way that is making it return different hashCode than when you first added map.

For more information this is from JDK dock for Map interface:

Note: great care must be exercised if mutable objects are used as map keys. The behavior of a map is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is a key in the map. A special case of this prohibition is that it is not permissible for a map to contain itself as a key. While it is permissible for a map to contain itself as a value, extreme caution is advised: the equals and hashCode methods are no longer well defined on such a map.