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

[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.

[Benmik]

Zitat von Stevie:

FWIW xxh32 gibt's auch als native Implementierung in Spring4D (natürlich für Windows in asm implementiert, somit durchaus vergleichbare Performance).Ist seit 2.0 die Standard Hashfunktion für Dictionary und Co

Ich habe mal Spring.Hash und XXHASH verglichen (1.400 Dateien, 14,3 GB); Letzteres hat ja auch eine 64 Bit-Implementierung. Spring.Hash und HashXXH32 waren genau gleich schnell, HashXXH64 jedoch spürbar (20% - 25%) schneller. Erstaunlich. Das ASM bringt offenbar gar nichts.

Hat denn das MD5 beim Dateivergleich überhaupt eine Existenzberechtigung? Es ist ja offenbar unfassbar langsam.

[Rollo62]

Zitat von Benmik:

Hat denn das MD5 beim Dateivergleich überhaupt eine Existenzberechtigung?

Es ist halt einfach überall bereits verfügbar und jahrzehnte lang ausgetestet, gefühlt von 8-Bit MCU bis der neuesten Intel/AMD Generation.

[Benmik]

Das erscheint mir als ein schwieriges Argument. Das Bessere ist der Feind des Guten. Joey Lynch hat 2021 auf Github den Artikel Use Fast Data Algorithms publiziert. Dort ist xxHash um den Faktor 10 schneller als MD5; Letzteres charakterisiert er als "This hash is both weak and slow. It does have the advantage of being one of the fastest slow choices in standard libraries and therefore it is somewhat common." Er rubriziert MD5 auch unter Untrusted Data Hashes und meint: "It’s slow and not resistant to collisions..."

Ich habe das bei mir mal nachgeprüft (wie Lynch empfiehlt) und Faktor 10 war noch untertrieben. xxHash ist augenscheinlich sehr etabliert und da sehe ich für MD5 - jedenfalls für mich - keine Berechtigung mehr. Ich meine, Faktor 10 bei einem ohnehin schon zeitaufwändigen Prozess ... ?