StackOverflowError while getting map entry

[Astha Sharma]

Why does the code below generates StackOverflowError?

import java.util.*;
public class test {	
	
  public static void main(String[] args) {
      Map m=new HashMap();
	Map m2=new HashMap();
	m2.put(m2,1);
	try{
	m2.get(m2);
	}
	catch(Throwable e){
	System.out.print(e);
	}
  }
}

output-
java.lang.StackOverflowError

[Andrea Binello]

Astha Sharma wrote:Why does the code below generates StackOverflowError?

This is a bit tricky. When you do a get on a hash-table based map, the map must first calculate the hashCode of the key. In the above code, the key is the HashMap m2. The hashCode of HashMap (see source code of AbstractMap) is the sum of hash codes from all Entries. The Entry calculates its hashCode using hashCode of key and value. But one key is the map m2 (put just before) .... and so calculates the hashCode of m2 using all entries .... and this goes theoretically to the infinite ..... causing somewhere a StackOverflowError.

[Sidharth Khattri]

Andrea Binello wrote:

Astha Sharma wrote:Why does the code below generates StackOverflowError?

This is a bit tricky. When you do a get on a hash-table based map, the map must first calculate the hashCode of the key. In the above code, the key is the HashMap m2. The hashCode of HashMap (see source code of AbstractMap) is the sum of hash codes from all Entries. The Entry calculates its hashCode using hashCode of key and value. But one key is the map m2 (put just before) .... and so calculates the hashCode of m2 using all entries .... and this goes theoretically to the infinite ..... causing somewhere a StackOverflowError.

But there's nothing in m2, why would it infinitely calculate the hashcode for m2?

[Astha Sharma]

Thanks for such nice explanation Andrea

Sidharth Khattri wrote:

Andrea Binello wrote:

Astha Sharma wrote:Why does the code below generates StackOverflowError?

This is a bit tricky. When you do a get on a hash-table based map, the map must first calculate the hashCode of the key. In the above code, the key is the HashMap m2. The hashCode of HashMap (see source code of AbstractMap) is the sum of hash codes from all Entries. The Entry calculates its hashCode using hashCode of key and value. But one key is the map m2 (put just before) .... and so calculates the hashCode of m2 using all entries .... and this goes theoretically to the infinite ..... causing somewhere a StackOverflowError.

But there's nothing in m2, why would it infinitely calculate the hashcode for m2?

For calculating hashcode of HashMap m2, it is needed to retrive hashcodes of all entries of HashMap m2. m2 is itself an entry inside m2. Thus process of retrieving hashcode for m2 will go on recursively.

[Andrea Binello]

Sidharth Khattri wrote:But there's nothing in m2, why would it infinitely calculate the hashcode for m2?

There is one entry, added with:

m2.put(m2,1);

and the entry's key is a map, exactly that same map m2.

When you do m2.get(m2) the following things happen:

- calculation of hashCode for the key parameter (m2)
- m2 is a HashMap, its hashCode is calculated from all entries.
- one entry is m2-->1. The Entry calculates its hashCode XORing together hashCodes of key and value. But the key is a map (again m2).
- m2 is a HashMap, its hashCode is calculated from all entries.
- one entry is m2-->1. The Entry calculates its hashCode XORing together hashCodes of key and value. But the key is a map (again m2).
.......

[Sidharth Khattri]

Astha Sharma wrote:Thanks for such nice explanation Andrea

Sidharth Khattri wrote:

Andrea Binello wrote:

Astha Sharma wrote:Why does the code below generates StackOverflowError?

This is a bit tricky. When you do a get on a hash-table based map, the map must first calculate the hashCode of the key. In the above code, the key is the HashMap m2. The hashCode of HashMap (see source code of AbstractMap) is the sum of hash codes from all Entries. The Entry calculates its hashCode using hashCode of key and value. But one key is the map m2 (put just before) .... and so calculates the hashCode of m2 using all entries .... and this goes theoretically to the infinite ..... causing somewhere a StackOverflowError.

But there's nothing in m2, why would it infinitely calculate the hashcode for m2?

For calculating hashcode of HashMap m2, it is needed to retrive hashcodes of all entries of HashMap m2. m2 is itself an entry inside m2. Thus process of retrieving hashcode for m2 will go on recursively.

Andrea Binello wrote:

Sidharth Khattri wrote:But there's nothing in m2, why would it infinitely calculate the hashcode for m2?

There is one entry, added with:

m2.put(m2,1);

and the entry's key is a map, exactly that same map m2.

When you do m2.get(m2) the following things happen:

- calculation of hashCode for the key parameter (m2)
- m2 is a HashMap, its hashCode is calculated from all entries.
- one entry is m2-->1. The Entry calculates its hashCode XORing together hashCodes of key and value. But the key is a map (again m2).
- m2 is a HashMap, its hashCode is calculated from all entries.
- one entry is m2-->1. The Entry calculates its hashCode XORing together hashCodes of key and value. But the key is a map (again m2).
.......

Thank you. Now I got it

[Sidharth Khattri]

:P

[Mala Gupta]

Here's the implementation of method 'hashCode' in class 'AbstractMap', which is inherited by class 'HashMap':

    /**
     * Returns the hash code value for this map.  The hash code of a map is
     * defined to be the sum of the hash codes of each entry in the map's
     * <tt>entrySet()</tt> view.  This ensures that <tt>m1.equals(m2)</tt>
     * implies that <tt>m1.hashCode()==m2.hashCode()</tt> for any two maps
     * <tt>m1</tt> and <tt>m2</tt>, as required by the general contract of
     * {@link Object#hashCode}.
     *
     * <p>This implementation iterates over <tt>entrySet()</tt>, calling
     * {@link Map.Entry#hashCode hashCode()} on each element (entry) in the
     * set, and adding up the results.
     *
     * @return the hash code value for this map
     * @see Map.Entry#hashCode()
     * @see Object#equals(Object)
     * @see Set#equals(Object)
     */
    public int hashCode() {
        int h = 0;
        Iterator<Entry<K,V>> i = entrySet().iterator();
        while (i.hasNext())
            h += i.next().hashCode();
        return h;
    }

If you are in doubt about the behaviour of a class or method, try to check its source code (if it is accessible).

With respect,
Mala

[Astha Sharma]

Thanks Mala