Warum ist XOR die Standardmethode zum Kombinieren von Hashes?

145

Angenommen, Sie haben zwei Hashes H(A)und H(B)möchten diese kombinieren. Ich habe gelesen, dass eine gute Möglichkeit, zwei Hashes zu kombinieren, darin besteht XOR, z XOR( H(A), H(B) ).

Die beste Erklärung, die ich gefunden habe, wird hier in den Richtlinien für Hash-Funktionen kurz angesprochen :

Das XORing von zwei Zahlen mit ungefähr zufälliger Verteilung führt zu einer anderen Zahl mit ungefähr zufälliger Verteilung *, die nun jedoch von den beiden Werten abhängt.
...
* Bei jedem Bit der beiden zu kombinierenden Zahlen wird eine 0 ausgegeben, wenn die beiden Bits gleich sind, andernfalls eine 1. Mit anderen Worten, in 50% der Kombinationen wird eine 1 ausgegeben. Wenn also die beiden Eingangsbits jeweils eine Chance von ungefähr 50-50 haben, 0 oder 1 zu sein, wird dies auch für das Ausgangsbit der Fall sein.

Können Sie die Intuition und / oder Mathematik erklären, warum XOR die Standardoperation zum Kombinieren von Hash-Funktionen sein sollte (anstelle von ODER oder UND usw.)?

Nate Murray
quelle
20
Ich denke du hast es gerade getan;)
Massa
22
Beachten Sie, dass XOR eine "gute" Möglichkeit sein kann, Hashes zu "kombinieren", je nachdem, was Sie in einer "Kombination" möchten. XOR ist kommutativ: XOR (H (A), H (B)) ist gleich XOR (H (B), H (A)). Dies bedeutet, dass XOR kein geeigneter Weg ist, um eine Art Hash einer geordneten Folge von Werten zu erstellen, da die Reihenfolge nicht erfasst wird.
Thomas Pornin
6
Neben dem Problem mit der Reihenfolge (Kommentar oben) gibt es ein Problem mit gleichen Werten. XOR (H (1), H (1)) = 0 (für jede Funktion H), XOR (H (2), H (2)) = 0 und so weiter. Für jedes N: XOR (H (N), H (N)) = 0. Gleiche Werte treten in realen Apps häufig auf. Dies bedeutet, dass das Ergebnis von XOR zu oft 0 ist, um als guter Hash angesehen zu werden.
Andrei Galatyn
Was verwenden Sie für die geordnete Folge von Werten? Angenommen, ich möchte einen Hash aus Zeitstempel oder Index erstellen. (MSB weniger wichtig als LSB). Entschuldigung, wenn dieser Thread 1 Jahr alt ist.
Alexis

Antworten:

120

Unter der Annahme gleichmäßig gleichmäßiger (1-Bit) Eingaben beträgt die Wahrscheinlichkeitsverteilung der UND-Funktionsausgabe 75% 0und 25% 1. Umgekehrt beträgt OR 25% 0und 75% 1.

Die XOR-Funktion beträgt 50% 0und 50% 1, daher eignet sie sich gut zum Kombinieren gleichmäßiger Wahrscheinlichkeitsverteilungen.

Dies kann durch Ausschreiben von Wahrheitstabellen gesehen werden:

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

 a | b | a OR b
---+---+--------
 0 | 0 |    0
 0 | 1 |    1
 1 | 0 |    1
 1 | 1 |    1

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

Aufgabe: Wie viele logische Funktionen von zwei 1-Bit-Eingängen aund bdiese gleichmäßige Ausgangsverteilung? Warum ist XOR für den in Ihrer Frage angegebenen Zweck am besten geeignet?

Greg Hewgill
quelle
24
Antwort auf die Übung: Von den 16 möglichen unterschiedlichen a XXX b-Operationen (0, a & b, a > b, a, a < b, b, a % b, a | b, !a & !b, a == b, !b, a >= b, !a, a <= b, !a | !b, 1)haben die folgenden 50% -50% -Verteilungen von 0s und 1s, vorausgesetzt, a und b haben 50% -50% -Verteilungen von 0s und 1s: a, b, !a, !b, a % b, a == bdh das Gegenteil von XOR (EQUIV) hätte auch verwendet werden können ...
Massa
7
Greg, das ist eine großartige Antwort. Die Glühbirne ging für mich an, nachdem ich Ihre ursprüngliche Antwort gesehen und meine eigenen Wahrheitstabellen aufgeschrieben hatte. Ich habe mir die Antwort von @ Massa überlegt, wie es 6 geeignete Operationen zur Aufrechterhaltung der Verteilung gibt. Und während Sie a, b, !a, !bdie gleiche Verteilung wie die jeweiligen Eingaben haben, verlieren Sie die Entropie der anderen Eingaben. Das heißt, XOR eignet sich am besten zum Kombinieren von Hashes, da wir die Entropie sowohl von a als auch von b erfassen möchten.
Nate Murray
1
In diesem Artikel wird erklärt, dass das sichere Kombinieren von Hashes, bei denen jede Funktion nur einmal aufgerufen wird, nicht möglich ist, ohne weniger Bits als die Summe der Anzahl der Bits in jedem Hashwert auszugeben. Dies deutet darauf hin, dass diese Antwort nicht korrekt ist.
Tamás Szelei
3
@Massa Ich habe noch nie gesehen, dass% für XOR verwendet wurde oder nicht gleich.
Buge
7
Wie Yakk betont, kann XOR gefährlich sein, da es für identische Werte Null erzeugt. Dieses Mittel (a,a)und (b,b)erzeugen beide Null, was in vielen ( die meisten?) Fällen erheblich die Wahrscheinlichkeit von Kollisionen in Hash-basierten Datenstrukturen erhöht.
Drew Noakes
170

xorist eine gefährliche Standardfunktion, die beim Hashing verwendet wird. Es ist besser als andund or, aber das sagt nicht viel.

xorist symmetrisch, so dass die Reihenfolge der Elemente verloren geht. Also "bad"wird Hash das gleiche kombinieren wie "dab".

xor Ordnet paarweise identische Werte Null zu, und Sie sollten vermeiden, "allgemeine" Werte Null zuzuordnen:

Also (a,a)auf 0 abgebildet wird, und (b,b)auch auf 0 abgebildet wird als solche Paare sind fast immer häufiger als Zufälligkeit könnte bedeuten, Sie am Ende mit viel zu vielen Kollisionen auf Null , als Sie sollten.

Mit diesen beiden Problemen wird xores zu einem Hash-Kombinierer, der auf der Oberfläche halbwegs anständig aussieht, aber nicht nach weiterer Prüfung.

Bei moderner Hardware ist das Hinzufügen normalerweise ungefähr so ​​schnell wie xor(es verbraucht wahrscheinlich mehr Strom, um dies zu erreichen, zugegebenermaßen). Die Wahrheitstabelle des Hinzufügens ähnelt der xordes betreffenden Bits, sendet jedoch auch ein Bit zum nächsten Bit, wenn beide Werte 1 sind. Dies bedeutet, dass weniger Informationen gelöscht werden.

Ist also hash(a) + hash(b)besser als hash(a) xor hash(b)wenn a==b, wenn das Ergebnis hash(a)<<1statt 0 ist.

Dies bleibt symmetrisch; so das "bad"und "dab"das gleiche Ergebnis erhalten bleibt ein Problem. Wir können diese Symmetrie für bescheidene Kosten brechen:

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

aka hash(a)*3 + hash(b). (Einmaliges Berechnen hash(a)und Speichern wird empfohlen, wenn Sie die Schichtlösung verwenden). Jede ungerade Konstante anstelle von 3wird eine kvorzeichenlose Ganzzahl mit " -bit" bijektiv auf sich selbst abbilden, da die Zuordnung auf vorzeichenlosen Ganzzahlen 2^kfür einige mathematisch modulo kist und jede ungerade Konstante relativ prim ist 2^k.

Für eine noch schickere Version können wir untersuchen boost::hash_combine, was effektiv ist:

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

Hier addieren wir einige verschobene Versionen von seedmit einer Konstanten (die im Grunde genommen zufällige 0s und 1s sind - insbesondere ist es die Umkehrung des Goldenen Schnitts als 32-Bit-Festkommafraktion) mit einer Addition und einem xor. Dies unterbricht die Symmetrie und führt zu einem gewissen "Rauschen", wenn die eingehenden Hash-Werte schlecht sind (dh stellen Sie sich vor, dass jede Komponente auf 0 gehasht wird - das oben Gesagte behandelt dies gut 1und erzeugt 0nach jedem Mähdrescher einen Abstrich von und s. Meine Naivität 3*hash(a)+hash(b)gibt einfach ein 0In aus dieser Fall).

(Für diejenigen, die mit C / C ++ nicht vertraut sind, size_tist a ein vorzeichenloser Ganzzahlwert, der groß genug ist, um die Größe eines Objekts im Speicher zu beschreiben. Auf einem 64-Bit-System ist es normalerweise eine 64-Bit-Ganzzahl ohne Vorzeichen. Auf einem 32-Bit-System , eine 32-Bit-Ganzzahl ohne Vorzeichen.)

Yakk - Adam Nevraumont
quelle
Schöne Antwort Yakk. Funktioniert dieser Algorithmus auf 32-Bit- und 64-Bit-Systemen gleich gut? Vielen Dank.
Dave
1
@ Dave füge weitere Bits hinzu 0x9e3779b9.
Yakk - Adam Nevraumont
10
OK, um vollständig zu sein ... hier ist die 64-Bit-Konstante mit voller Genauigkeit (berechnet mit langen Doubles und vorzeichenlosen langen Longs): 0x9e3779b97f4a7c16. Interessanterweise ist es immer noch gerade. Wenn Sie dieselbe Berechnung mit PI anstelle des Goldenen Schnitts wiederholen, erhalten Sie: 0x517cc1b727220a95, was ungerade statt gerade ist und daher wahrscheinlich "mehr Primzahl" als die andere Konstante. Ich habe verwendet: std :: cout << std :: hex << (vorzeichenlos lang lang) ((1.0L / 3.14159265358979323846264338327950288419716939937510L) * (powl (2.0L, 64.0L)) << std :: endl; mit cout.precision (numeric_limits <long double> :: max_digits10); Nochmals vielen Dank Yakk.
Dave
2
@Dave Die inverse Goldene Schnitt-Regel für diese Fälle ist die erste ungerade Zahl, die gleich oder größer als die von Ihnen durchgeführte Berechnung ist. Fügen Sie also einfach 1 hinzu. Dies ist eine wichtige Zahl, da die Folge von N * das Verhältnis, mod die maximale Größe (hier 2 ^ 64) den nächsten Wert in der Folge genau in diesem Verhältnis in die Mitte der größten 'Lücke' in setzt Zahlen. Durchsuchen Sie das Web nach "Fibonacci Hashing" für weitere Informationen.
Scott Carey
1
@ Dave die richtige Nummer wäre 0.9E3779B97F4A7C15F39 ... Siehe Link . Sie könnten unter der Round-to-Even-Regel leiden (was für Buchhalter gut ist), oder einfach, wenn Sie mit einer wörtlichen sqrt (5) -Konstante beginnen, wenn Sie 1 subtrahieren, entfernen Sie das höherwertige Bit a Bit muss verloren gegangen sein.
Migle
29

Trotz seiner praktischen Bitmischungseigenschaften ist XOR aufgrund seiner Kommutativität keine gute Möglichkeit, Hashes zu kombinieren. Überlegen Sie, was passieren würde, wenn Sie die Permutationen von {1, 2,…, 10} in einer Hash-Tabelle mit 10 Tupeln speichern würden.

Eine viel bessere Wahl ist m * H(A) + H(B), wenn m eine große ungerade Zahl ist.

Gutschrift: Der obige Kombinierer war ein Tipp von Bob Jenkins.

Marcelo Cantos
quelle
2
Manchmal ist Kommutativität eine gute Sache, aber xor ist selbst dann eine schlechte Wahl , weil alle Paare übereinstimmender Gegenstände auf Null gehasht werden. Eine arithmetische Summe ist besser; Der Hash eines Paares übereinstimmender Elemente speichert nur 31 Bits nützlicher Daten anstatt 32, aber das ist viel besser als das Beibehalten von Null. Eine andere Möglichkeit kann darin bestehen, die arithmetische Summe als zu berechnen longund dann den oberen Teil wieder mit dem unteren Teil zu verbinden.
Supercat
1
m = 3ist eigentlich eine gute Wahl und auf vielen Systemen sehr schnell. Beachten Sie, dass für jede ungerade mGanzzahl die Multiplikation modulo 2^32oder 2^64daher invertierbar ist, damit Sie keine Bits verlieren.
StefanKarpinski
Was passiert, wenn Sie über MaxInt hinausgehen?
störende
2
Anstelle einer ungeraden Zahl sollte man eine Primzahl wählen
TermoTux
2
@Infinum ist beim Kombinieren von Hashes nicht erforderlich.
Marcelo Cantos
17

Xor mag die "Standard" -Methode zum Kombinieren von Hashes sein, aber Greg Hewgills Antwort zeigt auch, warum es seine Tücken hat: Das xor von zwei identischen Hash-Werten ist Null. Im wirklichen Leben gibt es identische Hashes, die häufiger vorkommen als erwartet. Möglicherweise stellen Sie dann fest, dass in diesen (nicht so seltenen) Eckfällen die resultierenden kombinierten Hashes immer gleich sind (Null). Hash-Kollisionen wären viel, viel häufiger als erwartet.

In einem erfundenen Beispiel kombinieren Sie möglicherweise Hash-Passwörter von Benutzern von verschiedenen Websites, die Sie verwalten. Leider verwendet eine große Anzahl von Benutzern ihre Passwörter wieder, und ein überraschender Anteil der resultierenden Hashes ist Null!

Leo Goodstadt
quelle
Ich hoffe, das erfundene Beispiel kommt nie vor, Passwörter sollten gesalzen werden.
user60561
8

Es gibt etwas, auf das ich ausdrücklich für andere hinweisen möchte, die diese Seite finden. UND und ODER beschränken die Ausgabe wie BlueRaja - Danny Pflughoe versucht darauf hinzuweisen, kann aber besser definiert werden:

Zuerst möchte ich zwei einfache Funktionen definieren, mit denen ich dies erklären werde: Min () und Max ().

Min (A, B) gibt den Wert zurück, der zwischen A und B kleiner ist, zum Beispiel: Min (1, 5) gibt 1 zurück.

Max (A, B) gibt den Wert zurück, der zwischen A und B größer ist, zum Beispiel: Max (1, 5) gibt 5 zurück.

Wenn Sie gegeben werden: C = A AND B

Dann können Sie feststellen, dass C <= Min(A, B)wir das wissen, weil es nichts gibt, was Sie UND mit den 0 Bits von A oder B können, um sie zu 1s zu machen. Jedes Nullbit bleibt also ein Nullbit und jedes einzelne Bit hat die Chance, ein Nullbit (und damit ein kleinerer Wert) zu werden.

Mit: C = A OR B

Das Gegenteil ist der Fall: C >= Max(A, B)Damit sehen wir die Folge der UND-Funktion. Jedes Bit, das bereits eine Eins ist, kann nicht zu einer Null ODER-verknüpft werden, daher bleibt es eine Eins, aber jedes Null-Bit hat die Chance, eine Eins und damit eine größere Zahl zu werden.

Dies bedeutet, dass der Status der Eingabe Einschränkungen für die Ausgabe anwendet. Wenn Sie UND irgendetwas mit 90, wissen Sie, dass die Ausgabe gleich oder kleiner als 90 ist, unabhängig davon, was der andere Wert ist.

Für XOR gibt es keine implizite Einschränkung basierend auf den Eingaben. Es gibt spezielle Fälle, in denen Sie feststellen können, dass Sie, wenn Sie ein Byte mit 255 XOR-verknüpfen, das Inverse erhalten, aber jedes mögliche Byte daraus ausgegeben werden kann. Jedes Bit hat die Möglichkeit, den Status abhängig von demselben Bit im anderen Operanden zu ändern.

Corey Ogburn
quelle
6
Man könnte sagen, ORist bitweise max und ANDist bitweise min .
Paŭlo Ebermann
Sehr gut gesagt Paulo Ebermann. Schön, Sie hier sowie Crypto.SE zu sehen!
Corey Ogburn
Ich habe einen Filter erstellt, der alles enthält, was mit Kryptografie markiert ist , und auch Änderungen an alten Fragen. Auf diese Weise habe ich hier Ihre Antwort gefunden.
Paŭlo Ebermann
3

Wenn Sie XOReine zufällige Eingabe mit einer voreingenommenen Eingabe haben, ist die Ausgabe zufällig. Gleiches gilt nicht für ANDoder OR. Beispiel:

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

Wie @Greg Hewgill erwähnt, führt die Verwendung von oder zu einer voreingenommenen Ausgabe , selbst wenn beide Eingaben zufällig sind .ANDOR

Der Grund, warum wir XORetwas Komplexeres verwenden, ist, dass es keine Notwendigkeit gibt: Funktioniert XORperfekt und es ist unglaublich schnell.

BlueRaja - Danny Pflughoeft
quelle
1

Decken Sie die linken 2 Spalten ab und versuchen Sie herauszufinden, welche Eingaben nur die Ausgabe verwenden.

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

Wenn Sie ein 1-Bit gesehen haben, sollten Sie herausgefunden haben, dass beide Eingänge 1 waren.

Machen Sie jetzt dasselbe für XOR

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

XOR gibt nichts über seine Eingaben preis.

Robert
quelle
0

Der Quellcode für verschiedene Versionen von hashCode()in java.util.Arrays ist eine hervorragende Referenz für solide, allgemein verwendete Hashing-Algorithmen. Sie sind leicht zu verstehen und in andere Programmiersprachen zu übersetzen.

Grob gesagt hashCode()folgen die meisten Implementierungen mit mehreren Attributen diesem Muster:

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

Sie können in anderen Fragen und Antworten zu StackOverflow nach weiteren Informationen über die Magie dahinter suchen 31und warum Java-Code sie so häufig verwendet. Es ist nicht perfekt, hat aber sehr gute allgemeine Leistungseigenschaften.

Kevinarpe
quelle
2
Javas Standard-Hash "Mit 31 multiplizieren und addieren / akkumulieren" ist mit Kollisionen geladen (z. B. stringKollisionen mit string + "AA"IIRC), und sie wünschten sich vor langer Zeit, sie hätten diesen Algorithmus nicht in die Spezifikation eingebrannt. Das heißt, die Verwendung einer größeren ungeraden Zahl mit mehr gesetzten Bits und das Hinzufügen von Verschiebungen oder Rotationen behebt dieses Problem. MurmurHash3s 'Mix' macht das.
Scott Carey
0

XOR ignoriert einige Eingaben wie OR und AND manchmal nicht .

Wenn Sie zum Beispiel AND (X, Y) nehmen und die Eingabe X mit false füttern , spielt die Eingabe Y keine Rolle ... und man möchte wahrscheinlich, dass die Eingabe beim Kombinieren von Hashes eine Rolle spielt.

Wenn Sie eine XOR (X, Y) dann BEIDE Eingänge IMMER Angelegenheit. Es würde keinen Wert von X geben, bei dem Y keine Rolle spielt. Wenn entweder X oder Y geändert wird, spiegelt die Ausgabe dies wider.

Sunsetquest
quelle