Es wurde ja schon alles relevante gesagt, aber trotzdem mal in komprimierter Form
1.) mit Hash's ermittelt man ob zwei gehashte Dateien gleich sein könnten, zu 100% sicher kann man sich aber erst sein wenn man sie binär Bit für Bit vergleicht
2.) da man also im Worstcase Bit für Bit zwei Dateien vergleichen muß wäre es dumpfsinnig NICHT die Dateigrößen auf Gleichheit als Indiz zu benutzen. Ergo: die Dateigröße sollte als erstes und primäres Unterscheidungsmerkmal herangezugen werden.
3.) der Performance Vorteil ergibt sich aus dem Arbeitsaufwand. Zuerst vergleicht man jeweils 32Bit mit 32Bit Dateigröße. Falls dort Gleichheit herrschen sollte vergleicht man 128Bit mit 128Bit Hashwert. Und erst bei Gleichheit vergleicht man nun die Dateien Bit für Bit. Das macht also 1/(2^32 * 2^128)=(1/2^160) an Trefferquote das man zwei Dateien auch wirklich binär vergleichen muß. Versuche mal 1/2^160 auszurechnen und überlege dir wie lange es dauert einen 160Bit Zähler der in die Sekunde 256 mal inkrementiert wird zum überlaufen zu bringen. (2^260 / 2^8) = 2^152 Sekunden ~ 180000000000000000000000000000000000000 Jahre !!) Man sieht das 160 Bit = 2^160 eine enorm große Zahl darstellt und somit die Wahrscheinlichkeit für zwei gleiche Hashwerte zu unterschiedlichen Dateien in der Realität sehr sehr gering sein wird, aber eben nicht unmöglich ist. In fakt gibt es theoretisch Unendlich-(2^160) viele Dateien die alle den gleichen Hashwert erzeugen müssen. Davon sind aber fast Undenlich viele Dateien unendliche Bits groß. D.h. die größte Masse an Dateien mit gleichem Hashwert sind so rießig groß das sie auf keinen Rechner gespeichert werden können.
4.) die so gesammelten Dateigrößen + Hashwerte sollten in einer datenbank sortiert gespeichert werden. Bei sagen wir mal 1024 so gesammelten Dateien in der
DB benötigt man im Worstcase nur 12 Vergleiche von Dateigrößen + Hashwerten
5.) der Hashwert wird über die komplette Datei gezogen, NICHT nur über die ersten Bytes der Datei
6.) Da der hashwert nur 128 oder 256 Bits groß ist bedeutet das das zb. mit 1Mb großen Dateien exakt 2^(1Mb-256) Dateien gibt die den gleichen Hashwert erzeugen aber binär komplett unterschiedlich sind. Der Hash einer Datei, wie auch jede andere Prüfsumme ist also kein eineindeutiges Indiz für den Vergleich auf Gleichheit ! Sondern eher nur ein Indiz für Ungleichheit wenn die Hashwerte sich unterscheiden. Um so wichtiger ist es das man über die komplette Datei hasht.
7.) somit garantiert eine Hashfunktion das sie einen anderen Wert erzeugt wenn die Datei sich nur um 1 Bit unterscheidet. Sie garantiert aber nicht das zwei gleiche Hashwerte auch zweimal die gleiche Datei darstellt.
8.) Performancetechnisch sind die Hashfunktionen heutzutage schneller als jede Form eines direkten Binären Vergleiches. D.h. die Benutzung einer Hashfunktion ist absolut richtig wenn man einen performanten Vergleich erzielen möchte. Denn man produziert von einer neuen Datei nur einmal den Hash und vergleicht diesen dann mit 1000'enden anderen Hashwerten + Dateigrößen in der Datenbank. Das ist bei weitem viel weniger an Speicherzugriffen als alle diese Dateien binär bit für bit mit der neuen Datei zu vergleichen.
9.) ein 256Bit Algo. hat zwar viel weniger Redundanz als ein 128 Bit Algo, dafür sind die 256 Bit Algos durch die Bank weg aber auch langsammer, die Hashwerte benötigen 2x mehr an Speicherplatz und die Wahrscheinlichkeiten für Kollisionen mit unseren heutigen Dateien ist aber nicht um 2^128 vergleichbar größer. Ich würde also für so eine Aufgabe absolut den 128Bit MD4 Algo empfehlen. Er ist immer noch der schnellste seiner Art.
10.) bei einer solchen Aufgabe ist es wichtig sich darüber zu informieren wie die Wahrscheinlichkeiten der unterschiedlich auftretenden Dateien verteilen. Beispiel: in der
DB sind 65535 Dateien gespeichert. Davon werden maximal aber nur 1-2 % auch die gleiche Dateigröße besitzen und davon hat KEINE den gleichen Hashwert. Wird nun eine neue Datei eingefügt so wird diese mit max. 1-2% der gespeicherten Dateigrößen übereinstimmmen und von diesen 2% wird mit sehr sehr geringer Wahscheinlichkeit 1 Datensatz den gleichen Hashwert besitzen.
Mit einer 128 Bit Hashfunktion kann man mal unsauber eine Pi*Daumen Abschätzung machen -> falls 2^128 Datensätze, also 2^128 verschiedene Dateien in der
DB gespeichert würden so ist die wahrscheinlichkeit 100/(2^32) Prozent das man 1 Datensatz findet der mit dem neuen Datensatz übereinstimmen wird. Die 2^32 ist die Dateigröße die ebenfalls berücksichtigt werden sollte. Für diese riesige Datenbank von 2^128 Dateien heist dies das das Program sich eher auf eine hoch optimierte Datenbanksuche konzentrieren sollte da der eigentliche Dateivergleich sich in der Gesamtperformance fast garnicht auswirken wird.
Fazit: nehme MD4 mit 128Bit Hashwerten + Dateigröße in
DB auf. Konzentriere dich darauf die richtige "Datenbank" zu finden statt sich mit der "besten" Hashfunktion Zeit zu vergeuden. In der Gesamtperformance wird es garantiert nicht die Hashfunktion sein die die meiste Zeit verbrauchen wird, eher die Suche in der
DB.
Gruß Hagen