Wie implementiert man hashCode() effizient für einen einfach verknüpften Listenknoten in Java?

Question

Eclipse implementiert das hashCode() Funktion für die Node-Klasse einer einfach verknüpften Liste wie folgt:

class Node{
    int val;
    Node next;

    public Node(int val){
        this.val = val;
        next = null;
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((next == null) ? 0 : next.hashCode());
        result = prime * result + val;
        return result;
    }
}

Jetzt hashCode() denn ein Knoten ist vom Hash-Code der ihm folgenden Knoten abhängig.

Also, jeder Anruf von hashCode() wird eine amortisierte lineare Zeit in der Länge der verknüpften Liste in Anspruch nehmen.Also mit a HashSet<Node> wird undurchführbar werden.

Eine Möglichkeit, dies zu umgehen, besteht darin, den Wert zwischenzuspeichern hashCode in einer Variablen (nennen wir es Hash), sodass es nur einmal berechnet wird.Aber auch in diesem Fall wird der Hash ungültig, sobald der Wert eines Knotens geändert wird.Und wieder wird es lineare Zeit dauern, das zu ändern hashCode der Knoten, die dem aktuellen Knoten folgen.

Was sind also einige gute Möglichkeiten, Hashing für einen solchen verknüpften Listenknoten zu implementieren?

Answer 1

Mein erster Gedanke beim Lesen Ihrer Frage war:was macht LinkedList Tun?Wenn wir uns mit der Quelle befassen, sehen wir, dass es keine gibt hashCode() oder equals() auf der Innenseite definiert LinkedList.Node Klasse (Link zur Quelle).

Warum ist das sinnvoll?Nun, Knoten sind normalerweise interne Datenstrukturen, die nur für die Liste selbst sichtbar sind.Sie werden nicht in Sammlungen oder anderen Datenstrukturen abgelegt, in denen Gleichheitsvergleiche und Hash-Codes erforderlich sind.Kein externer Code hat Zugriff darauf.

Sie sagen in Ihrer Frage:

Also mit a HashSet<Node> wird undurchführbar werden.

Aber ich würde argumentieren, dass Sie Ihre Knoten nicht in einer solchen Datenstruktur platzieren müssen.Per Definition sind Ihre Knoten miteinander verknüpft und erfordern keine zusätzlichen Klassen, um diese Beziehung zu ermöglichen.Und es sei denn, Sie planen, diese Klasse außerhalb Ihrer Liste verfügbar zu machen (was nicht notwendig ist), werden sie niemals in a landen HashSet.

Ich würde vorschlagen, dass Sie dem folgen LinkedList.Node Modell und vermeiden Sie die Erstellung dieser Methoden auf Ihren Knoten.Die äußere Liste kann ihren Hashcode und ihre Gleichheit auf den in den Knoten gespeicherten Werten (aber nicht auf den Knoten selbst) basieren, was auch so ist LinkedList tut es - sehen Sie AbstractList (Link zur Quelle).

_{Quelllinks verweisen auf die OpenJDK-Quelle, in diesem Fall sind sie jedoch identisch mit der mit Oracle JDKs bereitgestellten Quelle}

Answer 2

Sie müssen sich fragen, welche Qualität des Hashings für Sie wertvoll ist.Die einzige Einschränkung besteht darin, sicherzustellen, dass eine andere Liste mit derselben Nummer in derselben Reihenfolge denselben Hash hat.Dies wird durch die Verwendung einer konstanten Zahl sowie durch die Verwendung der ersten und durch die Beschränkung auf fünf Zahlen erreicht.Wie viele Zahlen für Sie sinnvoll sind, hängt von der Struktur Ihrer Daten ab.Wenn Sie beispielsweise immer aufeinanderfolgende, aufsteigende Zahlen beginnend bei 1 speichern und der Unterschied nur in der Länge besteht, ist die Optimierung schwierig.Wenn es über den gesamten Bereich von int völlig zufällig ist, reicht die erste Zahl aus.Wie viele Zahlen für Sie das beste Verhältnis liefern, lässt sich, würde ich sagen, durch Messen herausfinden.

Letztendlich benötigen Sie ein gutes Verhältnis zwischen Kollisionen (Objekte, die in denselben Eimer gelegt werden) und Berechnungszeit.Generierte Implementierungen versuchen in der Regel, die Berechnungszeit zu maximieren, sodass der menschliche Entwickler viel Raum für Verbesserungen hat.;-)

Und bezüglich der Änderung des enthaltenen Werts:java.util.HashSet (bzw. die HashMap, die es enthält) berechnet seinen eigenen Hash auf Ihrem und speichert diesen zwischen.Wenn also ein in einem HashSet enthaltenes Objekt nicht mehr gefunden werden kann, nachdem es sich so weit geändert hat, dass sich sein Hash geändert hat.