Datenstruktur zum Speichern von Paaren aus mehreren Schlüsseln und Werten in Java

Question

Guten Abend,

Ich bin auf der Suche nach einer eleganten Lösung für die Implementierung einer Übergangstabelle (speziell für einen universellen Pushdown-Automaten), die mehrere diskrete Werte für einen bestimmten Übergang verwendet. Man sagt, ein Bild sagt mehr als tausend Worte, also hier ist ein Teil meiner Tabelle:

State    InputSymbol    StackSymbol   Move(NewState, Action)
------------------------------------------------------------
  0           a              Z0           (0, push)
  0           a              a            (0, push)
  0           a              b            (0, pop)
  0           b              Z0           (1, push)
  ...

Nun, ich habe mehrdimensionale Arrays, ArrayLists von ArrayLists und andere Lösungen der Art betrachtet, aber alle scheinen ziemlich brutal. Erschwerend kommt hinzu, dass nicht jede mögliche Kombination meiner drei Symbole (a, b und Z0) in der Tabelle enthalten ist.

Ich habe in Erwägung gezogen, eine HashMap zu verwenden, aber ich bin nicht ganz sicher, wie man diese Arbeit mit mehreren Schlüsselwerten zu machen. Ich war unter Berücksichtigung der Verkettung alle drei Symbole zusammen und mit der resultierenden Zeichenfolge als mein Schlüssel, aber das, auch, scheint weniger als elegant.

Übrigens ist dies eine Hausaufgabe, aber eine elegante Lösung ist nicht unbedingt erforderlich. Ich habe einfach Spaß an gutem Code.

Ich danke Ihnen im Voraus für Ihre Unterstützung.

Answer 1

Erstellen Sie eine Klasse wie diese:

 class Key{
    int state;
    char inputSysmbol;
    String StackSymbol;
    }

Verwenden Sie dann die Karte Map<Key,Move> .

Erstellen Sie eine Klasse für Move, wie oben beschrieben, und vergessen Sie nicht Hashcode außer Kraft setzen und gleichsetzen Methode in beiden Klassen.

Answer 2

Verkapseln Sie {State, InputSymbol, StackSymbol} in einem Objekt. Verwenden Sie dann den "hashcode()" des Objekts als Schlüssel für Ihre Hashtabelle. Für weitere Informationen über Hashcodes siehe Doc .

Answer 3

Werfen Sie einen Blick auf MultiHashMap aus dem Jakarta Commons Collections Framework. http://commons.apache.org/collections/api-release/org/apache/commons/collections/MultiHashMap.html

Leider ist das Jakarta Collection Framework nicht parametrisiert, d.h. es unterstützt keine Generika, so dass Sie Ihren spezifischen Typ casten müssen.

Die andere Lösung ist, etwas Ähnliches selbst zu implementieren. Erstellen Sie die Klasse Move, die Ihre Daten enthält. Erstellen Sie die Klasse Table, die die Logik kapselt. Diese Klasse kann eine Liste (besser LinkedList) von Moves und N Maps enthalten: Map> stateIndex Map> inputSymbolIndex etc, etc.

Die Implementierung der Add-Methode ist trivial. Die Implementierung von get ist interessanter:

public Move get(Integer state, Character inputSymbol, StackSymbol stackSymbol) {
    List<Move> stateList = stateIndex.get(state);
    List<Move> inputSymbolList = stateIndex.get(inputSymbol);
    List<Move> stackSymbolList = stateIndex.get(stackSymbol);

    Set<Move> result = new HashSet<Move>(stateList);
    result.retainAll(inputSymbolList);
    result.retainAll(stackSymbolList);

    if (result.size() > 1) {
        throw new IllegalStateException("Unique constraint violation");
    } 
    return  result.size() == 0 ? null : result.interator().next();
}