Ich verwende derzeit eine SHA1, um eine URL etwas zu verkürzen:
%Vor%Wie sicher ist es, nur die ersten 8 Zeichen des SHA1 als eindeutigen Bezeichner zu verwenden, wie es GitHub anscheinend tut?
Um die Wahrscheinlichkeit einer Kollision mit einer gegebenen Länge und die Anzahl der Hashes zu berechnen, lesen Sie das Geburtstagsproblem . Ich kenne nicht die Anzahl der Hashes, die Sie haben werden, aber hier sind einige Beispiele. 8 hexadezimale Zeichen sind 32 Bits, also für ungefähr 100 Hashes ist die Wahrscheinlichkeit einer Kollision ungefähr 1 / 1.000.000, für 10.000 Hashes ist es ungefähr 1/100, für 100.000 ist es 3/4 usw.
Sehen Sie sich die Tabelle im Geburtstagsangriff Artikel auf Wikipedia an, um eine gute Hash-Länge zu finden, die Ihren Bedürfnissen entspricht . Wenn zum Beispiel die Kollision weniger wahrscheinlich als 1 / 1.000.000.000 für einen Satz von mehr als 100.000 Hashes sein soll, dann verwenden Sie 64 Bits oder 16 hexadezimale Ziffern.
Es hängt alles davon ab, wie viele Hashes Sie haben werden und welche Wahrscheinlichkeit einer Kollision Sie bereit sind zu akzeptieren (weil es immer eine Wahrscheinlichkeit gibt, auch wenn sie wahnsinnig klein ist).
Wenn Sie von einem hexadezimalen SHA-1 sprechen, erhalten Sie nur 4 Bits pro Zeichen, also insgesamt 32 Bits. Die Wahrscheinlichkeit einer Kollision ist umgekehrt proportional zur Quadratwurzel dieses Maximalwerts, also etwa 1/65536. Wenn Ihr URL-Kürzler viel benutzt wird, wird es wahrscheinlich nicht lange dauern, bis Sie Kollisionen sehen.
Was Alternativen anbelangt, ist das offensichtlichste wahrscheinlich, nur einen Zähler zu warten. Da Sie eine Tabelle mit URLs speichern müssen, um Ihre verkürzte URL zurück in das Original zu übersetzen, speichern Sie einfach jede neue URL in Ihrer Tabelle. Wenn es bereits vorhanden war, geben Sie seine vorhandene Nummer an. Andernfalls fügen Sie es ein und geben ihm eine neue Nummer. In beiden Fällen geben Sie diese Nummer an den Benutzer.
Es hängt davon ab, was Sie erreichen wollen. Die Ausgabe von SHA1 ist in Bezug auf die Eingabe effektiv zufällig (die Ausgabe einer guten Hash-Funktion ändert sich in der Hälfte ihrer Bits basierend auf einer Ein-Bit-Änderung der Eingabe, und SHA1 ist zwar nicht perfekt, ist aber ziemlich gut) und Indem Sie eine 32-Bit-Untermenge der 160-Bit-Ausgabe (unter Annahme von 8 Hex-Stellen) verwenden, reduzieren Sie den Ausgabebereich von 2 ^ 160 auf 2 ^ 32 Werte. Wenn alle Dinge gleich sind, was sie niemals sind, würde dies die Schwierigkeit, eine Kollision zu finden, erheblich reduzieren.
Wenn die Eingabe der Hash-Funktion jedoch eine gültige URL sein muss, reduziert dies die Anzahl der möglichen Eingaben erheblich. @rsp weist auf das Geburtstagsproblem hin, aber angesichts dessen bin ich mir nicht sicher, ob es zumindest in seiner einfachen Form anwendbar ist. Außerdem geht es weitgehend davon aus, dass keine anderen Vorkehrungen vorhanden sind.
Ich wäre mehr daran interessiert, warum Sie das tun. Sind das URLs, die der Benutzer merken und eingeben muss? Wenn das der Fall ist, ist es wahrscheinlich eine schlechte Idee, eine Reihe zufälliger hexadezimaler Ziffern anzuheften. Ist es ein URL- oder URL-Parameter, der nur programmgesteuert weitergegeben wird? Dann würde mich die Länge nicht interessieren. In jedem Fall gibt es wahrscheinlich bessere Möglichkeiten, um das zu erreichen, was Sie erreichen möchten.
Wenn Sie eine binäre Ausgabe für SHA1 und Base64 für das Ergebnis verwenden, werden Sie dies tun eine viel höhere Informationsdichte pro Zeichen erhalten; Sie können die gleichen achtstelligen Namen haben, aber statt nur 16^8 ( 2^32 ) Möglichkeiten, haben Sie 64^8 ( 2^48 ) Möglichkeiten.
Unter der Annahme, dass die 50% -Wahrscheinlichkeit der Kollision mit 1.177 * sqrt (N) skaliert, Bei Verwendung einer Codierung im Base64-Stil werden 256 Mal mehr Eingaben benötigt als bei der Hex-Ausgabe, bevor die Wahrscheinlichkeit von 50% der Kollisionswahrscheinlichkeit erreicht wird.