Search code examples
javagenericsstack-overflowdfa

Recursive generic definitions and Stackoverflow in Java

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?

Solution

  • 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!