Beste Implementierung für die hashCode-Methode für eine Sammlung
299
Wie entscheiden wir uns für die beste Implementierung der hashCode()Methode für eine Sammlung (vorausgesetzt, die Methode equals wurde korrekt überschrieben)?
Die beste Implementierung? Das ist eine schwierige Frage, da sie vom Verwendungsmuster abhängt.
A für fast alle Fälle angemessen gute Umsetzung wurde vorgeschlagen Josh Bloch ‚s Effective Java in Punkt 8 (zweite Auflage). Das Beste ist, es dort nachzuschlagen, weil der Autor dort erklärt, warum der Ansatz gut ist.
Eine kurze Version
Erstellen Sie einen Wert int resultund weisen Sie einen Wert ungleich Null zu.
Berechnen Sie für jedesf in der equals()Methode getestete Feld einen Hash-Code cmit:
Wenn das Feld f a ist boolean: berechnen (f ? 0 : 1);
Wenn das Feld f a byteist char, shortoder int: berechnen (int)f;
Wenn das Feld f a ist long: berechnen (int)(f ^ (f >>> 32));
Wenn das Feld f a ist float: berechnen Float.floatToIntBits(f);
Wenn das Feld f a ist double: Berechnen Double.doubleToLongBits(f)und behandeln Sie den Rückgabewert wie jeden langen Wert;
Wenn das Feld f ein Objekt ist : Verwenden Sie das Ergebnis der hashCode()Methode oder 0 if f == null;
Wenn das Feld f ein Array ist : Sehen Sie jedes Feld als separates Element und berechnen Sie den Hash-Wert rekursiv und kombinieren Sie die Werte wie nachfolgend beschrieben.
Kombinieren Sie den Hashwert cmit result:
result =37* result + c
Rückkehr result
Dies sollte für die meisten Verwendungssituationen zu einer ordnungsgemäßen Verteilung der Hashwerte führen.
Ja, ich bin besonders neugierig, woher die Nummer 37 kommt.
Kip
17
Ich habe Punkt 8 von Josh Blochs "Effective Java" -Buch verwendet.
Meister
39
@dma_k Der Grund für die Verwendung von Primzahlen und die in dieser Antwort beschriebene Methode besteht darin, sicherzustellen, dass der berechnete Hashcode eindeutig ist . Wenn Sie Nicht-Primzahlen verwenden, können Sie dies nicht garantieren. Es spielt keine Rolle, welche Primzahl Sie wählen, die Zahl 37 hat nichts Magisches (schade, dass 42 keine Primzahl ist, oder?)
Simon Forsberg,
34
@ SimonAndréForsberg Nun, berechneter Hash-Code kann nicht immer eindeutig sein :) Ist ein Hashcode. Ich kam jedoch auf die Idee: Die Primzahl hat nur einen Multiplikator, während die Nicht-Primzahl mindestens zwei hat. Dadurch wird eine zusätzliche Kombination für den Multiplikationsoperator erstellt, die denselben Hash ergibt, dh eine Kollision verursacht.
Wenn Sie mit der von dmeister empfohlenen effektiven Java-Implementierung zufrieden sind, können Sie einen Bibliotheksaufruf verwenden, anstatt Ihren eigenen zu rollen:
Dies erfordert entweder Guava ( com.google.common.base.Objects.hashCode) oder die Standardbibliothek in Java 7 ( java.util.Objects.hash), funktioniert jedoch auf die gleiche Weise.
Wenn man keinen guten Grund hat, diese nicht zu verwenden, sollte man sie auf jeden Fall verwenden. (Stärker formulieren, da es meiner Meinung nach formuliert werden sollte.) Es gelten die typischen Argumente für die Verwendung von Standardimplementierungen / -bibliotheken (Best Practices, gut getestet, weniger fehleranfällig usw.).
Kissaki
7
@ justin.hughey Sie scheinen verwirrt zu sein. Der einzige Fall, den Sie überschreiben sollten, hashCodeist, wenn Sie eine benutzerdefinierte haben equals, und genau dafür sind diese Bibliotheksmethoden konzipiert. Die Dokumentation ist ziemlich klar über ihr Verhalten in Bezug auf equals. Eine Bibliotheksimplementierung erhebt keinen Anspruch darauf, Sie von den Merkmalen einer korrekten hashCodeImplementierung zu entbinden. Diese Bibliotheken erleichtern Ihnen die Implementierung einer solchen konformen Implementierung in den meisten Fällen, in denen sie equalsüberschrieben wird.
Bacar
6
Für alle Android-Entwickler, die sich die Klasse java.util.Objects ansehen, wurde sie nur in API 19 eingeführt. Stellen Sie daher sicher, dass Sie mit KitKat oder höher ausgeführt werden. Andernfalls erhalten Sie NoClassDefFoundError.
Andrew Kelly
3
Beste Antwort IMO, obwohl ich als Beispiel lieber die JDK7- java.util.Objects.hash(...)Methode als die Guavenmethode gewählt hätte com.google.common.base.Objects.hashCode(...). Ich denke, die meisten Leute würden die Standardbibliothek einer zusätzlichen Abhängigkeit vorziehen.
Malte Skoruppa
2
Wenn es zwei oder mehr Argumente gibt und eines davon ein Array ist, entspricht das Ergebnis möglicherweise nicht hashCode()Ihren Erwartungen, da es für ein Array nur das ist java.lang.System.identityHashCode(...).
Starikoff
59
Es ist besser, die von Eclipse bereitgestellten Funktionen zu verwenden, die ziemlich gute Arbeit leisten, und Sie können Ihre Anstrengungen und Energie in die Entwicklung der Geschäftslogik stecken.
+1 Eine gute praktische Lösung. Die Lösung von dmeister ist umfassender, aber ich vergesse oft, mit Nullen umzugehen, wenn ich versuche, selbst Hashcodes zu schreiben.
Quantum7
1
+1 Stimmen Sie Quantum7 zu, aber ich würde sagen, es ist auch sehr gut zu verstehen, was die von Eclipse generierte Implementierung tut und woher sie ihre Implementierungsdetails bezieht.
jwir3
15
Entschuldigung, aber Antworten mit "Funktionen, die von [einigen IDE] bereitgestellt werden" sind im Kontext der Programmiersprache im Allgemeinen nicht wirklich relevant. Es gibt Dutzende von IDEs, und dies beantwortet die Frage nicht ... nämlich weil es mehr um die algorithmische Bestimmung geht und direkt mit der Implementierung von equals () verbunden ist - etwas, von dem eine IDE nichts weiß.
@Overridepublicint hashCode(){// Start with a non-zero constant. Prime is preferredint result =17;// Include a hash for each field.// Primatives
result =31* result +(booleanField ?1:0);// 1 bit » 32-bit
result =31* result + byteField;// 8 bits » 32-bit
result =31* result + charField;// 16 bits » 32-bit
result =31* result + shortField;// 16 bits » 32-bit
result =31* result + intField;// 32 bits » 32-bit
result =31* result +(int)(longField ^(longField >>>32));// 64 bits » 32-bit
result =31* result +Float.floatToIntBits(floatField);// 32 bits » 32-bitlong doubleFieldBits =Double.doubleToLongBits(doubleField);// 64 bits (double) » 64-bit (long) » 32-bit (int)
result =31* result +(int)(doubleFieldBits ^(doubleFieldBits >>>32));// Objects
result =31* result +Arrays.hashCode(arrayField);// var bits » 32-bit
result =31* result + referenceField.hashCode();// var bits » 32-bit (non-nullable)
result =31* result +// var bits » 32-bit (nullable) (nullableReferenceField ==null?0: nullableReferenceField.hashCode());return result;}
BEARBEITEN
Wenn Sie überschreiben hashcode(...), möchten Sie normalerweise auch überschreiben equals(...). Für diejenigen, die bereits implementiert haben oder bereits implementiert haben equals, ist hier eine gute Referenz von meinem Github ...
@Overridepublicboolean equals(Object o){// Optimization (not required).if(this== o){returntrue;}// Return false if the other object has the wrong type, interface, or is null.if(!(o instanceofMyType)){returnfalse;}MyType lhs =(MyType) o;// lhs means "left hand side"// Primitive fieldsreturn booleanField == lhs.booleanField
&& byteField == lhs.byteField
&& charField == lhs.charField
&& shortField == lhs.shortField
&& intField == lhs.intField
&& longField == lhs.longField
&& floatField == lhs.floatField
&& doubleField == lhs.doubleField
// Arrays&&Arrays.equals(arrayField, lhs.arrayField)// Objects&& referenceField.equals(lhs.referenceField)&&(nullableReferenceField ==null? lhs.nullableReferenceField ==null: nullableReferenceField.equals(lhs.nullableReferenceField));}
Wenn equals () für zwei Objekte true zurückgibt, sollte hashCode () denselben Wert zurückgeben. Wenn equals () false zurückgibt, sollte hashCode () unterschiedliche Werte zurückgeben
Ich kann dir nicht zustimmen. Wenn zwei Objekte denselben Hashcode haben, muss dies nicht bedeuten, dass sie gleich sind.
Wenn A gleich B ist, muss A.hashcode gleich B.hascode sein
aber
Wenn A.hashcode gleich B.hascode ist, bedeutet dies nicht, dass A gleich B sein muss
Wenn (A != B) and (A.hashcode() == B.hashcode())ja, nennen wir das Hash-Funktionskollision. Dies liegt daran, dass die Codomäne der Hash-Funktion immer endlich ist, während dies bei der Domain normalerweise nicht der Fall ist. Je größer die Codomäne ist, desto seltener sollte die Kollision auftreten. Gute Hash-Funktionen sollten unterschiedliche Hashes für unterschiedliche Objekte zurückgeben, wobei die größte Wahrscheinlichkeit bei einer bestimmten Codomänengröße erreichbar ist. Es kann jedoch selten vollständig garantiert werden.
Krzysztof Jabłoński
Dies sollte nur ein Kommentar zu dem obigen Beitrag an Gray sein. Gute Informationen, aber es beantwortet die Frage nicht wirklich
Christopher Rucinski
Gute Kommentare, aber seien Sie vorsichtig bei der Verwendung des Begriffs "verschiedene Objekte" ... denn bei equals () und damit bei der Implementierung von hashCode () geht es nicht unbedingt um verschiedene Objekte in einem OO-Kontext, sondern in der Regel eher um deren Domänenmodelldarstellungen (z. B. zwei) Personen können als gleich angesehen werden, wenn sie einen Ländercode und eine Länder-ID gemeinsam haben - obwohl dies zwei verschiedene "Objekte" in einer JVM sein können -, werden sie als "gleich" angesehen und haben einen bestimmten Hashcode) ...
Darrell Teague
7
Wenn Sie Eclipse verwenden, können Sie Folgendes generieren equals()und hashCode()verwenden:
Quelle -> Generiere hashCode () und equals ().
Mit dieser Funktion können Sie entscheiden, welche Felder Sie für die Berechnung von Gleichheit und Hashcode verwenden möchten, und Eclipse generiert die entsprechenden Methoden.
Der Nachteil dieser API ist, dass Sie die Kosten für die Objektkonstruktion jedes Mal bezahlen, wenn Sie gleich und Hashcode aufrufen (es sei denn, Ihr Objekt ist unveränderlich und Sie berechnen den Hash vorab), was in bestimmten Fällen sehr viel sein kann.
James McMahon
Dies war bis vor kurzem mein Lieblingsansatz. Ich bin auf StackOverFlowError gestoßen, während ich ein Kriterium für die SharedKey OneToOne-Zuordnung verwendet habe. Mehr über, ObjectsKlasse bietet hash(Object ..args)und equals()Methoden von Java7 auf. Diese werden für alle Anwendungen empfohlen, die jdk 1.7+ verwenden
Diablo
@Diablo Ich denke, Ihr Problem war ein Zyklus im Objektdiagramm, und dann haben Sie bei den meisten Implementierungen kein Glück, da Sie einige Referenzen ignorieren oder den Zyklus unterbrechen müssen (Mandieren eines IdentityHashMap). FWIW Ich verwende einen ID-basierten Hashcode und ist für alle Entitäten gleich.
Maaartinus
6
Nur eine kurze Anmerkung zum Ausfüllen anderer detaillierterer Antworten (in Bezug auf den Code):
Wenn ich Ihre Frage richtig verstehe, haben Sie eine benutzerdefinierte Auflistungsklasse (dh eine neue Klasse, die sich über die Auflistungsschnittstelle erstreckt) und möchten die Methode hashCode () implementieren.
Wenn Ihre Auflistungsklasse AbstractList erweitert, müssen Sie sich keine Sorgen machen. Es gibt bereits eine Implementierung von equals () und hashCode (), bei der alle Objekte durchlaufen und ihre hashCodes () addiert werden.
Wenn Sie nun den Hash-Code für eine bestimmte Klasse am besten berechnen möchten, verwende ich normalerweise den Operator ^ (bitweise exklusiv oder), um alle Felder zu verarbeiten, die ich in der Methode equals verwende:
(Kann man hashCode heutzutage direkt von int in Java bekommen? Ich denke, es macht ein Autocasting. Wenn das der Fall ist, überspringe den toString, es ist hässlich.)
Der Fehler liegt in der langen Antwort von about8.blogspot.com. Wenn Sie den Hashcode aus einer Verkettung von Zeichenfolgen abrufen, erhalten Sie eine Hash-Funktion, die für jede Kombination von Zeichenfolgen, die sich zu derselben Zeichenfolge addieren, gleich ist.
SquareCog
1
Das ist also eine Metadiskussion und hat überhaupt nichts mit der Frage zu tun? ;-)
Huppie
1
Es ist eine Korrektur einer vorgeschlagenen Antwort, die einen ziemlich bedeutenden Fehler aufweist.
SquareCog
Dies ist eine sehr begrenzte Implementierung
Christopher Rucinski
Ihre Implementierung vermeidet das Problem und führt ein anderes ein. Tauschen foound barführt zum selben hashCode. Ihr toStringAFAIK wird nicht kompiliert, und wenn ja, ist es schrecklich ineffizient. So etwas 109 * getFoo().hashCode() + 57 * getBar().hashCode()ist schneller, einfacher und erzeugt keine unnötigen Kollisionen.
Maaartinus
2
Da Sie speziell nach Sammlungen gefragt haben, möchte ich einen Aspekt hinzufügen, den die anderen Antworten noch nicht erwähnt haben: Eine HashMap erwartet nicht, dass ihre Schlüssel ihren Hashcode ändern, sobald sie der Sammlung hinzugefügt werden. Würde den ganzen Zweck besiegen ...
Ich bevorzuge die Verwendung von Dienstprogrammmethoden aus der Google Collections-Bibliothek der Klasse Objects , mit denen ich meinen Code sauber halten kann. Sehr oft equalsund hashcodeMethoden werden aus der IDE-Vorlage erstellt, sodass sie nicht sauber zu lesen sind.
Hier ist eine weitere Demonstration des JDK 1.7+ -Ansatzes mit berücksichtigten Superklassenlogiken. Ich sehe es als ziemlich praktisch an, wenn die Objektklasse hashCode () berücksichtigt wird, reine JDK-Abhängigkeit und keine zusätzliche manuelle Arbeit. bitte beachten SieObjects.hash() tolerant ist.
Ich habe keine equals()Implementierung aufgenommen, aber in Wirklichkeit werden Sie sie natürlich brauchen.
import java.util.Objects;publicclassDemo{publicstaticclass A {privatefinalString param1;public A(finalString param1){this.param1 = param1;}@Overridepublicint hashCode(){returnObjects.hash(super.hashCode(),this.param1);}}publicstaticclass B extends A {privatefinalString param2;privatefinalString param3;public B(finalString param1,finalString param2,finalString param3){super(param1);this.param2 = param2;this.param3 = param3;}@Overridepublicfinalint hashCode(){returnObjects.hash(super.hashCode(),this.param2,this.param3);}}publicstaticvoid main(String[] args){
A a =new A("A");
B b =new B("A","B","C");System.out.println("A: "+ a.hashCode());System.out.println("B: "+ b.hashCode());}}
haben das gleiche hashCode, nämlich 31*(a+b) + cals Multiplikator fürList.hashCode verwendete hier wiederverwendet wird. Kollisionen sind natürlich unvermeidlich, aber unnötige Kollisionen zu erzeugen ist einfach ... unnötig.
Es ist nichts wesentlich Kluges an der Verwendung 31. Der Multiplikator muss ungerade sein, um Informationsverluste zu vermeiden (jeder gerade Multiplikator verliert mindestens das höchstwertige Bit, Vielfache von vier verlieren zwei usw.). Jeder ungerade Multiplikator ist verwendbar. Kleine Multiplikatoren können zu einer schnelleren Berechnung führen (die JIT kann Verschiebungen und Additionen verwenden), aber da die Multiplikation bei modernen Intel / AMD nur eine Latenz von drei Zyklen aufweist, spielt dies kaum eine Rolle. Kleine Multiplikatoren führen auch zu mehr Kollisionen bei kleinen Eingaben, was manchmal ein Problem sein kann.
Die Verwendung einer Primzahl ist sinnlos, da Primzahlen im Ring Z / (2 ** 32) keine Bedeutung haben.
Daher würde ich empfehlen, eine zufällig ausgewählte große ungerade Zahl zu verwenden (zögern Sie nicht, eine Primzahl zu nehmen). Da i86 / amd64-CPUs einen kürzeren Befehl für Operanden verwenden können, die in ein einzelnes vorzeichenbehaftetes Byte passen, gibt es für Multiplikatoren wie 109 einen winzigen Geschwindigkeitsvorteil. Nehmen Sie zur Minimierung von Kollisionen etwa 0x58a54cf5.
Die Verwendung verschiedener Multiplikatoren an verschiedenen Orten ist hilfreich, reicht jedoch wahrscheinlich nicht aus, um die zusätzliche Arbeit zu rechtfertigen.
Beim Kombinieren von Hashwerten verwende ich normalerweise die Kombinationsmethode, die in der Boost C ++ - Bibliothek verwendet wird, nämlich:
seed ^= hasher(v)+0x9e3779b9+(seed<<6)+(seed>>2);
Dies sorgt für eine ziemlich gleichmäßige Verteilung. Weitere Informationen zur Funktionsweise dieser Formel finden Sie im Beitrag zu StackOverflow: Magische Zahl in boost :: hash_combine
Für eine einfache Klasse ist es oft am einfachsten, hashCode () basierend auf den Klassenfeldern zu implementieren, die von der equals () -Implementierung überprüft werden.
Das Wichtigste ist, hashCode () und equals () konsistent zu halten: Wenn equals () für zwei Objekte true zurückgibt, sollte hashCode () denselben Wert zurückgeben. Wenn equals () false zurückgibt, sollte hashCode () unterschiedliche Werte zurückgeben.
Wie SquareCog schon bemerkt hat. Wenn Hashcode einmal aus der Verkettung von zwei Zeichenfolgen generiert wird, ist es extrem einfach, Massen von Kollisionen zu generieren : ("abc"+""=="ab"+"c"=="a"+"bc"==""+"abc"). Es ist ein schwerer Fehler. Es wäre besser, den Hashcode für beide Felder auszuwerten und dann eine lineare Kombination davon zu berechnen (vorzugsweise unter Verwendung von Primzahlen als Koeffizienten).
Krzysztof Jabłoński
@ KrzysztofJabłoński Richtig. Außerdem tauschen foound barerzeugt eine unnötige Kollision auch.
Objects.hashCode(collection)
sollte ich eine perfekte Lösung sein!collection.hashCode()
( hg.openjdk.java.net/jdk7/jdk7/jdk/file/9b8c96f96a0f/src/share/… )Antworten:
Die beste Implementierung? Das ist eine schwierige Frage, da sie vom Verwendungsmuster abhängt.
A für fast alle Fälle angemessen gute Umsetzung wurde vorgeschlagen Josh Bloch ‚s Effective Java in Punkt 8 (zweite Auflage). Das Beste ist, es dort nachzuschlagen, weil der Autor dort erklärt, warum der Ansatz gut ist.
Eine kurze Version
Erstellen Sie einen Wert
int result
und weisen Sie einen Wert ungleich Null zu.Berechnen Sie für jedes
f
in derequals()
Methode getestete Feld einen Hash-Codec
mit:boolean
: berechnen(f ? 0 : 1)
;byte
istchar
,short
oderint
: berechnen(int)f
;long
: berechnen(int)(f ^ (f >>> 32))
;float
: berechnenFloat.floatToIntBits(f)
;double
: BerechnenDouble.doubleToLongBits(f)
und behandeln Sie den Rückgabewert wie jeden langen Wert;hashCode()
Methode oder 0 iff == null
;Kombinieren Sie den Hashwert
c
mitresult
:Rückkehr
result
Dies sollte für die meisten Verwendungssituationen zu einer ordnungsgemäßen Verteilung der Hashwerte führen.
quelle
Wenn Sie mit der von dmeister empfohlenen effektiven Java-Implementierung zufrieden sind, können Sie einen Bibliotheksaufruf verwenden, anstatt Ihren eigenen zu rollen:
Dies erfordert entweder Guava (
com.google.common.base.Objects.hashCode
) oder die Standardbibliothek in Java 7 (java.util.Objects.hash
), funktioniert jedoch auf die gleiche Weise.quelle
hashCode
ist, wenn Sie eine benutzerdefinierte habenequals
, und genau dafür sind diese Bibliotheksmethoden konzipiert. Die Dokumentation ist ziemlich klar über ihr Verhalten in Bezug aufequals
. Eine Bibliotheksimplementierung erhebt keinen Anspruch darauf, Sie von den Merkmalen einer korrektenhashCode
Implementierung zu entbinden. Diese Bibliotheken erleichtern Ihnen die Implementierung einer solchen konformen Implementierung in den meisten Fällen, in denen sieequals
überschrieben wird.java.util.Objects.hash(...)
Methode als die Guavenmethode gewählt hättecom.google.common.base.Objects.hashCode(...)
. Ich denke, die meisten Leute würden die Standardbibliothek einer zusätzlichen Abhängigkeit vorziehen.hashCode()
Ihren Erwartungen, da es für ein Array nur das istjava.lang.System.identityHashCode(...)
.Es ist besser, die von Eclipse bereitgestellten Funktionen zu verwenden, die ziemlich gute Arbeit leisten, und Sie können Ihre Anstrengungen und Energie in die Entwicklung der Geschäftslogik stecken.
quelle
Obwohl dies mit der
Android
Dokumentation (Wayback Machine) und meinem eigenen Code auf Github verbunden ist funktioniert es im Allgemeinen für Java. Meine Antwort ist eine Erweiterung von dmeisters Antwort mit nur Code, der viel einfacher zu lesen und zu verstehen ist.BEARBEITEN
Wenn Sie überschreiben
hashcode(...)
, möchten Sie normalerweise auch überschreibenequals(...)
. Für diejenigen, die bereits implementiert haben oder bereits implementiert habenequals
, ist hier eine gute Referenz von meinem Github ...quelle
Stellen Sie zunächst sicher, dass equals korrekt implementiert ist. Aus einem IBM DeveloperWorks-Artikel :
Stellen Sie dann sicher, dass die Beziehung zu hashCode den Kontakt berücksichtigt (aus demselben Artikel):
Schließlich sollte eine gute Hash-Funktion danach streben, sich der idealen Hash-Funktion anzunähern .
quelle
about8.blogspot.com, sagten Sie
Ich kann dir nicht zustimmen. Wenn zwei Objekte denselben Hashcode haben, muss dies nicht bedeuten, dass sie gleich sind.
Wenn A gleich B ist, muss A.hashcode gleich B.hascode sein
aber
Wenn A.hashcode gleich B.hascode ist, bedeutet dies nicht, dass A gleich B sein muss
quelle
(A != B) and (A.hashcode() == B.hashcode())
ja, nennen wir das Hash-Funktionskollision. Dies liegt daran, dass die Codomäne der Hash-Funktion immer endlich ist, während dies bei der Domain normalerweise nicht der Fall ist. Je größer die Codomäne ist, desto seltener sollte die Kollision auftreten. Gute Hash-Funktionen sollten unterschiedliche Hashes für unterschiedliche Objekte zurückgeben, wobei die größte Wahrscheinlichkeit bei einer bestimmten Codomänengröße erreichbar ist. Es kann jedoch selten vollständig garantiert werden.Wenn Sie Eclipse verwenden, können Sie Folgendes generieren
equals()
undhashCode()
verwenden:Mit dieser Funktion können Sie entscheiden, welche Felder Sie für die Berechnung von Gleichheit und Hashcode verwenden möchten, und Eclipse generiert die entsprechenden Methoden.
quelle
Es gibt eine gute Umsetzung der Effective Java ‚s
hashcode()
undequals()
Logik in Apache Commons Lang . Kasse HashCodeBuilder und EqualsBuilder .quelle
Objects
Klasse bietethash(Object ..args)
undequals()
Methoden von Java7 auf. Diese werden für alle Anwendungen empfohlen, die jdk 1.7+ verwendenIdentityHashMap
). FWIW Ich verwende einen ID-basierten Hashcode und ist für alle Entitäten gleich.Nur eine kurze Anmerkung zum Ausfüllen anderer detaillierterer Antworten (in Bezug auf den Code):
Wenn ich die Frage betrachte, wie ich eine Hash-Tabelle in Java erstelle, und insbesondere den jGuru-FAQ-Eintrag , glaube ich, dass einige andere Kriterien, anhand derer ein Hash-Code beurteilt werden könnte, sind:
quelle
Wenn ich Ihre Frage richtig verstehe, haben Sie eine benutzerdefinierte Auflistungsklasse (dh eine neue Klasse, die sich über die Auflistungsschnittstelle erstreckt) und möchten die Methode hashCode () implementieren.
Wenn Ihre Auflistungsklasse AbstractList erweitert, müssen Sie sich keine Sorgen machen. Es gibt bereits eine Implementierung von equals () und hashCode (), bei der alle Objekte durchlaufen und ihre hashCodes () addiert werden.
Wenn Sie nun den Hash-Code für eine bestimmte Klasse am besten berechnen möchten, verwende ich normalerweise den Operator ^ (bitweise exklusiv oder), um alle Felder zu verarbeiten, die ich in der Methode equals verwende:
quelle
@ about8: da ist ein ziemlich schwerwiegender Fehler.
gleicher Hashcode
Sie wollen wahrscheinlich so etwas wie
(Kann man hashCode heutzutage direkt von int in Java bekommen? Ich denke, es macht ein Autocasting. Wenn das der Fall ist, überspringe den toString, es ist hässlich.)
quelle
foo
undbar
führt zum selbenhashCode
. IhrtoString
AFAIK wird nicht kompiliert, und wenn ja, ist es schrecklich ineffizient. So etwas109 * getFoo().hashCode() + 57 * getBar().hashCode()
ist schneller, einfacher und erzeugt keine unnötigen Kollisionen.Da Sie speziell nach Sammlungen gefragt haben, möchte ich einen Aspekt hinzufügen, den die anderen Antworten noch nicht erwähnt haben: Eine HashMap erwartet nicht, dass ihre Schlüssel ihren Hashcode ändern, sobald sie der Sammlung hinzugefügt werden. Würde den ganzen Zweck besiegen ...
quelle
Verwenden Sie die Reflektionsmethoden für Apache Commons EqualsBuilder und HashCodeBuilder .
quelle
Ich benutze einen winzigen Wrapper,
Arrays.deepHashCode(...)
weil er Arrays, die als Parameter geliefert werden, korrekt behandeltquelle
Jede Hashing-Methode, die den Hash-Wert gleichmäßig über den möglichen Bereich verteilt, ist eine gute Implementierung. Siehe effektives Java ( http://books.google.com.au/books?id=ZZOiqZQIbRMC&dq=effective+java&pg=PP1&ots=UZMZ2siN25&sig=kR0n73DHJOn-D77qGj0wOxAxiZw&hl=en=res ) dort für die Implementierung von Hashcode (Punkt 9 denke ich ...).
quelle
Ich bevorzuge die Verwendung von Dienstprogrammmethoden aus der Google Collections-Bibliothek der Klasse Objects , mit denen ich meinen Code sauber halten kann. Sehr oft
equals
undhashcode
Methoden werden aus der IDE-Vorlage erstellt, sodass sie nicht sauber zu lesen sind.quelle
Hier ist eine weitere Demonstration des JDK 1.7+ -Ansatzes mit berücksichtigten Superklassenlogiken. Ich sehe es als ziemlich praktisch an, wenn die Objektklasse hashCode () berücksichtigt wird, reine JDK-Abhängigkeit und keine zusätzliche manuelle Arbeit. bitte beachten Sie
Objects.hash()
tolerant ist.Ich habe keine
equals()
Implementierung aufgenommen, aber in Wirklichkeit werden Sie sie natürlich brauchen.quelle
Die Standardimplementierung ist schwach und führt zu unnötigen Kollisionen. Stellen Sie sich a
Jetzt,
und
haben das gleiche
hashCode
, nämlich31*(a+b) + c
als Multiplikator fürList.hashCode
verwendete hier wiederverwendet wird. Kollisionen sind natürlich unvermeidlich, aber unnötige Kollisionen zu erzeugen ist einfach ... unnötig.Es ist nichts wesentlich Kluges an der Verwendung
31
. Der Multiplikator muss ungerade sein, um Informationsverluste zu vermeiden (jeder gerade Multiplikator verliert mindestens das höchstwertige Bit, Vielfache von vier verlieren zwei usw.). Jeder ungerade Multiplikator ist verwendbar. Kleine Multiplikatoren können zu einer schnelleren Berechnung führen (die JIT kann Verschiebungen und Additionen verwenden), aber da die Multiplikation bei modernen Intel / AMD nur eine Latenz von drei Zyklen aufweist, spielt dies kaum eine Rolle. Kleine Multiplikatoren führen auch zu mehr Kollisionen bei kleinen Eingaben, was manchmal ein Problem sein kann.Die Verwendung einer Primzahl ist sinnlos, da Primzahlen im Ring Z / (2 ** 32) keine Bedeutung haben.
Daher würde ich empfehlen, eine zufällig ausgewählte große ungerade Zahl zu verwenden (zögern Sie nicht, eine Primzahl zu nehmen). Da i86 / amd64-CPUs einen kürzeren Befehl für Operanden verwenden können, die in ein einzelnes vorzeichenbehaftetes Byte passen, gibt es für Multiplikatoren wie 109 einen winzigen Geschwindigkeitsvorteil. Nehmen Sie zur Minimierung von Kollisionen etwa 0x58a54cf5.
Die Verwendung verschiedener Multiplikatoren an verschiedenen Orten ist hilfreich, reicht jedoch wahrscheinlich nicht aus, um die zusätzliche Arbeit zu rechtfertigen.
quelle
Beim Kombinieren von Hashwerten verwende ich normalerweise die Kombinationsmethode, die in der Boost C ++ - Bibliothek verwendet wird, nämlich:
Dies sorgt für eine ziemlich gleichmäßige Verteilung. Weitere Informationen zur Funktionsweise dieser Formel finden Sie im Beitrag zu StackOverflow: Magische Zahl in boost :: hash_combine
Es gibt eine gute Diskussion über verschiedene Hash-Funktionen unter: http://burtleburtle.net/bob/hash/doobs.html
quelle
Für eine einfache Klasse ist es oft am einfachsten, hashCode () basierend auf den Klassenfeldern zu implementieren, die von der equals () -Implementierung überprüft werden.
Das Wichtigste ist, hashCode () und equals () konsistent zu halten: Wenn equals () für zwei Objekte true zurückgibt, sollte hashCode () denselben Wert zurückgeben. Wenn equals () false zurückgibt, sollte hashCode () unterschiedliche Werte zurückgeben.
quelle
("abc"+""=="ab"+"c"=="a"+"bc"==""+"abc")
. Es ist ein schwerer Fehler. Es wäre besser, den Hashcode für beide Felder auszuwerten und dann eine lineare Kombination davon zu berechnen (vorzugsweise unter Verwendung von Primzahlen als Koeffizienten).foo
undbar
erzeugt eine unnötige Kollision auch.