Arrays der Hash-Tabelle, die zwei Arten von Referenzen speichert

Question

Meine Frage bezieht sich auf das Bucket-Array der Hash-Tabelle (z. B. A genannt). Da es manchmal zu Kollisionen in einer Hash-Map kommt, ist es üblich, die einfache Verkettungslösung zu verwenden. Das bedeutet, dass jeder Bucket auf eine verknüpfte Liste zeigt, die Einträge enthält, und wenn es zu einer Kollision kommt, fügen Sie einfach den neuen Eintrag mit demselben Schlüssel in die Liste ein.

Aber nach der Datenstruktur Buch, wenn ein Eimer A[i] leer ist, speichert er null, und wenn A[i] speichert nur ein einziger Eintrag (Schlüssel, Wert), können wir einfach A[i] Punkt direkt mit dem Eintrag (Schlüssel, Wert) anstatt zu einer listenbasierten Karte, die nur den einen Eintrag enthält. Daher denke ich, dass die Hash-Tabelle zwei verschiedene Arten von Objekten (Eingabeobjekte und Listenobjekte) enthalten wird.

Ich hatte Probleme bei der Implementierung dieser Methode.Ich wähle eine neue abstrakte Klasse (genannt "Super" zum Beispiel), die sowohl von List-Klasse und Entry-Klasse geerbt wird. Und es gibt nichts in dieser neuen Klasse. Als Ergebnis enthält die Hash-Tabelle nun nur noch einen Typ Objekt "super", der auf beide Arten von Objekten zeigen kann, die ich brauche. Allerdings muss ich "instanceof" verwenden, um zu wissen, was genau der Bucket A[i] zeigt, um Operationen wie das Hinzufügen eines neuen Eintrags auszuführen. Ich habe gehört, dass die Verwendung von instanceof zu viel nicht angemessen ist. Und es wird viele Orte geben, die eine "Besetzung" erfordern. Also sollte ich den Code in der Klasse Entry und List in die "super" -Klasse kopieren, um nicht so viele "cast" s zu verwenden?

Answer 1

Es ist nichts falsch daran, einen einzelnen Eintrag als verkettete Liste mit nur einem Link zu speichern. Schließlich ist der Unterschied zwischen einem Eintrag (der nur den Schlüssel und den Wert enthält) und einem Link einer verknüpften Liste, die einen Eintrag enthält (der Schlüssel, der Wert und ein Verweis auf den nächsten Link enthält), ein einzelner Verweis auf Der nächste Link. Das macht die JDK-Implementierung von HashMap für Buckets mit einer kleinen Anzahl von Einträgen.

Auf diese Weise müssen Sie sich keine Gedanken über das Speichern verschiedener Objekttypen in Ihrer Tabelle machen.

Auf der anderen Seite, die Umsetzung von HashMap in Java 8 verwendet zwei Eintritt Implementierungen die Einträge eines Eimer zu speichern, - eine Node (verkettete Liste) und einen TreeNode (einen Knoten eines Baums). Wenn Sie sich die Implementierung ansehen, sehen Sie, dass sie e instanceof TreeNode verwenden, um den spezifischen Typ eines bestimmten Knotens zu überprüfen. So wie Sie sehen können, sogar das JDK use "instanceof" to know what exactly the bucket A[i] is pointing to.