Ich verstehe, dass nach dem Schubladprinzip, wenn die Anzahl der Artikel größer ist als die Anzahl der Container, dann wird mindestens ein Container mehr als einen Artikel haben. Spielt es eine Rolle, welcher Container es sein wird? Wie gilt das für MD5-, SHA1-, SHA2-Hashes?
Nein, es spielt keine Rolle, welcher Container es ist, und tatsächlich ist dies für kryptografische Hashes nicht so wichtig; viel Wichtiger ist das Geburtstagsparadox , das besagt, dass Sie nur hash sqrt(numberNeededByPigeonHolePrincipal) brauchen. Werte im Durchschnitt vor dem Auffinden einer Kollision.
Daher muss der Hash groß genug sein, dass die Quadratwurzel des Suchraums zu groß für Brute-Force ist. Der Quadratwurzel-Suchraum für SHA1 ist 2 80 , und seit März 2012 wurden noch nie zwei Werte mit demselben SHA1-Hash gefunden (obwohl ich voraussage, dass dies innerhalb von SHA1 passieren wird) das nächste Jahr oder zwei ..); Gleiches gilt für SHA2, eine Familie von Hashes, die alle einen noch größeren Suchraum haben. MD5 wurde jedoch für eine Weile unterbrochen .
Wenn Sie mehr Hash-Elemente als Slots haben, haben Sie Hash-Kollisionen. Aber wenn Sie einen schlechten Hashing-Algorithmus haben, dann werden Sie Kollisionen sehen, selbst wenn das Verhältnis von Items / Slots sehr klein ist. Ein guter Hashalgorithmus (einschließlich der meisten, die Sie in freier Wildbahn sehen werden) wird versuchen, die resultierenden Hashes über den gesamten Ausgabebereich so gleichmäßig wie möglich zu verteilen und somit Kollisionen zu minimieren.
Beachten Sie, dass eine Hash-Kollision nicht das Ende der Welt ist. Wenn es beispielsweise in einer Hash-Tabelle verwendet wird, bedeutet dies nur, dass mehr als ein Element in einem Slot gespeichert ist, und der Tabellencode muss ein wenig mehr durchlaufen, um das Zielelement zu finden oder hinzuzufügen, wodurch die Nachschlagezeit leicht erhöht wird / p>
Sie werden sehen, dass Leute MD5 als "kaputten" Hash-Algorithmus bezeichnen, obwohl es in Wirklichkeit nur ein schlechter als kryptografischer Hashwert ist. Es wird besser sein als du selbst.
Der Sinn einer Hash-Funktion besteht darin, Elemente in Container zu verteilen. Für eine gute Hash-Funktion ist es nicht wichtig, welchen Container es sein soll, denn sie müssen nicht unterscheidbar sein.
Dies gilt nicht für "perfekte Hash" -Implementierungen, die versuchen, besser als Zufallsverteilung - anders als die Algorithmen, die Sie erwähnten.
Wie Michael erwähnt hat, passieren Kollisionen LANGSAM, bevor es so viele Gegenstände wie Slots gibt. Sie müssen eine elegante Kollisionsabfrage (oder einen perfekten Hash) haben, wenn Sie das Geburtstagsparadox bearbeiten möchten.
Ich denke, die Anwendung, für die Sie die Hash-Funktion verwenden, ist eine wichtige Unterscheidung. Häufige Kollisionen in Hash-Containern können beispielsweise die Leistung beeinträchtigen. Häufige Kollisionen in der Kryptographie werden weit verheerende Folgen haben (siehe: kryptografische Hash-Funktion auf Wikipedia ).
Kollision passiert relativ einfach sogar mit einem "anständigen" Hash-Algorithmus. Zum Beispiel in Java,
%Vor% hasht immer auf 0. Das heißt, alle Zeichenfolgen, die nur %code% enthalten, werden in Java auf 0 gesetzt.
Für "ob es wichtig ist, welcher Container wird es sein?", wieder kommt es auf die Anwendung an. Sie können Hash-Funktionen entwerfen, die "ähnliche" Objekte mit ähnlichen Werten versehen. Dies ist nützlich, wenn Sie beispielsweise nach ähnlichen Objekten suchen möchten. Hau sie einfach alle zusammen und sieh, wo sie hinfallen. In diesem Fall sind Kollisionen oder Beinahe-Kollisionen wünschenswert, weil sie ähnliche Objekte gruppiert.
In anderen Anwendungen möchten Sie sogar die geringste Änderung des Objekts zu einem völlig anderen Hash-Wert führen. Dies ist beispielsweise in der Kryptographie der Fall, wo Sie so sicher wie möglich sein wollen, dass etwas nicht verändert wurde. Es ist viel schwieriger, verschiedene Objekte zu finden, die in diesem Fall auf den gleichen Wert getastet werden.
Abhängig von Ihrer Anwendung sind kryptografische Hashes wie MDA, SHA1 / 2 usw. möglicherweise nicht die ideale Wahl, gerade weil sie wie zufällig erscheinen und Ihnen Kollisionen geben, wie sie vom Geburtstagsparadox vorhergesagt werden. Herkömmlicherweise besteht ein Grund für die Verwendung einfacher Hashwerte auf der Basis der Restoperation darin, dass von Schlüsseln erwartet wurde, dass sie Seriennummern oder Ähnliches sind, so dass eine Restoperation weniger Kollisionen ertragen würde, als zufällig erwartet. Z.B. Wenn die Schlüssel die Ganzzahlen 1..1000 sind, könnten Sie in einem Container der Größe 1009 überhaupt keine Kollisionen haben, wenn Ihre Hash-Funktion der Schlüssel mod 1009 ist. Manchmal würden Menschen Systeme manuell abstimmen, indem sie Containergröße und Hash-Funktion sorgfältig auswählen eine gleichmäßige Aufteilung erreichen.
Natürlich müssen Sie sich Sorgen darüber machen, ob Sie böswillig Schlüssel auswählen, die Ihnen Schwierigkeiten bereiten, oder ein vorgelagertes System, das Ihnen sehr voreingestellte Schlüssel sendet (weil es z. B. eine eigene Hash-Tabelle hat und alle Schlüssel mit X verschlüsselt) auf einmal). Vielleicht möchten Sie einen Hash verwenden, der auf einer kryptographischen Verschlüsselungsfunktion basiert, um sich dagegen zu wehren.