Warum ist die XOR-Operation der Standard-Weg, um zu kombinieren hashes?

xor ist eine gefährliche Standard-Funktion verwenden, wenn das hashing. Es ist besser als und und oder, aber das macht nicht viel sagen.

xor ist symmetrisch, so ist die Reihenfolge der Elemente geht verloren. So "bad" wird hash kombinieren die gleichen wie "dab".

xor-Karten identische Werte auf null, und Sie sollten es vermeiden mapping "gemeinsame" Werte auf null:

So (a,a) bekommt die 0 zugeordnet, und (b,b) bekommt auch 0 zugeordnet. Als solche Paare sind häufiger als Zufälligkeit könnte bedeuten, dass Sie am Ende mit viel zu viele Kollisionen bei null, als Sie sollten.

Mit diesen beiden Problemen, xor am Ende ein hash-combiner, sieht halbwegs anständige auf der Oberfläche, nicht aber nach einer weiteren Inspektion.

Auf moderner hardware hinzufügen in der Regel etwa so schnell wie xor (es verwendet wahrscheinlich mehr Strom zu ziehen diese aus, zugegeben). Hinzufügen Wahrheit Tabelle ist ähnlich wie xor auf das bit in Frage, aber es sendet auch ein bit zum nächsten bit beendet, wenn beide Werte 1 sind. Dies bringt weniger Informationen.

So hash(a) + hash(b) ist besser, wenn a==b, das Ergebnis ist stattdessen hash(a)<<1 statt 0.

Bleibt symmetrisch. Wir brechen diese Symmetrie für eine bescheidene Kosten:

hash(a)<<1 + hash(a) + hash(b)

aka hash(a)*3 + hash(b). (Berechnung hash(a) einmal und speichern ist zu empfehlen, wenn Sie verwenden Sie die Umschalt-Lösung). Jede ungerade Konstante anstelle von 3 wird bijectively Karte ein size_t (oder k-bit-unsigned-Konstante) zu sich selbst, als Karte auf unsigned-Konstanten math modulo 2^k für einige k, und jede ungerade Konstante teilerfremd zu 2^k.

Für einen noch eleganteren version, können wir untersuchen boost::hash_combine effektiv:

size_t hash_combine( size_t lhs, size_t rhs ) {
  lhs^= rhs + 0x9e3779b9 + (lhs << 6) + (lhs >> 2);
  return lhs;
}

hier fügen wir zusammen einige verschobene Versionen von seed mit einer Konstanten (das ist im Grunde zufällig 0s und 1s -- insbesondere ist die inverse der goldene Schnitt als ein 32-bit-fixed-point-Fraktion) mit etwas Zusatz und einem xor. Dies bricht die Symmetrie, und stellt einige "Lärm", wenn die eingehenden Hash-Werte schlecht sind (dh, stellen Sie sich vor jede Komponente hashes 0 -- die oben behandelt Sie gut, Sie generieren ein Abstrich von 1 und 0s nach jedem kombinieren. Mir einfach die Ausgänge a 0).

Für diejenigen, die nicht vertraut mit C/C++, eine size_t ist ein unsigned-integer-Wert, der groß genug ist, um zu beschreiben, die Größe eines Objekts im Speicher. Auf einem 64 bit-system, es ist in der Regel eine 64-bit-Ganzzahl. Auf einem 32 bit system ein 32-bit unsigned integer.

InformationsquelleAutor Yakk - Adam Nevraumont

Xor kann der "Standard" Weg, um zu kombinieren, hashes, aber Greg Hewgill die Antwort zeigt auch, warum es hat seine Tücken:
Das xor von zwei identischen hash-Werte gleich null ist.
Im wirklichen Leben gibt es identische hashes sind häufiger, als man erwartet haben könnte. Dann könnten Sie feststellen, dass in diesen (nicht so seltene) Ausnahmefälle, die resultierenden kombinierten hashes sind immer die gleichen (null). Hash-Kollisionen wäre viel, viel häufiger, als Sie erwarten.

In ein erfundenes Beispiel könnte man das kombinieren der Hash-Passwörter von Benutzern aus verschiedenen websites, die Sie verwalten. Leider, eine große Anzahl von Benutzern wiederverwenden Ihre Kennwörter, und einen überraschenden Anteil des resultierenden hashes sind gleich null!

InformationsquelleAutor Leo Goodstadt

Wenn Sie XOR eine zufällige Eingabe mit einem voreingenommenen Eingabe, die Ausgabe ist zufällig. Das gleiche gilt nicht für AND oder OR. Beispiel:

00101001 XOR 00000000 = 00101001 
00101001 UND 00000000 = 00000000 
00101001 ODER 11111111 = 11111111 

Als @Greg Hewgill erwähnt, auch wenn beide Eingänge sind zufällig, mit AND oder OR führt voreingenommenen Ausgang.

Dem Grund verwenden wir XOR über etwas mehr Komplex ist, dass es, es gibt keine Notwendigkeit: XOR funktioniert perfekt, und es ist unglaublich dumm-schnell.

InformationsquelleAutor BlueRaja - Danny Pflughoeft

Abdeckung der linken 2 Spalten und versuchen, herauszufinden, was die Eingänge werden mit nur der Ausgabe.

 a | b | a AND b
---+---+--------
 0 | 0 |    0
 0 | 1 |    0
 1 | 0 |    0
 1 | 1 |    1

Sah man ein 1-bit-sollten Sie arbeitete heraus, dass beide Eingänge waren 1.

Nun tun Sie dasselbe mit XOR

 a | b | a XOR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    0

XOR gibt nichts über es-Eingänge.

InformationsquelleAutor Robert