Wie implementiere ich einen guten Hashcode, wenn es zwei boolesche Felder gibt? Normalerweise fügen Leute nur ihre ganzzahligen Werte ihren Hashcode-Werten hinzu. Aber wenn ich einfach 1 oder 0 zu meinem Hashcode hinzufüge, denke ich nicht, dass es gut ist. Denn wenn ich zwei Objekte der Klasse A habe:
obj1.b = true, obj1.c = false.
obj2.b = false, obj2.c = true.
Alles andere ist gleich. Dann ist der Hashcode für diese zwei ungleichen Objekte gleich. Ich weiß, dass diese Situation in Ordnung ist. Aber stell dir vor, wenn es 100 boolesche Felder gibt, dann würde es zu viel Kollision geben, oder? Ich möchte nicht, dass so viele verschiedene Objekte in den gleichen Eimer fallen.
Was ich im Folgenden gemacht habe, ist, verschiedenen Wahrheitswerten für jedes Feld unterschiedliche Zahlen zuzuordnen, damit die Hashcodes der Objekte sehr unterschiedlich sein können.
%Vor%Sie haben ein paar Optionen:
Der beste Weg zu garantieren , dass nie Kollisionen zwischen booleschen Hashes sein können, ist eine ähnliche Technik wie in bit flagging , wobei jeder Boolean sein eigenes Bit belegt. Zum Beispiel:
%Vor% Dieser Ansatz wird jedoch bei einer großen Anzahl von Booleschen Werten schnell ineffizient und hängt stark von der Größe des Zielarrays ab. Wenn Sie beispielsweise ein Zielarray der Größe 16 haben, haben nur die ersten 4 Auswirkungen auf den Hashwert (da der maximale Index 1111 ist).
Die zwei Lösungen dafür sind, entweder die Größe Ihres Zielarrays zu erhöhen (was möglicherweise nicht unter Ihrer Kontrolle steht), oder sicherzustellen, dass die Reihenfolge Ihrer Booleschen Werte von den meisten zu den kleinsten variiert. Keine von beiden ist optimal, und so ist diese Methode schnell und einfach, aber in der Praxis nicht sehr effektiv.
Das Design, das Pham Trung in seiner Antwort zeigt , erweitert Option 1 um eine einfachere Möglichkeit, mehrere Felder unterzubringen. Als Adrian Shum kommentierte , diese Antwort bietet einen Überblick über einen" allgemeinen Hashalgorithmus ", der unabhängig von dem, was Sie zu hashen versuchen, effektiv ist.
Die Grundidee besteht darin, einen vereinfachten Hash-Wert für jeden Typ mit einer beliebig großen Primzahl zu multiplizieren, um sicherzustellen, dass jeder Hash eindeutig ist (obwohl der Beweis dafür mir entgeht). Zum Beispiel:
%Vor% Für eine noch dünnere Hash-Verteilung können Sie dies wie folgt mit Boolean.hashCode kombinieren anzeigen:
Das Beste an dieser Lösung ist, dass sie auf andere Typen angewendet werden kann, wie Sie sie bereits in Ihrem Beispielcode haben:
%Vor% Hinweis : In diesen Beispielen ist 31 nur eine beliebige Primzahl. Sie hätten einfach 37 , 113 oder 23456789 verwenden können. Es gibt jedoch Kompromisse bei der Verwendung größerer Multiplikanden, nämlich dass Ihr Hash schneller Integer.MAX_VALUE überschreitet und Ihren Hash ungültig macht.
Wenn Sie zwei oder mehr boolesche Werte haben, ist der Hashcode-Algorithmus bereits dafür zuständig.
Schauen Sie ein wenig näher:
%Vor%Beachten Sie den Hauptteil der for-Schleife, in diesem Fall behandeln wir jeden booleschen Wert unterschiedlich, da wir das Ergebnis immer mit 31 (oder einer beliebigen guten Primzahl) multiplizieren, bevor wir es zum Ergebnis hinzufügen .
Wenn wir den gesamten Hashcode als eine Anzahl von Basis 31 visualisieren, können wir verstehen, dass die Position und der Wert jedes booleschen Wertes im Endergebnis berücksichtigt werden. Jeder boolesche Wert kann im Hashcode als Ziffer behandelt werden. Für den Fall (wahr, falsch) und den Fall (falsch, wahr) haben sie zwei verschiedene Hashcodes.
Bei der Kombination mehrerer Felder empfiehlt es sich, mit dem ersten Feld hashCode zu beginnen und dann das aktuelle Ergebnis mit einer Primzahl zu multiplizieren, bevor Sie jedes Feld hashcode hinzufügen:
%Vor%Sie können ein Beispiel aus der Praxis in Code von Draht generiert (eine Prococol-Puffer-Implementierung).
Referenzen: