Hashcode - Operator ^

[Strim]

Hallo,

ich habe gerade gesehen dass eine Hashcode-Methode wie folgt überschrieben wurde:

@Override
public int hashCode ( ) {
return xPosition ^ 31 *  yPosition;
}

Ich verstehe den Sinn nicht, was soll mit ^ erreicht werden und wieso 31?

Mfg,
Tim

 

[Tobse]

^

ist der XOR-Operator (siehe Kontravalenz ? Wikipedia)
31 in binär ist

11111

. Was das genau mit dem hash-code auf sich hat, kann ich dir leider nicht sagen :/

 

[Strim]

Hm... noch ne Frage:
Eigentlich ist doch das Überschreiben der Methode hashCode() nur für Klassen wichtig die man als Key verwenden will, nicht aber für Klassen die man als Value in einer Hash-Tabelle verwenden will oder? Hab ich das richtig verstanden?

 

[Tobse]

Korrekt. Die Java Collection-Klassen prüfen über

hashCode()

auf identität. Wenn du aber die Equals-Methode überschreibst, musst du auch die hashCode-Methode überschreiben, sonst kannst du auf Situationen stoßen, die dich Stunden an Arbeit kosten nur um herauszufinden, dass das Problem in einer nicht oder falsch implementierten hashCode-Methode lag.

 

[Strim]

Die Java Collection-Klassen prüfen über hashCode() auf identität.

Nur die hashbasierten Container wie zB HashMap tun das oder? Wenn ich zB nur ArrayList verwenden will muss ich ja hashCode() nicht überschreiben oder doch?


Ich hab hier zu meiner ersten Frage nochmal die Ganze Aufgabe:
Sie wollen Objekte der folgenden Klasse als Schlüssel in der Hash-Tabelle ablegen. Die
Klasse beschreibt einen Punkt in einem Koordinatensystem. Ergänzen Sie dazu eventuell
erforderliche Methoden.

public class Point2D {
private int xPosition;
private int yPosition;
}

public class Point2D {
private int xPosition;
private int yPosition;
@Override
public boolean equals(Object other) {
if (other != null && other.getClass ( ) == getClass ( ) ) {
Point2D otherPoint = (Point2D) other;
return otherPoint.xPosition == xPosition
&& otherPoint.yPosition == yPosition;
}
return false;
}
@Override
public int hashCode ( ) {
return xPosition ^ 31  yPosition;
}
}

Um die hashCode() Methode zu überschreiben hätte ich doch zB auch die Berechnung:
xPosition + yPosition * 3 nehmen können oder? Das liegt ja bei mir oder?

MfG

 

[Tobse]

Nur die hashbasierten Container wie zB HashMap tun das oder? Wenn ich zB nur ArrayList verwenden will muss ich ja hashCode() nicht überschreiben oder doch?


Ich hab hier zu meiner ersten Frage nochmal die Ganze Aufgabe:
Sie wollen Objekte der folgenden Klasse als Schlüssel in der Hash-Tabelle ablegen. Die
Klasse beschreibt einen Punkt in einem Koordinatensystem. Ergänzen Sie dazu eventuell
erforderliche Methoden.

public class Point2D {
private int xPosition;
private int yPosition;
}

public class Point2D {
private int xPosition;
private int yPosition;
@Override
public boolean equals(Object other) {
if (other != null && other.getClass ( ) == getClass ( ) ) {
Point2D otherPoint = (Point2D) other;
return otherPoint.xPosition == xPosition
&& otherPoint.yPosition == yPosition;
}
return false;
}
@Override
public int hashCode ( ) {
return xPosition ^ 31  yPosition;
}
}

Um die hashCode() Methode zu überschreiben hätte ich doch zB auch die Berechnung:
xPosition + yPosition * 3 nehmen können oder? Das liegt ja bei mir oder?

MfG

Du musst die hashCode funktion nur überschreiben, wenn du die equals-methode auch überschreibst.
Die Methode muss ein Ergebnis liefern, dass eindeutig für die enthaltenen Werte ist, es darf keine zwei Zustände geben, die den gleichen hash-code zur Folge haben.

 

[Strim]

Aber wenn ich gar keine hash-basierten Container benutzen will aber trotzdem Objekte vergleichen, reicht es doch wenn ich die equals Methode ohne die hashCode Methode überschreib oder nicht?

Wäre xPosition + yPosition * 3 nicht gut als HashCode-Berechnung?
Wie mache ich dann eine gute Berechnung für einen HashCode bei zB solchen 2 int Attributen?
Ich kann mit xPosition ^ 31 *  yPosition nichts anfangen
Mfg

 

[Tobse]

Aber wenn ich gar keine hash-basierten Container benutzen will aber trotzdem Objekte vergleichen, reicht es doch wenn ich die equals Methode ohne die hashCode Methode überschreib oder nicht?

Doch. Erstens, weil es dem Standard entspricht und zweitens weil du böse darüber stolpern kannst, wenn du es nicht tust.

Wäre xPosition + yPosition * 3 nicht gut als HashCode-Berechnung?
Wie mache ich dann eine gute Berechnung für einen HashCode bei zB solchen 2 int Attributen?
Ich kann mit xPosition ^ 31 *  yPosition nichts anfangen
Mfg

welche IDE benutzt du? In NetBeans gibt es eine eingebaute Funktion dafür.

 

[Strim]

Ok danke.

welche IDE benutzt du? In NetBeans gibt es eine eingebaute Funktion dafür.

Eclipse

MfG

 

[nvidia]

Aber wenn ich gar keine hash-basierten Container benutzen will aber trotzdem Objekte vergleichen, reicht es doch wenn ich die equals Methode ohne die hashCode Methode überschreib oder nicht?

Wäre xPosition + yPosition * 3 nicht gut als HashCode-Berechnung?
Wie mache ich dann eine gute Berechnung für einen HashCode bei zB solchen 2 int Attributen?
Ich kann mit xPosition ^ 31 *  yPosition nichts anfangen
Mfg

Auch wenn man gar keinen Hash Code berechnen möchte oder kann (weil z.B. alle Fields veränderbar sind) sollte hashCode() überschrieben werden. Hauptsache hashCode() hält sich an ein paar Regeln und ist konsistent zu equals(). Ganz wichtig ist es das für den hash code nur Attribute verwendet werden die sich über die gesamte Lebenszeit des Objektes nicht ändern. Ist das nicht der Fall und man hat z.B. nur Attribute die alle änderbar sind wird hashCode dennoch überschrieben und meist eine Konstante wie 0 zurückgegeben damit die Konsistenz zu equals() gewährleistet ist.

Es ist wichtig die Gedanken hinter equals()/hashCode() zu verstehen. Eine gute Einführung in equals()/hashCode() findest du hier. Als Anfänger wirst du das wahrscheinlich mehrfach lesen müssen.

AngelikaLanger.com - Implementing the equals() Method - Part 1 - Angelika Langer Training/Consulting
AngelikaLanger.com - Implementing the equals() Method - Part 2 - Angelika Langer Training/Consulting

AngelikaLanger.com - Implementing the hashCode() Method - Angelika Langer Training/Consulting

Und allgemein, dieses Bit-Shifting und die Verwendung einer Primzahl macht man um eine gleichmäßigere Verteilung der Werte innerhalb der Hashtabelle zu erreichen.

 

[Strim]

Ok, ich verstehe.

Zu zweiterem:
Kann ich mir das also als Faustregel merken zum hashCode berechnen?
feld1 ^ primzahl * feld2 ??

Oder könnt ihr mir irgendeine Faustregel dafür geben zum Berechnen eines hashCodes aus Feldern die sich über die gesamte Lebenszeit eines Objektes nicht ändern?

In der Klausur hat der Prof das ja in den Lösungen mit "xPosition ^ 31 *  yPosition" gemacht... hätte man aber auch anders machen können oder?

MfG

 

[nvidia]

Ok, ich verstehe.

Zu zweiterem:
Kann ich mir das also als Faustregel merken zum hashCode berechnen?
feld1 ^ primzahl * feld2 ??

Oder könnt ihr mir irgendeine Faustregel dafür geben zum Berechnen eines hashCodes aus Feldern die sich über die gesamte Lebenszeit eines Objektes nicht ändern?

In der Klausur hat der Prof das ja in den Lösungen mit "xPosition ^ 31 *  yPosition" gemacht... hätte man aber auch anders machen können oder?

MfG

Klar kann man das auch anders machen, es gibt einen Haufen verschiedener Hashfunktionen und obendrein könntest du auch immer 0 zurückgeben, das ist genauso eine gültige Hashfunktion aber die Verteilung der Werte ist schlecht. Gute Hashfunktionen zu finden ist nicht so einfach, es hängt vom Datentyp ab, der Länge der Eingabe usw. Es gibt reichlich wissenschaftliche Artikel zu dem Thema.

Wenn euer Prof. das so haben möchte kannst du das so machen. Ob das die "beste" Hashfunktion für das Problem ist kann ich aber nicht sagen, das könnte man mit etwas Aufwand jedoch nachrrechnen oder einfach durch Experimentieren herausbekommen.

Na jedenfalls kannst du dir die Hashfunktion oft von der IDE generieren lassen, Eclipse generiert eine Funktion ähnlich der in Effective Java (ab S. 45 glaube ich) beschriebenen.
Bei der Java-Standardbibliothek ist das auch noch ein wenig anders, da wird der Wert von hashCode() noch einmal "gehasht" wenn man z.B. eine HashMap verwendet. Der Hintergedanke war wohl sich gegen schlechte Hashfunktionen etwas abzusichern.