C++ Schneller Hash-Algo für große Dateien

[hanussen]

Hallo,

wie kann ich große Dateien schnell und einfach unabhängig ihres Namens identifizieren. Die Größe alleine ist beinahe einmalig, allerdings möchte ich auf Nummer sicher gehen und noch einen HASH generieren.

MD5 und SHAx kommen nicht in Frage da sie einfach VIEL zu langsam sind.

Schon alleine alle Daten der Datei anzuschauen wäre viel zu Zeitaufwendig, also muss ich irgendwie ein bisschen drin herumstochern um daraus einen möglichst eindeutigen Schlüssel zu generieren.

Möglichst eindeutig da ich ja noch die feste Größe der Datei habe... selbst wenn der Hash-Algorithmus nicht vollständig kollisionsfrei sein sollte tut er noch.


Danke schon mal im Voraus.

MfG Hanussen

 

[AppLeYArD]

da hash ja nicht wirklich eindeutig sein muss sondern einfach nur die Ergebnismenge sehr sehr stark eingrenzt wäre die Größe nach deiner Aussage eine schön performante Variante... und danach wird dann ja normalerweise der Gleichheitsvergleich ausgeführt..

 

[1668mib]

Du könntest z.B. ja nur Teile der Dateien "vergeichen" (Hash-Berechnung auf Teile begrenzen, z.B. erstes Megabyte, oder Ende, oder evtl auch immer nur die ersten 4 KB eines 1 MB-Blocks) - abhängig davon, inwiefern du die Dateien erwartest, unterschiedlich zu sein.
Aber eine 100%ige Scherheit hättest damit nicht.

 

[Firestorm-]

Geht es dir konkret um das ablegen von großen Datenmengen und das schnelle Wiederfinden?

Wenn ja, dann bietet sich in deinem Fall möglicherweise eine Variante des Chained Hashing an. Du erzeugst mit einer geigneten Hashfunktion einen Index, an dem dein Objekt ablegegt wird. Das Array sollte in diesem Fall nur so groß sein wie in etwa eine Primzahl in der Nähe der Anzahl an Objekten die im Array abgelegt werden sollen, eher ein bisschen kleiner.

Dann würde sich z.b. eine Hashfunktion a la H(x) = n % 97 anbieten ( Bei einer ungefähren Arraygröße von 50 bis 75), wobei n eine aufsteigend vergebene Zahl in deinem Objekt sein könnte. Je nach Zahl wird dann der Index berechnet auf dem das Objekt abgelegt wird. Wenn es Kollisionen gibt, dann wird beispielweise eine einfach verkettete Liste als Überlaufspeicher genutzt, welcher dann bei der Suche Schritt für Schritt abgearbeitet wird und verglichen wird. Rein von der Komplexität kann es hier im schlimmsten Fall O(n) sein, aber das ist nicht weiter schlimm, wenn die Arraygröße dementsprechend gut gewählt wird.
Dadurch entstehen keine langen Überlaufspeicher und du findest deine Daten rel. schnell wieder.

 

[1668mib]

@Firestorm: Es geht ihm darum dass seine Hash-Funktion schnell sein sollte.
Es geht ihm nicht um Zugriff auf eine Hash-Tabelle...

 

[Firestorm-]

Im Best-Case hast du immer noch konstante Komplexität, schneller gehts nicht!
Im Worst-Case eben O(n), aber wie gesagt, mit einer entsprechenden Länge des Arrays, kein Thema.

@1668mib: Hast du meinen Post ganz gelesen oder nur die erste Zeile? 0o

 

[1668mib]

Hast du das Problem gelesen?
Es geht hier nicht um die Verwendung von Hash-Tabellen, sondern um die Generierung eines Hash-Wertes von großen Dateien, was bei einer großen Datei durchaus einige Minuten gehen kann, wenn man z.B. SHA1 oder MD5 nimmt.

Es geht um die Generierung eines möglichst eindeutigen Schlüssels, wie es MD5 und SHA1 eigentlich machen. Wie generierst du den Schlüssel in deiner Erklärung?

 

[Firestorm-]

Was spricht gegen eine selbst geschriebene Hashfunktion? Man muss mit dem Wert ja keine Array bedienen.

 

[XunnD]

-Um welche Dateigrößen geht es konkret?
-Wie berechnest Du gerade die Prüfsumme? (gib das Codebeispiel an, wo der Hash generiert wird)
-Wie wird konkret die Datei eingelesen, wie wird MD5 angewandt? (Code-Auszug)

Mein Verdacht ist nämlich, dass die E/A-Routine zu langsam ist und nicht der Algorithmus.

 

[1668mib]

@Firestorm-:
Heureka! Genau darum geht es doch.
Was hat die Hash-Funktion aber mit Chained Hashing?
Es geht eben genau um die geeignete Hashfunktion, die fehlt, die wird gesucht.


@XunnD: Richtig. Natürlich ist die E/A das Problem. Deshalb könnte man (bzw habe ich ^^) überlegen, ob sich eben die zu hashenden Teile der Dateien begrenzen lassen...

 

[XunnD]

Welche Implementierung von MD5 wird denn genutzt? Die Referenzimplementierung in C oder eine aus irgendeiner Library?

 

[Firestorm-]

Eine Datei "identifizieren" so wie es im Eingangsposting geschrieben wurde kann man nunmal auf mehrere Arten deuten.

 

[1668mib]

MD5 und SHAx kommen nicht in Frage da sie einfach VIEL zu langsam sind.

Schon alleine alle Daten der Datei anzuschauen wäre viel zu Zeitaufwendig, also muss ich irgendwie ein bisschen drin herumstochern um daraus einen möglichst eindeutigen Schlüssel zu generieren

Ich weiß nicht was man daraus anderes interpretieren sollte...

 

[XunnD]

Es geht mir nur darum: wenn man Byte für Byte einliest und dann MD5 anwendet ist das klar, dass das lange dauert - daran ist dann aber nicht MD5 Schuld, sondern die E/A-Routine.


Ich hab übrigens gerade mal in meinem Ubuntu 8.04 LTS md5sum ausgeführt:
20MB in unter 1 Sekunde auf einem 1.4GHz Centrino (Single-Core), 512MB DDR1, Ubuntu 8.04 und einer Festplatte mit 5.400U/min (mehr als 80% Speicher sind belegt).

Wenn Du für kleinere Dateien bereits mehr Zeit brauchst, dann ist Deine E/A-Routine auf jeden Fall der Flaschenhals.

 

[hanussen]

Mir geht es nur darum in einer Datenbasis (xml, xls, esql,.. wie auch immer) spezifische benutzerdefinierte Attribute zu den Dateien zu hinterlegen.

Diese Dateien werden gerne zwischen den Ordnern hin- und hergeschoben und ggf. auch umbenannt...

Nun soll das Programm alle Ordner durchsuchen, in der Datenbasis nachschauen um welche Datei es sich handelt und eine Liste samt der hinterlegten Attribute erstellen nach denen man dann filtern/sortieren kann.

Wir reden nicht von ein paar MB. Die Archive sind ein paar GB groß. Als ich im Zuge des Windows7-RC vom Microsoft-Image den SHA1-Hash berechnet habe, ärgerte ich mich das das bestimmt 10-30 Sekunden dauerte... da warte ich bei 1000 Dateien ewig.

Vielen Dank für eure bisherigen Vorschläge.

MfG Hanussen

 

[XunnD]

Wir reden nicht von ein paar MB. Die Archive sind ein paar GB groß. Als ich im Zuge des Windows7-RC vom Microsoft-Image den SHA1-Hash berechnet habe, ärgerte ich mich das das bestimmt 10-30 Sekunden dauerte... da warte ich bei 1000 Dateien ewig.

1GB, 30s entspricht 33MB/s
1GB, 10s entspricht 100MB/s

2GB, 30s entspricht 66MB/s
2GB, 10s entspricht 100MB/s

Aktuelle Festplatten (mit Platter) machen durchschnittlich 60-90MB/s.

Da ist nicht MD5 oder SHA1 langsam, sondern das Medium, wo die Daten herkommen - also sind wie bereits vermutet die E/A-Routinen der Flaschenhals.

MD5 Summen müssen ja auch immer nur dann generiert werden, wenn sich Daten ändern. Wenn sich die Datei seit der letzten Generierung des Hashes nicht geändert hat, kannst Du ja auf einen gespeicherten Hash zurückgreifen.
Sprich: Du bildest eine Relation über die Zeit der letzten Änderung (t) zum Hash zur Zeit t


Im Übrigen würde ich einen Index über die Dateigröße aufbauen, in der nächsten Hierarchie-Ebene dann den Hash des ersten, mittleren und letzten Kilobytes der Datei und dann den Hash der kompletten Datei überprüfen, sodass Du nicht jedesmal alle Bytes einer Datei auslesen musst.

 

[1668mib]

Richtig, ich würde ähnlich vorgehen wie XunnD, die Strategie klingt zumindest nicht schlecht.

 

[hanussen]

Super, vielen Dank.


MfG Hanussen