Hashtabellen

21. Juni 2002

F: Wenn ich ein Objekt als Schlüssel in einer Hashtabelle verwende, was in der Object-Klasse muss ich überschreiben und warum?

A: Wenn Sie ein eigenes Schlüsselobjekt zur Verwendung in a erstellen Hashtable, müssen Sie die Methoden Object.equals()und überschreiben Object.hashCode(), da Hashtableeine Kombination der Schlüssel hashCode()und equals()Methoden verwendet wird, um die Einträge schnell zu speichern und abzurufen. Es ist auch eine allgemeine Regel, dass Sie beim Überschreiben equals()immer überschreiben hashCode().

Mehr zum Warum

Eine etwas ausführlichere Erklärung hilft Ihnen dabei, Hashtableden Mechanismus zum Speichern und Abrufen zu verstehen . Ein Hashtableintern enthält Buckets, in denen die Schlüssel / Wert-Paare gespeichert sind. Der Hashtableverwendet den Hashcode des Schlüssels, um zu bestimmen, welchem ​​Bucket das Schlüssel / Wert-Paar zugeordnet werden soll.

Abbildung 1 zeigt a Hashtableund seine Eimer. Wenn Sie einen Schlüssel / Wert an übergeben Hashtable, wird der Hashcode des Schlüssels abgefragt. Der Hashtableverwendet diesen Code, um den Bucket zu bestimmen, in dem der Schlüssel / Wert platziert werden soll. Wenn beispielsweise der Hashcode gleich Null ist, wird der HashtableWert in Bucket 0 platziert. Wenn der Hashcode zwei ist, wird Hashtableder Wert ebenfalls in Bucket 2 platziert. (Dies ist ein vereinfachtes Beispiel; der Hashtablewird zuerst den Hashcode massieren, damit der Hashtableversucht nicht, den Wert außerhalb des Buckets einzufügen.)

Wenn Sie den Hashcode auf diese Weise verwenden, Hashtablekönnen Sie auch schnell feststellen, in welchen Bucket der Wert platziert wurde, wenn Sie versuchen, ihn abzurufen.

Hashcodes repräsentieren jedoch nur die Hälfte des Bildes. Der Hashcode gibt nur an, Hashtablein welchen Bucket der Schlüssel / Wert abgelegt werden soll. Manchmal können jedoch mehrere Objekte demselben Bucket zugeordnet werden, ein Ereignis, das als Kollision bezeichnet wird. In Java Hashtablereagiert der auf eine Kollision, indem er mehrere Werte in denselben Bucket legt (andere Implementierungen behandeln Kollisionen möglicherweise anders). Abbildung 2 zeigt Hashtable, wie ein nach einigen Kollisionen aussehen könnte.

Stellen Sie sich nun vor, Sie rufen get()mit einem Schlüssel auf, der Bucket 0 zugeordnet Hashtableist. Nun müssen Sie eine sequentielle Suche durch die Schlüssel / Wert-Paare in Bucket 0 durchführen, um den gewünschten Wert zu finden. Um diese Suche durchzuführen, Hashtableführt der die folgenden Schritte aus:

  1. Fragen Sie den Hashcode des Schlüssels ab
  2. Rufen Sie die Liste der Schlüssel / Werte ab, die sich in dem durch den Hashcode angegebenen Bucket befinden
  3. Scannen durch jeden Eintrag nacheinander , bis ein Schlüssel, der die Schlüssel übergeben gleich in get()gefunden wird

Eine lange Antwort auf eine kurze Frage, die ich kenne, aber es wird schlimmer. Richtig überschreiben equals()und hashCode()ist eine nicht triviale Übung. Sie müssen äußerst vorsichtig sein, um die Verträge beider Methoden zu garantieren.

Bei der Implementierung von equals ()

Laut equals()Javadoc muss die Methode den folgenden Regeln entsprechen:

"Die equals()Methode implementiert eine Äquivalenzbeziehung:
  • Es ist reflexiv: Für jeden Referenzwert x x.equals(x)sollte true zurückgegeben werden
  • Es ist symmetrisch: Für alle Referenzwerte x und y x.equals(y)sollte genau dann true zurückgegeben werden, wenn y.equals(x)true zurückgegeben wird
  • Es ist transitiv: Wenn für alle Referenzwerte x, y und z x.equals(y)true und y.equals(z)true zurückgegeben wird, x.equals(z)sollte true zurückgegeben werden
  • Es ist konsistent: Für alle Referenzwerte x und y geben mehrere Aufrufe von x.equals(y)konsistent true oder konsistent false zurück, sofern keine Informationen geändert werden, die für gleichwertige Vergleiche des Objekts verwendet werden
  • Sollte für jeden Nicht-Null-Referenzwert x x.equals(null)false zurückgeben "

In Effective Java bietet Joshua Bloch ein fünfstufiges Rezept zum Schreiben einer effektiven equals()Methode. Hier ist das Rezept in Codeform:

öffentliche Klasse EffectiveEquals {private int valueA; private int valueB; . . . public boolean equals (Object o) {if (this == o) {// Schritt 1: Führen Sie einen == Test durch. return true; } if (! (o Instanz von EffectiveEquals)) {// Schritt 2: Instanz der Prüfung return false; } EffectiveEquals ee = (EffectiveEquals) o; // Schritt 3: Cast-Argument // Schritt 4: Überprüfen Sie für jedes wichtige Feld, ob sie gleich sind. // Verwenden Sie für Grundelemente == // Verwenden Sie für Objekte equals (), achten Sie jedoch darauf, // auch den Null-Fall zu behandeln zuerst ee.valueA == valueA && ee.valueB == valueB zurückgeben; }. . . }}

Hinweis: Sie müssen keine Nullprüfung durchführen, da dies null instanceof EffectiveEqualsals falsch ausgewertet wird.

Kehren Sie schließlich für Schritt 5 zum equals()Vertrag zurück und fragen Sie sich, ob die equals()Methode reflexiv, symmetrisch und transitiv ist. Wenn nicht, beheben Sie es!

Bei der Implementierung von hashCode ()

Für hashCode()den Generalvertrag sagt der Javadoc:

  • "Immer wenn es während der Ausführung einer Java-Anwendung mehr als einmal für dasselbe Objekt aufgerufen wird, hashCode()muss die Methode konsistent dieselbe Ganzzahl zurückgeben, vorausgesetzt, dass keine Informationen geändert werden, die für gleiche Vergleiche für das Objekt verwendet werden. Diese Ganzzahl muss nicht von einer konsistent bleiben." Ausführung einer Anwendung zu einer anderen Ausführung derselben Anwendung.
  • Wenn zwei Objekte gemäß der equals(Object)Methode gleich sind, muss der Aufruf der hashCode()Methode für jedes der beiden Objekte das gleiche ganzzahlige Ergebnis liefern.
  • Es ist nicht erforderlich, dass, wenn zwei Objekte gemäß der equals(java.lang.ObjectMethode ungleich sind, der Aufruf der hashCode()Methode für jedes der beiden Objekte unterschiedliche ganzzahlige Ergebnisse liefern muss. Der Programmierer sollte sich jedoch bewusst sein, dass das Erzeugen eindeutiger ganzzahliger Ergebnisse für ungleiche Objekte die Leistung von Hashtabellen verbessern kann. "

Die Schaffung einer ordnungsgemäß funktionierenden hashCode()Methode erweist sich als schwierig. Noch schwieriger wird es, wenn das betreffende Objekt nicht unveränderlich ist. Sie können einen Hashcode für ein bestimmtes Objekt auf viele Arten berechnen. Die effektivste Methode basiert auf den Feldern des Objekts. Darüber hinaus können Sie diese Werte auf verschiedene Arten kombinieren. Hier sind zwei beliebte Ansätze:

  • Sie können die Felder des Objekts in eine Zeichenfolge umwandeln, die Zeichenfolgen verketten und den resultierenden Hashcode zurückgeben
  • Sie können den Hashcode jedes Felds hinzufügen und das Ergebnis zurückgeben

Während andere, gründlichere Ansätze existieren, erweisen sich die beiden oben genannten Ansätze als am einfachsten zu verstehen und umzusetzen.

Tony Sintes ist ein unabhängiger Berater und Gründer von First Class Consulting, einem Beratungsunternehmen, das sich auf die Überbrückung unterschiedlicher Unternehmenssysteme und Schulungen spezialisiert hat. Außerhalb von First Class Consulting ist Tony ein aktiver freiberuflicher Autor und Autor von Sams Teach Yourself Object-Oriented Programming in 21 Tagen (Sams, 2001; ISBN: 0672321092).

Erfahren Sie mehr über dieses Thema

  • Für den Hashtable Javadoc gehen Sie zu

    //java.sun.com/j2se/1.4/docs/api/java/util/Hashtable.html

  • Vipan Singlas "Implementieren von equals () und hashCode ()" bietet eine eingehende Diskussion zum Überschreiben der Methoden equals () und hashCode ()

    //www.vipan.com/htdocs/hashcode_help.html

  • The Object.equals() Javadoc

    //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#equals(java.lang.Object)

  • The Object.hashCode() Javadoc

    //java.sun.com/j2se/1.4/docs/api/java/lang/Object.html#hashCode()

  • For Joshua Bloch's Effective Java Programming Language Guide (Addison Wesley Professional, 2001; ISBN0201310058), go to

    //www.amazon.com/exec/obidos/ASIN/0201310058/javaworld

  • For more articles on Java classes and methods, browse the APIs section of JavaWorld's Topical Index

    //www.javaworld.com/channel_content/jw-apis-index.shtml

  • Want more? See the Java Q&A index page for the full Q&A catalog

    //www.javaworld.com/columns/jw-qna-index.shtml

  • Seit mehr als 100 interessanten Java - Tipps von einigen der besten Köpfe im Geschäft, Besuch Javaworld‘ s Java Tipps Indexseite

    //www.javaworld.com/columns/jw-tips-index.shtml

  • Lernen Sie Java Grundlagen in unserer Java Anfänger Diskussion

    //forums.idg.net/[email protected]@.ee6b804

  • Melden Sie sich für den kostenlosen wöchentlichen Core Java- E-Mail-Newsletter von JavaWorld an

    //www.javaworld.com/subscribe

  • Unter .net finden Sie eine Fülle von IT-Artikeln aus unseren Schwesterpublikationen

Diese Geschichte "Hashtables" wurde ursprünglich von JavaWorld veröffentlicht.