hashCode()

[Foo Bar]

im neuen Heft im Kasten auf S. 28 steht zum Thema hashCode

"unveränderlich: Der Hash-Wert darf sich nicht ändern, sonst findet man das Objekt nicht wieder."

Deshalb sei der Anfangsbuchstabe schlecht, weil es vorkommen könne, dass eine Person z.B. durch Heirat ihren Nachnamen ändert.

Das ist doch irgendwie völlig verkehrt: wenn ich ein Objekt irgendwo mit Hilfe des HashWerts gespeichert habe (als Key in einer HashMap, in einem HashSet) dann darf sich <b>das Objekt</b> nicht ändern. Der hashCode muss/soll sich sogar mitändern, wenn das Objekt seine "Identität" ändert!

Es ist also genau andersrum.

Wenn ich eine Person p in einem HashSet ablege, und dann ändere ich den Nachnamen der Person (mit p.setNachname), dann wird die "alte Referenz" nicht wiedergefunden (d.h. contains liefert false); weil sich bei korrekter Implementierung der HashWert in 99,9% aller Fälle auch ändert.

Selbst wenn der hashCode sich nicht ändern würde - das könnte ja zufällig sein -würde es immer noch am equals scheitern.

Genau so soll es sein...

[Stefan Gawlick]

Korrekt.

Wenn man equals überschreibt, sollte man auch hashCode überschreiben.

Bei einer Person wird der Nachname ja sinnvollerweise in der equals-Methode ausgewertet. Da sollte er wohl auch in der hashCode-Methode ausgewertet werden.

Anderenfalls hätte man unerfreuliche Effekte mit den Collection-Klassen und ähnlichem

[Dissy McLaine]

Bei Durchsicht des JavaMagazins frage ich mich immer mal wieder, ob denn wirklich über diese oder jene Trivialität auch im Jahre 10 nach Java immer noch Artikel geschrieben werden müssen. Der "Schweinchenartikel" fiel auch darunter, obwohl die Darstellung mal angenehm "untechnisch" und leichtverständlich war, sodass ich das ganz gelungen fand. Nachdem ich aber hier diese Forum-Beiträge lese, stelle ich fest, dass es *unbedingt* notwendig zu sein scheint, auch hinlänglich bekannte Sachverhalte immer wieder in Artikeln allen nahezubringen, die doch noch irgendwelchen Irrlehren anhängen. Also bitte nochmal genau den Artikel lesen..

[Foo Bar]

@Dissy

Hä, soll das heissen die Darstellung mit

"hashCode soll unveränderlich sein" in Verbindung mit dem "wenn eine Person den Nachnamen ändert" usw. sei richtig???

was für ein Quark

Wenn eine Person z.B. durch Heirat ihren Nachnamen ändert, dann ist das einfach nur ein SCH***Beispiel, weil sich rein philosophisch gesehen ja die "Identität" nicht ändert...

99 von 100 Programmierern würden wohl eher sagen, dass man den Nachnamen in den equals/hashCode aufnehmen muss und dass daher der hashCode seinen Wert ändern soll, wenn sich der Nachname ändert

ich frage mich wo da die "Irrlehre" ist, viel eher ist doch die Formulierung "der hashCode soll unveränderlich sein" völliger Quatsc

[Bjørn Stachmann]

Hallo Foo Bar,

in den letzten Tagen hatte ich (Bjørn Stachmann, einer der Autoren des Artikels)
leider keine Zeit, ins Leserform zu schauen. Jetzt bin ich ganz erstaunt,
ob der Heftigkeit der entbrannten Diskussion über das Thema.

Ich denke, ich kann ein wenig Hintergrundwissen beisteueren, und hoffe
damit die Diskussion wieder etwas versachlichen zu können.

Im Artikel raten wir (also die Autoren) dringend davon ab, Hash-Werte
von Objekten zu änderen:

"unveränderlich: Der Hash-Wert darf sich nicht ändern, ...", Kasten, S. 28

Hierfür gibt es auch einen Grund, und der liegt in der Funktionsweise der
Klassen HashSet und HashMap begründet. Diese Klassen legen die Informationen
in sogenannten "Buckets" ab. In welchem Bucket ein Objekt abgelegt wird,
bestimmt der HashCode. Wenn sich der HashCode ändert liegt das Objekt im
"falschen" Bucket, denn die HashMap erfährt ja nicht, dass sich etwas
geändert hat.

Da nun die gesamte Interne Organisation der Klasse HashSet und HashMap erwarten,
dass Objekte in den Buckets liegen, die ihrem Hash-Code entsprechen,
kann es zu sehr interessantem "Verhalten" dieser Klassen kommen:
Duplikate, die es nicht geben sollte, oder falsche gezählte
Mengengrößen etc.

Ein kleines Codebeispiel, welches diese Art von Problemem demonstriert,
finden Sie als Anhang.

Diese Art von "Verhalten" zu debuggen kann sehr unangenehm sein,
da es oftmals nicht nachvollziehbar ist, wann und durch welche Hashwert-Änderung
der inkonsistenten Zustand verursacht wurde.

In der Theorie wäre es möglich, das Ändern von Hash-Codes zu erlauben,
solange ein Objekt weder in einem HashSet noch in einer HashMap steckt.
Die Frage ist nur: Wie will man das in einer komplexen Anwendung
(z. B. in einem Application Server) garantieren?

Letztlich bleibt es also dabei:

Nur wenn man garantieren kann,
dass sich der Hash-Code nicht ändert,
ist man auf der sicheren Seite!

Ein Tipp, falls Sie selber einmal versuchen möchten, eine HashCode-Methode
zu implementieren:

Deklarieren sie alle Attribute, die in die Hash-Code-Berechnung eingehen als final!

In der Hoffnung für etwas mehr Klarheit gesorgt zu haben, verbleibe ich

mit freundlichen Grüßen

Bjørn Stachmann

PS:

Falls Sie noch mehr über das Thema wissen möchten:

1. "Java Effektiv" (J. Bloch), Thema 8: "Überschreiben sie hashCode immer,
wenn Sie equals überschreiben" unt Thema 13: "Bevorzugen Sie Unveränderbarkeit"

Joshua Bloch gibt hervorragende Praxistipps für das Arbeiten mit Java.

2. Werfen Sie mal einen Blick in den Quelltext der Klasse HashMap (zum Teil
auch von J. Bloch). Es ist gar nicht soo schwer zu verstehen, wenn man
bereits ein wenig Java programmieren kann.

3. Für die Grundlagen (wie Behälterklassen funktionieren) empfehle ich gerne die
hervorragenden Standardwerke von Wirth und Knuth:

"Algorithmen und Datenstrukturen", N. Wirth

"The Art of Computer Programming", Donald Knut

[Bjørn Stachmann]

Ein Codebeispie

[Bjørn Stachmann]

/**
* Ein kleines Beispiel für Probleme beim Ändern von
* Hash-Werten.
*/

import java.util.HashSet;

/**
* Ein Zaubertrick in Java.
*/
public class DemoHashCodeDerSichAendert {

public static void main(String[] args) {
HashSet<Spielkarte> karten = new HashSet<Spielkarte>();

Spielkarte karte1 = new Spielkarte("Herz", "Dame");
Spielkarte karte2 = new Spielkarte("Pik", "Dame");
karten.add(karte1);
karten.add(karte2);

System.out.println("Karten vorher : " + karten);
// Es erfolgt die Ausgabe:
// Karten vorher: [Pik-Dame, Herz-Dame]

karte2.setWert("Sieben"); // Pik-Dame wird zu Pik-Sieben
karten.add(karte2); // und jetzt als Pik-Sieben hinzugefügt


System.out.println("Karten nachher : " + karten);
// Es erfolgt die Ausgabe:
// Karten nachher: [Pik-Sieben, Pik-Sieben, Herz-Dame]

// Pik-Sieben hat sich magisch verdoppelt!
// Der Magier Copperfield wäre stolz darauf.

// Jetzt erstellen wir eine Kopie.
System.out.println("karten (original) : "+karten);
Object clone = karten.clone();
System.out.println("clone : "+clone);
System.out.println("clone.equals(original) : "+clone.equals(karten));
// Es erfolgt die Ausgabe:
// karten (original) : [Pik-Sieben, Pik-Sieben, Herz-Dame]
// clone : [Pik-Sieben, Herz-Dame]
// clone.equals(original) : false

// Das Original hat 3 Elemente, die Kopie 2. Applaus!
// Die Kopie ist nicht equals zu ihrem eigenen Klon. Applaus!


// Beide Objekte entfernen!
karten.remove(karte1);
karten.remove(karte2);

System.out.println("Karten nach dem löschen : " + karten);
// Es erfolgt die Ausgabe:
// Karten nach dem löschen: [Pik-Sieben]

// Die Pik-Sieben auch nach dem Löschen noch drin!
// Congratulations Mr. Copperfield!
}

/**
* Diese Klasse berechnet ihren Hash-Wert aus den Attributen farbe und wert.
* Diese Attribute können nachträglich durch Set-Methoden geändert werden.
* Das ist gefährlich!
*/
public static class Spielkarte {


private String farbe;

private String wert;

public Spielkarte(String farbe, String wert) {
this.farbe = farbe;
this.wert = wert;
}

public String getFarbe() {
return farbe;
}

public void setFarbe(String farbe) {
this.farbe = farbe;
}

public String getWert() {
return wert;
}

public void setWert(String wert) {
this.wert = wert;
}

@Override
public boolean equals(Object obj) {
if (obj == this)
return true;

if (!(obj instanceof Spielkarte))
return false;

Spielkarte other = (Spielkarte) obj;
return this.farbe.equals(other.farbe)
&& this.wert.equals(other.wert);
}

@Override
public int hashCode() {
// hashCode Berechung nach Joshua Bloch
int result = 17;
result = 37 * result + farbe.hashCode();
result = 37 * result + wert.hashCode();
return result;
}

public String toString() {
return "" + farbe + "-" + wert;
}
}

[Foo Bar]

Lieber Herr Stachmann,
<p>
ihr Tipp "Objekte mit hashCode/equals immer immuteable machen" ist in meinen Augen ziemlich praxisfern.
<p>
immer locker bleiben, eine heftige Diskussion ist was ganz was anderes. Ihr Artikel - und auch ihr obiger Post - zeugt von einer gewissen Begriffsverwirrung
</p>
<p>
a) immutable Objekte

b) Objekte mit equals und hashCode ("Wertobjekt")
</p>
<p>
Weil Immutables ohnehin ihren Zustand nicht ändern können, kann für diese Objekte natürlich ohne Problem equals/hashCode implementiert werden (das ist trivial)
</p>
<p>
Ob ein Objekt mit equals/hashCode auch immutable ist, ist eine Frage des Designs / der Implementierung / des Speichers / der Semantik oder was auch immer. Auf jeden Fall ist das nicht immer so.
</p>
<p>
Nun zu Ihrem Beispiel - ich kann nur nochmal sagen
<b>
Sobald ein "Wertobjekt" in einer HashMap als Key, in einem HashSet usw. abgelegt wurde, darf sich die <i>Objektidentität</i> nicht mehr ändern.
</b>
</p>
<p>
Der Grund ist ganz einfach: wenn sich diese Objektidentität ändert, wird es nicht "wiedergefunden" <br>
Ob sich der hashCode bei einer Identitätsänderung mitändert, ist (wegen der in vielen Fällen fehlenden Eindeutigkeit) sowieso Zufall. Wenn er sich ändert, findet man das Bucket nicht wieder, wenn er sich nicht ändert findet man zwar das Bucket, aber wegen des equals findet man das Objekt in diesem Bucket trotzdem nicht.
</p>
"Wenn man garantieren kann dass sich der HashCode nicht ändert" ist als Formulierung irgendwie Quatsch - klar kann man das mit Immutables erreichen (aber das ist nicht immer möglich, man denke nur an die neuen EJB3 POJOs)
<br><br>
Im übrigen habe ich mich nur auf die missverständliche Formulierung bezogen: nicht der hashCode soll unveränderlich sein, sondern das Objekt soll sich nicht ändern solange es irgendwo in einem HashContainer ist. Wenn sich die "Idendität" ändert, dann soll/darf sich hingegen auch der hashCode mitändern.
<br><br>
Und zu Ihrem Appserver Argument: den hashCode (oder gleich ein HashSet oder ..) irgendwo zu persistieren ist eine ganz üble Idee (kann ja ohnehin jedesmal neu berechnet werden...).
<br><br>
Zum Schluss noch etwas Kosmetik: Im Uhrenbeispiel im Heft frage ich mich, warum Stunde und Minute nicht final sind? Und bei Immutables sollte man den hashCode im voraus berechnen - kleiner Performancetrick. Und nun zu Trick 37:
<pre>
stunde + minute*37
</pre>
ist albern: Im Heft nicht erklärt, also gibts zwei Arten von Lesern: die die Bloch schon gelesen haben (für die ist eh alles klar) und die die das für völlig aus der Luft gegriffen halten. Das hätte man zumindest erklären müssen. Ausserdem wäre in dem Fall
<pre>
stunde * 60 + minute
</pre>
wesentlich besser verständlich gewesen: Es fehlte nämlich auch der Hinweis dass man einen hashCode EINDEUTIG machen soll wenn das irgenwie möglich ist

[Foo Bar]

Ach ja, kleiner Nachtrag

hashCode ist ein reiner Performance-Twister, der keinerlei Auswirkung auf die Korrektheit von Programmen hat

<pre>
public int hashCode(){ return 1; }
</pre>

führt zu völlig korrekten Programmen, nur die Laufzeit bei gewissen Operationen geht eben von O(1) auf O(n)
<br>
damit ist man erst recht auf der sicheren Seite :-

[Stefan Gawlick]

Zum Beispiel mit der Person und dem sich ändernden Nachnamen:
"Überschreiben Sie hashCode immer, wenn Sie equals überschreiben" (siehe "Effective Java" von J.Bloch). Möglichst sollte man in beiden Methoden die selben Attribute auswerten.
Dann wäre es in diesem Fall gut, gar nicht erst den Namen zur "Identifikation" einer Person zu verwenden (Namensgleichheit gibt es sowieso recht oft). Man sollte in diesem Fall eine Personalnummer oder Ausweisnummer oder ähnlich eindeutiges verwenden. Dann würde man diese sowohl in equals als auch in hashCode verwenden. Und diese ändert sich schließlich auch nicht.

Aber ich bleibe dabei:
überschreibt man equals in einer Weise, bei der der Name verglichen wird, wäre es gut, wenn sich bei einer Namensänderung auch der hashCode ändert. Sonst hat man nämlich die von Foo Bar angesprochene Performance-Katastrophe.

Und daß Container/Listen/Sets/GUI-Klassen oder was auch immer interne Wertänderungen eines Objektes nicht automatisch mitbekommen, sollte jedem Entwickler klar sein. Wollte man dennoch darauf aufmerksam machen, sollte man es nicht verwirrenderweise mit dem hashCode-Thema vermischen. Das ist schließlich ein ganz allgmeines Problem: entweder ich gebe der mein Objekt referenzierenden Klasse ein neues Objekt mit den neuen Werten anstelle des alten Objektes oder ich ändere intern die Werte (Objektidentität!) und müßte dann der haltenden Klasse die Änderung mitteilen (was bei den Listen und Sets nicht geht).

Also beim nächsten Mal bitte klarer herausstellen, worauf man eigentlich hinaus will. Als Thema "wie überschreibe ich hashCode (sinnvoll)" konnten hier nur solche Reaktionen kommen

[Foo Bar]

Na eben, in dem Artikel fehlen ein paar interessante Aspekte:
<br>
1. Wie überschreibt man equals/hashCode richtig wenn eine Vererbungshierarchie im Spiel ist (unmöglich!). Gibts ein paar gute Artikel von Angelica Langer dazu
<br>
2. Was macht überhaupt die Identität aus? Ein Objekt = Gesamtheit seiner Attribute -> welche sollen in equals ausgewertet werden (schwierige Designfrage)
<br>
3. Nettes Beispiel ist java.net.URL, gut zum experimentieren geeignet weil da in equals tatsächlich die DNS Auflösung eingeht...
<br>
4. Mit den üblich POJOs aus Datenbanken (Hibernate, EJB3): Klar dass der PK ausreicht, aber wenn Objekt A schon drin ist (also einen PK hat) und Objekt B noch nicht persisitiert wurde was dann? Wie überschreibt man equals in dem Fall? Was soll passieren
<br>
5. Wenn die Anzahl der verschiedenen (unter equals) Objekte <= 2^32 ist, dann sollte man versuchen Eindeutigkeit im hashCode hinzukriegen
<br>
6. Wie genau funktioniert der Trick 37 von Bloch -> auch ein interessantes Thema
<br>
usw. usf.

Leider hat der Artikel fast alle interessanten Aspekte weggelassen :-