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

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