Ich habe zwei Nummern und möchte sie zusammen als Schlüssel in einem Map verwenden. Momentan verkette ich ihre String-Repräsentationen. Angenommen, die Schlüsselnummern sind 4 und 12. Ich verwende:
Die Karte wird als Map<String, Object> deklariert.
Ich denke, das ist so schlimm! Ich benutze etwas anderes als String als Schlüssel! Ich möchte den schnellsten Weg, um diese Schlüssel zu erstellen.
Wer hat eine gute Idee?
Erstellen Sie ein Objekt, das die zwei Zahlen enthält, und verwenden Sie es als Schlüssel. Zum Beispiel:
%Vor%Wenn Sie einen mathematischen Ansatz bevorzugen, lesen Sie diese StackOverflow-Antwort .
Sie sollten java.awt.Dimension als Schlüssel verwenden.
Dimension key = neue Dimension (4, 12);
Dimension hat eine sehr schöne hashCode () -Methode, die für jedes Paar positiver Ganzzahlen einen anderen Hash-Code erzeugt, so dass die Hash-Codes für (4, 12) und (12, 4) unterschiedlich sind. So sind diese schnell zu instanziieren und sehr gute hashCodes zu machen.
Ich wünschte, sie hätten die Klasse unveränderlich gemacht, aber Sie können Ihre eigene unveränderliche Klasse nach Dimension modellieren.
Hier ist eine Tabelle, die den Hash-Code für verschiedene Werte von Breite und Höhe zeigt:
%Vor%Wenn Sie den Hash-Codes in der Reihenfolge von 0 bis 14 folgen, sehen Sie das Muster.
Hier ist der Code, der diesen hashCode erzeugt:
%Vor%Sie können die Formel für die Dreieckszahl innerhalb der letzten Zeile erkennen. Deshalb enthält die erste Spalte der Tabelle alle dreieckigen Zahlen.
Für Geschwindigkeit sollten Sie den Hash-Code im Konstruktor berechnen. So könnte Ihre ganze Klasse so aussehen:
%Vor%Natürlich, wenn Sie wahrscheinlich eine equals-Methode benötigen, aber Sie sich auf positive Ganzzahlen beschränken, die nicht überlaufen, können Sie eine sehr schnelle hinzufügen:
%Vor%Wir beschränken dies auf positive Werte, weil negative Werte einige duplizierte Hash-Codes erzeugen. Aber mit dieser Einschränkung sind dies die schnellsten Methoden hashCode () und equals (), die geschrieben werden können. (Natürlich können Sie hashCodes in jeder unveränderlichen Klasse genauso schnell schreiben, indem Sie den hashCode im Konstruktor berechnen.)
Wenn Sie mit diesen Einschränkungen nicht leben können, müssen Sie nur die Parameter speichern.
%Vor%Aber hier ist der Kicker. Du brauchst diese Klasse überhaupt nicht. Da die Formel für jedes Zahlenpaar eine eindeutige Ganzzahl enthält, können Sie diese Ganzzahl nur als Kartenschlüssel verwenden. Die Integer-Klasse hat ihre eigenen schnellen equals () - und hashCode-Methoden, die gut funktionieren. Diese Methode generiert den Hash-Schlüssel aus zwei kurzen Werten. Die Einschränkung besteht darin, dass Ihre Eingaben positive Kurzwerte sein müssen. Dies ist garantiert nicht überlaufen, und durch das Gießen der Zwischensumme zu einem langen, hat es einen größeren Bereich als die vorherige Methode: Es funktioniert mit allen positiven kurzen Werten.
%Vor%Wenn Sie mit der Objektlösung gehen, stellen Sie sicher, dass Ihr Schlüsselobjekt unveränderlich ist .
Andernfalls, wenn jemand den Wert verändert, wird er nicht nur nicht mehr mit anderen scheinbar identischen Werten übereinstimmen, aber der in der Map gespeicherte Hashcode stimmt nicht mehr mit dem von der Methode hashCode() zurückgegebenen überein. An diesem Punkt bist du im Grunde SOL.
Wenn Sie zum Beispiel java.awt.Point verwenden - was aussieht, auf Papier, genau wie Sie wollen - das Folgende:
druckt:
%Vor%Ein anderer Ansatz wäre die Verwendung von verschachtelten Maps:
%Vor%Hier haben Sie keinen Overhead um Schlüssel zu erstellen. Sie haben jedoch mehr Aufwand, um Einträge korrekt zu erstellen und abzurufen, und Sie müssen immer auf Karten zugreifen, um das gesuchte Objekt zu finden.
Warum sollte das Schreiben dieses zusätzlichen Codes, um eine vollständige Klasse zu erstellen, die Sie für nichts anderes benötigen, besser sein als die Verwendung eines einfachen Strings? Wird der Hash-Code für Instanzen dieser Klasse viel schneller berechnet als für den String? Ich denke nicht.
Sofern Sie nicht in einer Umgebung mit extrem eingeschränkter Rechenleistung arbeiten, sollte der Aufwand für das Erstellen und Hashen von Strings nicht merklich größer sein als der für die Instanziierung Ihrer benutzerdefinierten Klasse.
Ich denke, der schnellste Weg wäre, die Ints einfach in eine einzige Long zu packen, wie es der ZZ-Coder vorgeschlagen hat, aber in jedem Fall erwarte ich nicht, dass die Geschwindigkeitsgewinne beträchtlich sind.
Tags und Links java performance data-structures collections key