7

我正在为一些研究项目编写确定性有限自动机的实现，并且有一些弧会导致相同的状态。我为 State 编写了这个类，但我想知道为什么代码会产生 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);
    }
}

令人惊讶的是，如果我删除“addTransition”调用之一，则没有错误。

我的 Java 版本是 JDK 1.6.37，操作系统是 Ubuntu Linux 12.04。

* UPD： *堆栈跟踪是：

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)

任何意见？

4

1 回答 1

11

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!

于 2012-11-30T06:44:38.520 回答