Zusammengesetzte Objekte hashen

9

BEARBEITEN: Diese Frage bezieht sich nicht auf bitweise Operatoren und kann nicht mit Warum wird XOR oft in Java hashCode () verwendet, aber andere bitweise Operatoren werden selten verwendet?

Ich habe verschiedene Ansätze für die Hash-Berechnung von Objekten gesehen:

%Vor%

Es scheint, dass die LIB-Methode SUM verwendet, aber warum ist es besser als XOR?

Obwohl das Beispiel in Java ist, geht es bei dieser Frage mehr um Mathematik und Wahrscheinlichkeiten.

    
Basilevs 25.06.2013, 12:16
quelle

2 Antworten

4

Die SUM stellt sicher, dass Sie alle Bits des Hashcodes verwenden, um Ihr Hashing zu verteilen (in diesem Fall die 32 Bits eines int), und macht keine Hypothese über die Implementierung von sub hashcode () dafür.

Das XOR hat nur die gleiche Eigenschaft, wenn der Hashcode von B und C es hat, sonst wird es nur das Minimum der Anzahl "nützlicher" Bits in B- und C-Hashcode verwenden, was zu einer schlechteren Verteilung führen könnte, und häufigerer Zusammenstoß. Es ist sehr einfach, das Problem zu sehen, wenn B und C Ganzzahlen sind, die dazu neigen, sehr klein zu sein, Sie werden immer nur die ersten paar Bits verwenden (da int.hashcode () die Identitätsfunktion ist).

    
C4stor 25.06.2013, 12:24
quelle
0

Dies liegt daran, dass sum für eine bessere Verteilung sorgt als xor .

Wenn zum Beispiel int a und b Werte zwischen 0 und 7 haben ( 000 und 111 binär), dann ist das Ergebnis von xor dieser beiden Argumente immer zwischen 0 und 7 (als xor wird nur 3 Bits ändern). Wenn Sie nun eine Multiplikation und sum durchführen, haben Sie eine viel bessere Verteilung, da die Werte nicht innerhalb des Bereichs 0 und 7 liegen.

    
Adam Siemion 25.06.2013 12:19
quelle

Tags und Links