Optimaler Hash-Algorithmus und Strategie für Dateivergleiche, Verzeichnisbaum

[himitsu]

Zitat:

Das ist eine sehr kleine Wahrscheinlichkeit, aber es ist nicht null

Egal welcher Hash, Kollisionen sind theoretisch immer vorhanden, so lange der Hash kleiner ist, als die Datei.
Selbst wenn der Hash gleich groß wäre, wie die Datei, gäbe es theoretisch immernoch Kollisionen, da ja der Hash einen anderen Wert berechnet, wie die Ursprungsdaten und somit kann ebenfalls bei unterschiedlichen Dateien der Selbe hash entstehen.

Was also bei den Hashs den Unterschied macht, ist wie groß er ist, je größer um so unwahrscheinlicher,
und je besser die Berechnung ist, um unwahrscheinlicher.



Billigster Hash, es werden einfach nur die Bytes in den Speicher geschoben, ohne Rückführung des Überlaufs, dann hat ein 32 Bit Hash schon ab einer Datei von 5 Byte Größe garantiert im ersten Byte alle Kollisionen drin, da immer nur die letzten 4 Byte zählen.

[Michael II]

Zitat von himitsu:

Selbst wenn der Hash gleich groß wäre, wie die Datei, gäbe es theoretisch immer noch Kollisionen, da ja der Hash einen anderen Wert berechnet, wie die Ursprungsdaten und somit kann ebenfalls bei

In diesem Fall sind Kollisionen nicht nur "theoretisch möglich": Für alle möglichen Dateien maximaler Länge n und n Bit Hash gibt es immer mindestens 2^n-1 Kollisionen.
(Es gibt eine Datei mit Länge 0, 2 Dateien mit Länge 1... also insgesamt 2^n-1 voneinander verschiedene Dateien mit maximaler Länge n-1. Wenn der n Bit Hash für all diese Dateien zu keiner Kollision führt, dann spätestens dann, wenn du zwei voneinander verschiedene Dateien der Länge n auswertest.)

[himitsu]

Es war ein vereinfachtes Beispiel, wo die meisten Kollisionen in einen definierten Bereich verschoben wurden, an der Anzahl ändert sich nicht viel, selbst wenn er besser rechnet.

Schlecht rechnen:
* wenn ein Hash bereits bei gleichgroßem Eingang zu viele Kollisionen aufweist, dann wird es noch schlimmer. (z.B. wenn er immer nur ungerade Hashs ausspuckt, dann hast'e bereits 50% Ausfall, also bei CRC32 so, als hätte er nur 31 Bit)
* und dazu kommen noch garantierte die Kollisionen mit kürzeren Eingängen, bei CRC32 also 0, 1, 2 oder 3 Byte große Daten.



Selbst bei einem Hash mit 512 Bit, gibt es garantiert enorm viele Kollisionen, spätestens bei mehr als 64 Byte.
Bei 68 Byte hast du da auch schon durchschnittlich 4 Milliarden Kollisionen pro Hash, also insgesamt mindestens 2,4^173.
Drum hatte sich mein SerarchSameFiles nicht nur auf Hashs verlassen, sondern bei gleichen Hashs auch nochmal die kompletten Dateien verglichen.

Es kommt nur drauf an, wie gut der Hash rechnet und wir wahrscheinlich es ist, dass wirklich einer dieser Fälle getroffen wird.
Bei reinen Textdateien/XML/JSON fällt schonmal Vielles weg und wenn auch noch was "sinnvolles" in den Dateien steht, nochmal ein enorm großer Anteil.