递归泛型定义和 Java 中的 Stackoverflow

Question

我正在为一些研究项目编写确定性有限自动机的实现，并且有一些弧导致相同的状态。 我为状态编写了这个类，但是 我想知道为什么代码会产生堆栈溢出：

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)

有什么意见吗？

Answer 1

运行这个程序后，我认为问题如下：由于您正在添加从节点到自身的过渡，因此最终会得到一个将字符映射到自身的HashMap。 当您尝试添加第二个过渡时，它需要将对象添加到HashSet中。 问题是，为了做到这一点，它需要计算对象的哈希代码。 由于您的对象扩展HashMap，它使用HashMap代码来计算对象的哈希代码。 为此，它尝试递归构造HashMap中所有对象的哈希代码，其中包括它自己。 因此，它递归地尝试计算自己的哈希代码，这需要它计算自己的哈希代码，这需要它计算自己的哈希代码等。

我不确定最好的解决方法是什么，但我首先不要让这个对象扩展HashMap.当您打算使用组合时，通常认为使用继承是一个坏主意。 将HashMap作为对象的直接字段意味着您将打破这个循环，因为 Java 将使用默认实现hashCode，它不会尝试计算对象的深度哈希代码。

希望这有帮助！