Рекурсивные универсальные определения и Stackoverflow в Java

Я пишу реализацию детерминированных конечных автоматов для некоторого исследовательского проекта, и есть несколько дуг, которые приводят к одному и тому же состоянию. Я написал этот класс для 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)

Любые комментарии?


java generics stack-overflow dfa
person Evgenii.Balai    schedule 30.11.2012    source источник
comment
Можете ли вы добавить трассировку стека в вопрос?   -  person Reddy    schedule 30.11.2012

Ответы (1)


arrow_upward
11
arrow_downward

Запустив эту программу, я думаю, что проблема в следующем: поскольку вы добавляете переход от узла к себе, вы получаете HashMap, который отображает символ на себя. Когда вы пытаетесь добавить второй переход, он должен добавить объект в HashSet. Проблема в том, что для этого ему нужно вычислить хеш-код для вашего объекта. Поскольку ваш объект расширяет HashMap, он использует код HashMap для вычисления хэш-кода для вашего объекта. Для этого он пытается рекурсивно построить хеш-код для всех объектов в HashMap, включая самого себя. Таким образом, он рекурсивно пытается вычислить свой собственный хеш-код, что требует от него вычисления собственного хеш-кода, что требует от него вычисления собственного хэш-кода и т. д.

Я не уверен, какое лучшее решение для этого, но я бы начал с того, что этот объект не расширял HashMap. Обычно считается плохой идеей использовать наследование, когда вы хотите использовать композицию. Создание HashMap прямым полем объекта означает, что вы прервете этот цикл, потому что Java будет использовать реализацию hashCode по умолчанию, которая не пытается вычислить глубокий хеш-код для объекта.

Надеюсь это поможет!

person templatetypedef    schedule 30.11.2012
comment
Я также отлаживал с тем же результатом. Точную логику можно найти в функции AbstractMap.hashCode. - person Robe Elckers; 30.11.2012
comment
Спасибо. Подход с композицией (когда HashMap — это поле) работает. Я думаю, мне нужно много раз прочитать ваш комментарий, чтобы понять, что на самом деле происходит, но это кажется интересным :) - person Evgenii.Balai; 30.11.2012
comment
Но я бы сказал, что в данном конкретном случае композиция более интуитивна. Само состояние представляет собой часть таблицы переходов, которая является картой. Существует множество реализаций, основанных на наследовании:stackoverflow.com/questions/1870519/, stackoverflow.com/questions/1871403/) ... В любом случае, большое спасибо за вашу помощь. - person Evgenii.Balai; 30.11.2012