Flottes Hash-Verfahren

[ByTheTime]

Moin,
es gibt zwar schon unzählige Threads dazu, wie man eine Datei hashen hann, aber ich wollte mal in Erfahrung bringen, welche am schnellsten sind. Es geht darum Dateien zu hashen. Ungefähr 124 GB Musik (nehm' ich zum testen) sollen so schnell wie möglich gehasht werden. Die beiden mir bekannten Verfahren sind das MD4 und MD5 Hashverfahren. Aber wo genau liegt der Unterschied? Ich habe gelesen das MD5 entwickelt wurde, da man MD4 möglicherweiße für unsicher hielt. Da es bei mir aber nicht um Sicherheit geht, sondern darum, die Vollständigkeit/Fehlerfreiheit einer Datei zu überprüfen, kann mir das ja egal sein. Zudem hat Hagen hier erwähnt, das seine MD4 Variante 239Mb/sec packt und MD5 immerhin 162Mb/sec. Ich habe mal ein Pseudo-Programm geschrieben, das packt ganze 29,8Mb/sec. Ist zwar auch ziemlich hingerotzt und unoptimiert, aber selbst wenn ich da noch versuche was rauszuholen, komm ich nie im Leben auf Hagen's Werte. Ich habe es übrigens mit INDY gemacht, da sind Hash-Funktionen dabei. Aber wie gesagt, da bietet sich MD4 ja wohl an, zumal es weniger Speicher verbraucht. Aber wo ist der Hacken? Würde MD4 für solch einen Zweck völlig ausreichen? Und wer hat hier die schnellste Funktion parat :-D Können ja 'nen Wettkampf draus machen 8-)

MfG,
Lukas

P.S: Pseudo-Hasher im Anhang :-D Einfach Ordner wählen und hashen :thumb: Bei mir haben 11 Datein mit insgesamt 962MB 32270ms gebraucht (32,27s) :lol::roll:

[Aphton]

Ich vermute mal, dass es bei MD4 (zwar selten bis fast nie aber) öfter zu einer Kollision kommt - sprich Hash(A) == Hash(B).
Man hat für MD5 auch Kollisionen gefunden bzw es gibt soweit ich mich recht entsinne, Methoden, eine Kollsion speziell für einen Datenstrom zu finden.
Wie dem auch sei, ich schätze, sofern es dir um die Eindeutigkeit geht, müsstest du da großen Wert drauf legen.
Ich kann dir aber leider nicht sagen, welcher Hashing Algorithmus da in dieser Hinsicht am besten ist.
Edit: Kuck mal hier

[Aphton]

Achja, ich benötige für 962 mb (11 gleich große Dateien mit zufälligem, gleichverteiltem Inhalt - Entropie!) ca 2 sek (mit MD5).

Edit: Habs angehängt. Kann sein, dass mein Rechner stärker ist als deiner. Probiers selbst aus!

Edit2: Habe ich den Hagen geschlagen? Wie alt ist dieser Thread, wo er diese Zahlen gepostet hat? Wahrscheinlich ist das schon ein bisschen her und damals waren die Rechner evt. nicht so gut..

[ByTheTime]

Danke erstmal für die Antwort. Kannst du mal ein paar Kerndaten von deinem Rechner posten. Ich hab hier nur ein Laptop mit i5M, 4GB Ram. Nebenbei noch eine GT310M als Graka, was aber nebensächlich ist. Mit deiner Hashing.exe brauche ich 4,46 Sekunden. Morgen versuche ich das ganze nochmal an einem anderen System mit i5, 8GB Ram zu testen. Allerdings bin ich dann erstmal im Urlaub... Mal sehen ob ich es noch schaffe.

[Aphton]

Ups entschuldige mich, es war doch MD4 =/
Ich uploade mal mit MD5.

Mit md5 brauch ich im Schnitt um die 3 Sekunden.
(Achja, nicht wundern, dass da immer dieselben Daten generiert werden - es wird ein konstanter RandomSeed gesetzt damit über verschiedene Systeme hinweg verglichen werden kann!)

Edit:
Relevante PC Daten:
Desktop-Standrechner mit i7-2600 3.4 Ghz
8gb Ram und Win 7 64 Bit System.

[jaenicke]

Zitat:

Zitat von ByTheTime (Beitrag 1221005)

Ich hab hier nur ein Laptop mit i5M, 4GB Ram.

Dass das bei einer Notebookfestplatte deutlich länger dauert, ist ja zu erwarten... die schaffen oft nur um die 70 MiB/s maximal, selbst die schnellsten liegen bei rund 100 MiB/s. Deshalb bringen SSDs ja auch gerade bei Notebooks so viel.

[ByTheTime]

Das läuft bei mir sogar schneller durch: 3,74 Sekunden.

Edit: @jaenicke: Ich setzt mich morgen früh nochmal an einen flotten Rechner mit i5, 8GB Ram und SSD. Mal sehen was dabei herauskommt.

[Aphton]

Nun, das Hashen könnte man ja direkt im Hauptspeicher machen - wird dadurch natürlich um einiges schneller.. Aber da er es anders gemacht hat, wollte ich es genauso machen um für gleiche Verhältnisse zu sorgen

[sx2008]

Wie gross sind denn die Datenblöcke die durch MD4 oder MD5 gejagt werden?
Falls die Blöcke < 4kB sind wäre das der Flaschenhals.

[Aphton]

Delphi-Quellcode:

const
  DefaultChunkSize = $40000; // 256 kb - like Windows!

Hab irgendwann einmal rausgefunden, dass Windows beim Kopieren von Datein udgl auch 256 kb Chunkgrößen verwendet, daher der Kommentar!

Meine Hash-API (Wrapper) sollte hier irgendwo veröffentlicht sein (Luckie hat es bei seiner API Sammlung aufgenommen - sucht mal nach aphtonHashAPI)

[mentaltec]

für

Zitat:

Zitat von ByTheTime (Beitrag 1221000)

Vollständigkeit/Fehlerfreiheit

wurde eigentlich CRC erfunden -- da sollte auch etwas schneller sein bzw. weniger CPU beanspruchen

mfg

[ByTheTime]

Urlaub vorbei, bin wieder fleißig am arbeiten. Und ja, CRC hat sich als bessere Lösung erwiesen. Dazu hab ich auch mehr gefunden und hab es in meine Anwendung implementiert. Hier, hierund hier etwas gespickt.

Danke für eure Hilfe :)

[sx2008]

CRC32 ist natürlich etwas schneller als MD4, aber bei sagen wir mal 4000 MP3-Dateien besteht rein rechnerisch die Chance von 1 zu 500000, dass zwei unterschiedliche Dateien den gleichen CRC32 Wert erhalten.

Wenn also zwei Dateien den gleichen CRC haben sollten, wäre es sinnvoll trotzdem noch zu prüfen, ob die Dateien wirklich gleichen Inhalts sind.

Wenn du Duplikate finden möchtest, dann kann ich dir SearchMyFiles von Nirsoft empfehlen.

[Furtbichler]

Beim Hashen von Strings ist ein ELF-Hash viel schneller als CRC. Er erzeugt bei kurzen Strings auch nicht mehr Kollisionen (bei meinen Versuchen)

Delphi-Quellcode:

Function HashFromStr(Const Value: String): Cardinal; // ELF-Hash
Var
   i: Integer;
   x: Cardinal;
Begin
   Result := 0;
   For i := 1 To Length(Value) Do Begin
     Result := (Result Shl 4) + Ord(Value[i]);
     x := Result And $F0000000;
     If (x <> 0) Then
       Result := Result Xor (x Shr 24);
     Result := Result And (Not x);
   End;
End;

[p80286]

Zitat:

Zitat von sx2008 (Beitrag 1221989)

CRC32 ist natürlich etwas schneller als MD4, aber bei sagen wir mal 4000 MP3-Dateien besteht rein rechnerisch die Chance von 1 zu 500000, dass zwei unterschiedliche Dateien den gleichen CRC32 Wert erhalten.

Wenn also zwei Dateien den gleichen CRC haben sollten, wäre es sinnvoll trotzdem noch zu prüfen, ob die Dateien wirklich gleichen Inhalts sind.

Vor längerer Zeit ist dieses Problem hier schon einmal diskutiert worden. Ist der Hash-Wert unterschiedlich sind auch die Dateien unterschiedlich. Bei gleichem Hash-Wert können die Dateien auch gleich sein. Sicher ist man nur mit einem binären Vergleich.

Ach ja, was manchmal übersehen wird Dateien mit unterschiedlicher Größe sind nicht gleich.

Gruß
K-H