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.)?
cryptography
bit-manipulation
hash
probability
xor
Nate Murray
quelle
quelle
Antworten:
Unter der Annahme gleichmäßig gleichmäßiger (1-Bit) Eingaben beträgt die Wahrscheinlichkeitsverteilung der UND-Funktionsausgabe 75%
0
und 25%1
. Umgekehrt beträgt OR 25%0
und 75%1
.Die XOR-Funktion beträgt 50%
0
und 50%1
, daher eignet sie sich gut zum Kombinieren gleichmäßiger Wahrscheinlichkeitsverteilungen.Dies kann durch Ausschreiben von Wahrheitstabellen gesehen werden:
Aufgabe: Wie viele logische Funktionen von zwei 1-Bit-Eingängen
a
undb
diese gleichmäßige Ausgangsverteilung? Warum ist XOR für den in Ihrer Frage angegebenen Zweck am besten geeignet?quelle
(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 == b
dh das Gegenteil von XOR (EQUIV) hätte auch verwendet werden können ...a, b, !a, !b
die 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.(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.xor
ist eine gefährliche Standardfunktion, die beim Hashing verwendet wird. Es ist besser alsand
undor
, aber das sagt nicht viel.xor
ist 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
xor
es 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 derxor
des 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 alshash(a) xor hash(b)
wenna==b
, wenn das Ergebnishash(a)<<1
statt 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:aka
hash(a)*3 + hash(b)
. (Einmaliges Berechnenhash(a)
und Speichern wird empfohlen, wenn Sie die Schichtlösung verwenden). Jede ungerade Konstante anstelle von3
wird einek
vorzeichenlose Ganzzahl mit " -bit" bijektiv auf sich selbst abbilden, da die Zuordnung auf vorzeichenlosen Ganzzahlen2^k
für einige mathematisch modulok
ist und jede ungerade Konstante relativ prim ist2^k
.Für eine noch schickere Version können wir untersuchen
boost::hash_combine
, was effektiv ist:Hier addieren wir einige verschobene Versionen von
seed
mit einer Konstanten (die im Grunde genommen zufällige0
s und1
s 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 gut1
und erzeugt0
nach jedem Mähdrescher einen Abstrich von und s. Meine Naivität3*hash(a)+hash(b)
gibt einfach ein0
In aus dieser Fall).(Für diejenigen, die mit C / C ++ nicht vertraut sind,
size_t
ist 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.)quelle
0x9e3779b9
.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.
quelle
long
und dann den oberen Teil wieder mit dem unteren Teil zu verbinden.m = 3
ist eigentlich eine gute Wahl und auf vielen Systemen sehr schnell. Beachten Sie, dass für jede ungeradem
Ganzzahl die Multiplikation modulo2^32
oder2^64
daher invertierbar ist, damit Sie keine Bits verlieren.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!
quelle
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.
quelle
OR
ist bitweise max undAND
ist bitweise min .Wenn Sie
XOR
eine zufällige Eingabe mit einer voreingenommenen Eingabe haben, ist die Ausgabe zufällig. Gleiches gilt nicht fürAND
oderOR
. Beispiel:Wie @Greg Hewgill erwähnt, führt die Verwendung von oder zu einer voreingenommenen Ausgabe , selbst wenn beide Eingaben zufällig sind .
AND
OR
Der Grund, warum wir
XOR
etwas Komplexeres verwenden, ist, dass es keine Notwendigkeit gibt: FunktioniertXOR
perfekt und es ist unglaublich schnell.quelle
Decken Sie die linken 2 Spalten ab und versuchen Sie herauszufinden, welche Eingaben nur die Ausgabe verwenden.
Wenn Sie ein 1-Bit gesehen haben, sollten Sie herausgefunden haben, dass beide Eingänge 1 waren.
Machen Sie jetzt dasselbe für XOR
XOR gibt nichts über seine Eingaben preis.
quelle
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:Sie können in anderen Fragen und Antworten zu StackOverflow nach weiteren Informationen über die Magie dahinter suchen
31
und warum Java-Code sie so häufig verwendet. Es ist nicht perfekt, hat aber sehr gute allgemeine Leistungseigenschaften.quelle
string
Kollisionen mitstring + "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.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.
quelle