Wie hashCode () steht im Einklang mit equals () zu gewährleisten?
https://stackoverflow.com/questions/410236
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Wenn die Gleichheitsüberschreiben () Funktion von java.lang.Object, die javadocs legt nahe, dass
es ist in der Regel notwendig, die hashCode Methode außer Kraft zu setzen, wenn diese Methode außer Kraft gesetzt wird, um den allgemeinen Auftrag für die hashCode Methode zu halten, die besagen, dass gleiche Objekte gleich Hash-Codes haben.
Die hashCode () -Methode muss zurückgeben eindeutige ganze Zahl für jedes Objekt (das ist einfach zu tun, wenn Objekte basierend auf Speicherplatz zu vergleichen, bringen Sie einfach die einzigartigen integer Adresse des Objekts)
Wie sollte eine hashCode () -Methode so außer Kraft gesetzt wird, dass es eine eindeutige Ganzzahl gibt für jedes Objekt nur auf Basis dieses Objekts properities?
public class People{
public String name;
public int age;
public int hashCode(){
// How to get a unique integer based on name and age?
}
}
/*******************************/
public class App{
public static void main( String args[] ){
People mike = new People();
People melissa = new People();
mike.name = "mike";
mike.age = 23;
melissa.name = "melissa";
melissa.age = 24;
System.out.println( mike.hasCode() ); // output?
System.out.println( melissa.hashCode(); // output?
}
}
Lösung
Es heißt nicht die Hash-Code für ein Objekt völlig eindeutig sein muss, nur, dass der Hash-Code für zwei gleiche Objekte den gleichen Hash-Code zurückgibt. Es ist völlig legal zu haben zwei nicht gleich Objekte denselben Hash-Code zurück. Allerdings, je mehr einzigartige eine hashcode Verteilung ist über eine Reihe von Objekten, die ein bessere Leistung werden Sie aus HashMaps und anderen Operationen erhalten, die die hashCode verwenden.
IDEs wie IntelliJ Idea haben eingebaute Generatoren für equals und hashCode, die einen ziemlich guten Job bei kommen mit „gut genug“ Code für die meisten Objekte (und wahrscheinlich besser als einige handgearbeiteten übermäßig gescheit Hash-Funktionen im Allgemeinen tun ).
Zum Beispiel, hier ist eine hashCode Funktion, die Idee für Ihre Menschen Klasse erzeugt:
public int hashCode() {
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
Andere Tipps
Ich werde nicht auf die Details der hashCode Einzigartigkeit geht in wie Marc es bereits angesprochen hat. Für Ihre People Klasse, müssen Sie zunächst entscheiden, was die Gleichheit einer Person bedeutet. Vielleicht ist Gleichheit beruht allein auf ihren Namen, vielleicht ist es auf Name und Alter basiert. Es wird Domain-spezifisch sein. Sagen wir Gleichheit auf Namen und Alter basiert. Ihre überschriebene equals würde so aussehen
public boolean equals(Object obj) {
if (this==obj) return true;
if (obj==null) return false;
if (!(getClass().equals(obj.getClass())) return false;
Person other = (Person)obj;
return (name==null ? other.name==null : name.equals(other.name)) &&
age==other.age;
}
Jedes Mal, wenn Sie außer Kraft setzen equals Sie hashCode außer Kraft setzen müssen. Darüber hinaus hashCode können keine weiteren Felder in der Berechnung verwenden als equals tat. Die meiste Zeit müssen Sie oder Exklusiv-oder fügen Sie den Hash-Code der verschiedenen Felder (hashCode sollte zu berechnen sein schnell). So eine gültige hashCode Methode könnte wie folgt aussehen:
public int hashCode() {
return (name==null ? 17 : name.hashCode()) ^ age;
}
Beachten Sie, dass die folgende ist nicht gültig , da es ein Feld verwendet, dass equals nicht (Höhe). In diesem Fall sind zwei „gleich“ Objekte einen anderen Hash-Code haben könnte.
public int hashCode() {
return (name==null ? 17 : name.hashCode()) ^ age ^ height;
}
Außerdem ist es durchaus möglich, zwei nicht-gleich-Objekte den gleichen Hash-Code hat:
public int hashCode() {
return age;
}
In diesem Fall Jane Alter 30 ist nicht gleich Bob Alter 30, aber beide ihrer Hash-Codes sind 30. Während gültig dies für die Leistung in Hash-basierten Sammlungen unerwünscht ist.
Eine weitere Frage stellt, ob es einige grundlegende Low-Level sind die Dinge, die alle Programmierer wissen sollten, und ich denke, Hash-Lookups einer von denen. So, hier geht.
Eine Hash-Tabelle (beachten Sie, dass ich einen tatsächlichen Klassennamen nicht verwenden) ist im Grunde eine Reihe von verknüpften Listen. Um etwas in der Tabelle zu finden, berechnen Sie zuerst den Hash-Code des etwas, mod es dann durch die Größe der Tabelle. Dies ist ein Index in das Array, und Sie eine verknüpfte Liste an diesem Index erhalten. Sie dann die Liste durchlaufen, bis Sie Ihr Objekt zu finden.
Da das Feld Retrieval O (1) ist, und verknüpfte Liste Traversal ist O (n), mögen Sie eine Hash-Funktion, die als zufällig eine Verteilung wie möglich erzeugt, so dass Objekte in verschiedenen Listen gehasht werden. Jedes Objekt kann den Wert 0 als Hash-Code zurückgeben und eine Hash-Tabelle würde immer noch funktionieren, aber es wäre im wesentlichen eine lange verketteten Liste bei Element 0 des Arrays sein.
Sie in der Regel auch das Array wollen groß sein, was die Chancen erhöht, dass das Objekt in einer Liste der Länge 1. Die Java HashMap sein wird, zum Beispiel erhöht die Größe des Arrays, wenn die Anzahl der Einträge in der Karte ist> 75% der Größe des Arrays. Es ist ein Kompromiss hier: Sie haben eine riesige Auswahl mit sehr wenigen Einträgen und Abfall Speicher aufweisen kann, oder ein kleineres Array, in dem jedes Element im Array ist eine Liste mit> 1 Einträge, und Abfallzeit durchlaufen. Eine perfekte Hash würde jedes Objekt auf eine eindeutige Position in dem Array zugeordnet werden, ohne verschwendeten Raum.
Der Begriff „perfekte Hash“ ist ein echter Begriff, und in einigen Fällen können Sie eine Hash-Funktion erstellen, die für jedes Objekt eine eindeutige Nummer zur Verfügung stellt. Dies ist nur möglich, wenn man die Menge aller möglichen Werte kennen. Im allgemeinen Fall, können Sie dies nicht erreichen, und es werden einige Werte, die denselben Hash-Code zurück. Das ist einfache Mathematik. Wenn Sie eine Zeichenfolge, die mehr als 4 Bytes lang ist, können Sie nicht einen einzigartigen 4-Byte-Hash-Code erstellen
Ein interessanter Leckerbissen. Hash-Arrays sind so bemessen, basieren in der Regel auf Primzahlen, die beste Chance für die zufällige Zuteilung zu geben, wenn Sie die Ergebnisse mod, unabhängig davon, wie zufällig die Hashcodes wirklich sind
Bearbeiten basierend auf Kommentare:
1) Eine verkettete Liste ist nicht die einzige Möglichkeit, die Objekte zu repräsentieren, die denselben Hash-Code haben, obwohl dies ist das Verfahren, durch das JDK 1.5 HashMap verwendet. Obwohl weniger speichereffizienter als ein einfaches Array, es ist wohl schafft weniger Abwanderungs wenn Wiederkäuen (da die Einträge aus einem Eimer und neu gebunden zu einem anderen nicht verknüpft werden).
2) Ab JDK 1.4, die HashMap Klasse verwendet ein Array als eine Potenz von 2 bemessen; vor, dass sie verwendet 2 ^ N + 1, die ich für N ist eine Primzahl glauben <= 32. Dies bedeutet beschleunigen nicht Array-Indizierung per se, aber der Array-Index mit einem bitweise AND eher als eine Teilung berechnet werden lässt, wie von Neil Coffey zur Kenntnis genommen. Persönlich würde ich dies als verfrühte Optimierung in Frage, aber angesichts der Liste der Autoren auf HashMap, ich nehme an, dass eine wirkliche Nutzen ist.
In der Regel kann der Hash-Code nicht eindeutig sein, da es mehr Werte als möglicher Hash-Codes (Integer). Ein guter Hash-Code verteilt die Werte auch über die ganzen Zahlen. Ein schlecht kann man immer den gleichen Wert geben und noch logisch korrekt sein, wäre es nur zu einem unannehmbar ineffizient Hash-Tabellen führen.
Gleiche Werte müssen den gleichen Hash-Wert haben für Hash-Tabellen korrekt zu arbeiten. Andernfalls könnten Sie einen Schlüssel zu einer Hash-Tabelle hinzufügen, dann versuchen Sie es mit einem anderen Hash-Code über einen gleichen Wert zu suchen und ihn nicht finden. Oder Sie könnten einen gleichen Wert mit einem anderen Hash-Code setzen und haben zwei gleiche Werte an verschiedenen Orten in der Hash-Tabelle.
In der Praxis Sie in der Regel eine Teilmenge der Felder auswählen, um berücksichtigt werden sowohl in der hashCode () und dem Gleichheits () -Methode.
Ich glaube, du es falsch verstanden. Der Hash-Code muss nicht für jedes Objekt eindeutig sein (schließlich ist es ein Hash-Code), obwohl man natürlich es für alle Objekte identisch ist nicht will. Sie tun, aber müssen es alle Objekte identisch sein, die gleich sind, sonst Dinge wie die Standard-Sammlungen nicht funktionieren würde (zum Beispiel Sie etwas in der Hash-Set sehen würden, aber würde es nicht).
Für die einfache Attribute, einige IDEs haben hashcode Funktion Bauer.
Wenn Sie nicht IDEs verwenden, sollten Apahce Commons verwenden und die Klasse HashCodeBuilder
Die einzige vertragliche Verpflichtung für hashCode ist es konsistent zu sein. Die Felder in der Erstellung der HashCode Wert verwendet wird, muss die gleiche oder eine Teilmenge der Felder in dem Gleichheits Verfahren verwendet werden. Das bedeutet, 0 für alle Werte der Rückkehr gültig ist, wenn auch nicht effizient.
Man kann prüfen, ob hashCode konsistent über einen Unit-Test ist. Ich eine abstrakte Klasse geschrieben namens EqualityTestCase , die eine Handvoll hashCode Kontrollen der Fall ist. Man muss einfach den Testfall verlängern und zwei oder drei Fabrikmethoden implementieren. Der Test hat eine sehr grobe Arbeit der Prüfung, ob die hashCode effizient ist.
Dies ist, was Dokumentation sagt uns, wie für Hash-Code-Methode
@ javadoc
Jedes Mal, wenn es aufgerufen wird auf das gleiche Objekt mehr als einmal während eine Ausführung einer Java-Anwendung, die HashCode Methode muss konsistent die gleiche ganze Zahl zurück, sofern keine Informationen, die in gleich Vergleiche auf dem Objekt verändert wird. Diese integer muss nicht konsistent bleiben von einer Ausführung einer Anwendung auf eine andere Ausführung der gleichen Anwendung.
Es gibt eine Vorstellung von Business-Schlüssel, die Einzigartigkeit separater Instanzen des gleichen Typs bestimmt. Jede spezifische Art (Klasse), die Modelle eine separate Einheit von der Zieldomäne (z.B. Fahrzeug in einer Flotte System) soll ein Geschäft Schlüssel hat, die durch ein oder mehr Klassenfelder repräsentiert wird. Methoden equals () und hasCode () sollten beide implementiert werden, um die Felder verwenden, die einen Geschäftsschlüssel bilden. Dadurch wird sichergestellt, dass beide Methoden im Einklang miteinander.
