Recursive generic definitions and Stackoverflow in Java

Question

I'm writing an implementation of deterministic finite automata for some research project and there are some arcs which lead to the same state. I wrote this class for State , but I wonder why the code produces Stackoverflow:

 public class State extends HashMap<Character, HashSet<State>>
 {
    public static void main(String[]args)
    {
       State t=new State();
       t.addTransition('a',t);
       t.addTransition('b',t);
    }
    public void addTransition(Character symbol, State t )
    {
        if(!this.containsKey(symbol))
        {
            this.put(symbol, new HashSet<State>());
        }
        this.get(symbol).add(t);
    }
}

Surprisingly, there are no errors if I remove one of "addTransition" calls.

My Java version is JDK 1.6.37, operating system is Ubuntu Linux 12.04.

*UPD:*The stack trace is:

Exception in thread "main" java.lang.StackOverflowError
at java.util.HashMap$KeyIterator.<init>(HashMap.java:843)
at java.util.HashMap$KeyIterator.<init>(HashMap.java:843)
at java.util.HashMap.newKeyIterator(HashMap.java:857)
at java.util.HashMap$KeySet.iterator(HashMap.java:891)
at java.util.HashSet.iterator(HashSet.java:170)
at java.util.AbstractSet.hashCode(AbstractSet.java:122)
at java.util.HashMap$Entry.hashCode(HashMap.java:737)
at java.util.AbstractMap.hashCode(AbstractMap.java:494)
at java.util.AbstractSet.hashCode(AbstractSet.java:126)
at java.util.HashMap$Entry.hashCode(HashMap.java:737)
at java.util.AbstractMap.hashCode(AbstractMap.java:494)
at java.util.AbstractSet.hashCode(AbstractSet.java:126)
at java.util.HashMap$Entry.hashCode(HashMap.java:737)
...
at java.util.AbstractMap.hashCode(AbstractMap.java:494)
at java.util.AbstractSet.hashCode(AbstractSet.java:126)
at java.util.HashMap$Entry.hashCode(HashMap.java:737)
at java.util.AbstractMap.hashCode(AbstractMap.java:494)
at java.util.AbstractSet.hashCode(AbstractSet.java:126)
at java.util.HashMap$Entry.hashCode(HashMap.java:737)

Any comments?

Jamikajamil

Can you add stack trace in the question? – Ferula

Answer 1

Having run this program, I think the problem is the following: since you are adding a transition from the node to itself, you end up with a HashMap that maps a character to itself. When you try adding in the second transition, it needs to add the object into a HashSet. The problem is that in order to do this, it needs to compute a hash code for your object. Since your object extends HashMap, it uses the HashMap code to compute the hash code for your object. To do this, it tries to recursively construct the hash code for all the objects in the HashMap, which includes itself. It thus recursively tries to compute its own hash code, which requires it to compute its own hash code, which requires it to compute its own hash code, etc.

I'm not sure what the best fix for this is, but I would start by not having this object extend HashMap. It is generally considered a bad idea to use inheritance when you mean to use composition. Making a HashMap a direct field of the object means that you'll break this cycle because Java will use the default implementation of hashCode, which doesn't try to compute a deep hash code for the object.

Hope this helps!

Typewritten

I was also debugging with the same result. Exact logic can be found in AbstractMap.hashCode function. – Joab

Thank you. The approach with composition (when HashMap is a field) works. I think I need to read your comment many times to understand what actually happens, but it seems interesting:) – Jamikajamil

But I would argue that in this particular case composition is more intuitive. State itself represents a part of transition table, which is a map. There are a lot of implementations based on inheritance:#1871019, #1871903) ... Anyway, thank you very much for your help. – Jamikajamil