Warum erzeugt der Hash-Codes, der von dieser Funktion nicht eindeutig?
https://stackoverflow.com/questions/63897
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich teste die VB-Funktion unten, dass ich von einer Google-Suche bekam. Ich plane, es zu benutzen Hash-Codes für die schnellen String-Vergleich zu erzeugen. Es gibt jedoch Fälle, in denen zwei verschiedene Strings den gleichen Hash-Code haben. Zum Beispiel können diese Strings
"122Gen 1 Heap-Größe (.NET CLR-Speicher w3wp): mccsmtpteweb025.20833333333333E-02"
"122Gen 2 Heap-Größe (.NET CLR-Speicher w3wp): mccsmtpteweb015.20833333333333E-02"
hat den gleichen Hash-Code von 237.117.279.
Bitte sagen Sie mir: - Was ist mit der Funktion falsch? - Wie kann ich es beheben
?Danke
martin
Private Declare Sub CopyMemory Lib "kernel32" Alias "RtlMoveMemory" (dest As Any, src As Any, ByVal bytes As Long)
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor codes(i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
Lösung
Ich wette es gibt mehr als nur „Gelegenheiten“, wenn zwei Strings den gleichen Hash mit Ihrer Funktion erzeugen. In der Tat kommt es wahrscheinlich öfter, als Sie denken.
Ein paar Dinge zu erkennen:
Als erstes wird es Hash-Kollisionen. Es passiert. Selbst bei wirklich, wirklich große Räume wie MD5 (128 Bit) gibt es noch zwei Saiten, die die gleiche resultierende Hash erzeugen kann. Sie haben durch die Schaffung von Eimern mit diesen Kollisionen zu behandeln.
Zweitens ist eine lange Ganzzahl ist nicht wirklich ein großer Hash-Raum. Du wirst mehr Kollisionen bekommen, als würden Sie, wenn Sie mehr Bits verwendet wird.
Drittens gibt es Bibliotheken in Visual Basic zur Verfügung (wie .NET des System.Security.Cryptography Namespace), die eine viel bessere Arbeit des Hashing als die meisten Sterblichen tun.
Andere Tipps
Die beiden Strings haben die gleichen Zeichen. (Man beachte die '2' und die '1', die Flip-Flop)
Deshalb ist der Hash-Wert gleich ist.
Stellen Sie sicher, dass die Hash-Funktion in Betracht nimmt die Reihenfolge der Zeichen.
Hash-Funktionen garantieren nicht Einzigartigkeit von Hash-Werten. Wenn der Eingangswertebereich (Beurteilung Saiten Probe) größer ist als der Ausgangswertebereich (zB 32-Bit-Integer), dann Einzigartigkeit ist physikalisch unmöglich.
Wenn das größte Problem ist, dass es nicht für die Position des Bytes nicht berücksichtigen, könnten Sie es wie dieses Problem zu beheben:
Private Function HashCode(Key As String) As Long
On Error GoTo ErrorGoTo
Dim lastEl As Long, i As Long
' copy ansi codes into an array of long'
lastEl = (Len(Key) - 1) \ 4
ReDim codes(lastEl) As Long
' this also converts from Unicode to ANSI'
CopyMemory codes(0), ByVal Key, Len(Key)
' XOR the ANSI codes of all characters'
For i = 0 To lastEl - 1
HashCode = HashCode Xor (codes(i) + i) 'Xor'
Next
ErrorGoTo:
Exit Function
End Function
Der einzige Unterschied ist, dass sie die Zeichen Position, um es der Byte-Wert vor dem XOR hinzufügt.
Keine Hash-Funktion kann Einzigartigkeit garantieren. Es gibt ~ 4000000000 32-Bit-Integer, so dass selbst die beste Hash-Funktion wird Duplikate erzeugen, wenn sie mit ~ 4 Milliarden und 1 Zöpfen (und meistens wahrscheinlich lange vor).
Der Umzug in 64-Bit-Hash-Werten oder sogar 128-Bit-Hash-Wert ist die Lösung nicht wirklich, obwohl es die Wahrscheinlichkeit einer Kollision reduziert.
Wenn Sie eine bessere Hash-Funktion wollen Sie an dem kryptographischen Hashes aussehen könnten, aber es wäre besser, Sie Algorithmus zu überdenken und entscheiden, ob Sie mit den Kollisionen eine andere Art und Weise umgehen können.
Die System.Security.Cryptography Namespace mehrere Klassen enthält, die für Sie Hashing können (wie zum Beispiel MD5 ), die sie wahrscheinlich Hash besser als Sie selbst konnte und viel weniger Aufwand.
Sie müssen nicht immer das Rad neu zu erfinden.
Einfache XOR ist eine schlechte Hash: Sie viele Zeichenketten finden, die kollidieren. Der Hash hängt nicht von der Reihenfolge der Buchstaben in der Zeichenkette, für eine Sache.
Versuchen Sie, die FNV Hash mit http://isthe.com/chongo/tech/comp / FNV /
Das ist wirklich einfach zu implementieren. Es verschiebt den Hash-Code nach jeder XOR, so dass die gleichen Buchstaben in einer anderen Reihenfolge einen anderen Hash erzeugen.
Hash-Funktionen werden nicht zurück unterschiedliche Werte für unterschiedliche Strings gemeint. Allerdings sollte eine gute Hash-Funktion unterschiedliche Werte für Zeichenketten zurück, die gleich aussehen. Hash-Funktionen verwendet werden, aus vielen Gründen zu suchen, einschließlich in eine große Sammlung zu suchen. Wenn die Hash-Funktion ist gut, und wenn sie Werte aus dem Bereich [0, N-1] liefert, dann wird eine große Sammlung von M Objekten wird divide in N Sammlungen sein, die jeweils mit etwa M / N-Elementen. Auf diese Weise müssen Sie nur in einer Anordnung von M / N Elemente anstelle des Suchens in einer Reihe von M Elementen suchen.
Aber, wenn Sie nur zwei Saiten haben, ist es nicht schneller den Hash-Wert für diejenigen zu berechnen! Es ist besser , um nur die beiden Strings zu vergleichen.
Eine interresing Hash-Funktion könnte sein:
unsigned int hash(const char* name) {
unsigned mul=1;
unsigned val=0;
while(name[0]!=0) {
val+=mul*((unsigned)name[0]);
mul*=7; //you could use an arbitrary prime number, but test the hash dispersion afterwards
name++;
}
return val;
}
Ich reparierte die Syntax für ihn hervorheben.
Auch für diejenigen, die nicht sicher für die Umwelt waren oder waren vermutlich eine sichere Hash: es ist Classic (pre-.Net) VB, weil .Net Klammern für den Aufruf von Copymemory erfordern würde.
IIRC, es gibt keine sicheren Hash-Werte für Classic VB eingebaut. Es gibt nicht viel da draußen auf dem Netz entweder, so kann dies seine beste Wette.
Ich verstehe nicht ganz die Umwelt sehen Sie in Arbeit. Ist der .NET-Code? Wenn Sie wirklich gute Hash-Codes wollen, würde ich Blick in kryptographischen Hashes empfehlen (bewährte Algorithmen) anstatt zu versuchen, Ihre eigenen zu schreiben.
Btw, könnten Sie Ihre Post bearbeiten und den Code in einfügen als ein Code-Beispiel (siehe Symbolleiste)? Dies würde es leichter zu lesen.
„Tu das nicht.“
Ihre eigene Hash-Funktion zu schreiben, ist ein großer Fehler, weil Sie Ihre Sprache sicherlich bereits eine Implementierung von SHA-1 hat, die eine ganz gute Hash-Funktion ist. Wenn Sie nur 32 Bits benötigen (statt der 160, SHA-1 zur Verfügung stellt), verwenden Sie nur die letzten 32 Bits von SHA-1.
Diese besondere Hash-Funktionen XORs alle Zeichen in einer Zeichenkette. Leider XOR ist assoziativ:
(a XOR b) XOR c = a XOR (b XOR c)
So Strings, mit den gleichen Eingabezeichen wird in dem gleichen Hash-Code zur Folge hat. Die beiden Saiten versehen sind gleich, mit Ausnahme der Lage von zwei Zeichen, deshalb sollten sie den gleichen Hash-Code haben.
Sie müssen möglicherweise einen besseren Algorithmus finden, würde MD5 eine gute Wahl sein.
Die XOR-Operation ist kommutativ; das heißt, wenn in einem String alle Zeichen XOR-Verknüpfung, die Reihenfolge der Zeichen keine Rolle spielt. Alle Anagramme eines Strings die gleiche XOR Hash erzeugen.
In Ihrem Beispiel Ihre zweite Zeichenfolge kann von Ihrem ersten erzeugt werden, indem die „1“ nach „... Genen“ mit den ersten ‚2‘ es folgendem Swapping.
Es ist nichts falsch mit Ihrer Funktion. Alle nützlichen Hashing-Funktionen werden manchmal Kollisionen erzeugen, und Ihr Programm muß bereit sein, sich zu lösen.
Eine Kollision tritt auf, wenn ein Eingang auf einen Wert Hashes bereits mit einer früheren Eingabe identifiziert. Wenn ein Hash-Algorithmus nicht Kollisionen erzeugen könnte, müßten die Hash-Werte so groß wie die Eingangswerte. Ein solcher Hash-Algorithmus von begrenztem Nutzen im Vergleich zu nur das Speichern der Eingabewerte sein würde.
-Al.
Es gibt eine Visual Basic-Implementierung von MD5-Hashing hier
