HashCode gegenüber SHA-1

Question

Ich möchte einige große Objekte vergleichen, die Bäume und Caches darstellen etwas um zu vermeiden, dass das neue Objekt jedes Mal mit einem bereits vorhandenen Objekt verglichen wird...

Die Frage ist, was wäre das Beste? (ein Kompromiss zwischen Leistung und Kollisionen...).

Einerseits habe ich eine reguläre HashCode-Funktion, die auf dem Wert verschiedener Felder basiert (in Anlehnung an das Kapitel 3 von leistungsfähiges Java . Aber ich bin nicht in der Lage, die potenziellen Kollisionen zu bewerten, die ein solcher Ansatz mit sich bringt.

Auf der anderen Seite habe ich den MessageDigest-Ansatz aus der Standard-Java-Distribution mit SHA-1-Algorithmus. Ich gehe davon aus, dass dies nicht effizient ist, aber ich habe vielleicht weniger Kollisionen. Liege ich da richtig? Ist dies eine korrekte Lösung in meinem Kontext oder liege ich völlig falsch?

Das Problem ist, dass ich nicht weiß, wie groß die Objekte sein werden. Bitte beachten Sie auch, dass der berechnete Wert nicht in einer HashTable verwendet werden soll.

Danke...

Answer 1

Siehe das Folgende:

• http://www.javapractices.com/topic/TopicAction.do?Id=28
• https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode--
• http://www.ibm.com/developerworks/java/library/j-jtp05273.html

Beachten Sie folgende Punkte:

• Ein Objekt kann ungleich sein, aber den gleichen Hash-Code haben
• Ihr Kollisionspotenzial hängt davon ab, wie viele Objekte Sie treffen.
• Wie nützlich Hash-Codes sind, hängt davon ab, wie Sie die Überprüfung durchführen

Im Allgemeinen können Sie die Wahrscheinlichkeit einer Kollision anhand der Anzahl der erwarteten Objekte und der Anzahl der möglichen Hashes (maximaler Hashwert) bestimmen. Siehe http://en.wikipedia.org/wiki/Birthday_paradox für die ausführliche Erklärung.

Persönlich? Java-Objekte (instanziierte Klassen) < 10.000? Hash-Code. Darstellung von Dateien / Blobs / vielen Daten? SHA-1. Ich verwende SHA-1-Hashing in meiner Datenbank, um zu verhindern, dass ETL-Arbeiten an ein und derselben Datei mehrfach durchgeführt werden. Dann verwende ich SHA-1-Hashing auf einer zweiten Ebene, um zu verhindern, dass ein und derselbe Abschnitt in mehr als einer Datei mit ETL bearbeitet wird (z. B. verschiedene Dateien, aber die gleiche Reihenfolge taucht zweimal auf).

Answer 2

Persönlich würde ich verwenden hashCode() für die Objekte, bis bewiesen ist, dass mögliche Kollisionen ein tatsächliches Problem darstellen, um zu vermeiden, dass man ein Problem, das man vielleicht gar nicht hat, vorschnell optimiert.

Answer 3

Aufgrund der Geburtstagsproblem, Die Wahrscheinlichkeit eines Zusammenstoßes hängt davon ab, mit wie vielen Gegenständen Sie arbeiten.

Der 160-Bit-Raum von SHA-1 ist so groß, dass ich bezweifle, dass man jemals genug Elemente haben könnte, um eine Kollision zu erkennen.

Der 32-Bit-Bereich von hashCode() sollte erst bei mehr als 50.000 Artikeln eine nennenswerte Anzahl von Kollisionen auftreten. Dies hängt jedoch von der Verwendung eines guten Hash-Algorithmus ab.

Um einen kryptografischen Digest wie SHA-1 anzuwenden, müssen Sie Ihren Graphen in eine Byte-Zeichenkette umwandeln, was wahrscheinlich rechenintensiv und kompliziert sein kann.

Answer 4

Für die Erkennung doppelter Dateien/Daten ist MD5 in der Regel ein guter Kompromiss zwischen Geschwindigkeit und Kollisionswahrscheinlichkeit. MD5 ist ungeeignet, wenn jemand absichtlich Dateien fälschen könnte, um Ihr Programm zu täuschen (es ist leicht anfällig für Kollisionsangriffe). Wenn Sie sich jedoch nur Sorgen über zufällige Kollisionen machen, ist die Breite von 128 Bit derzeit praktisch immer ausreichend.

SHA-1 und SHA-256 bieten einen gewissen Schutz gegen absichtliche Kollisionsangriffe (theoretische, aber keine praktischen Angriffe mit SHA-1 sind bekannt; für die Verschlüsselung von Daten lohnt es sich kaum, über eine Hash-Code-Breite von 160 Bit hinauszugehen). SHA-1 ist etwa halb so schnell wie MD5.

Wenn Sie MD5 verwenden, sollte die Leistung wahrscheinlich kein allzu großes Problem darstellen. Aber das hängt natürlich auch von der Größe Ihrer Daten ab. Vielleicht sind Sie an einigen Informationen interessiert, die ich zusammengestellt habe über Leistung von sicheren Hash-Funktionen in Java.

Wenn Sie wirklich etwas Schnelleres brauchen und nur mit ein paar Millionen Daten zu tun haben, dann ist der 64-Bit-Hash-Algorithmus, den die Autoren von Numerical Recipes vorgeschlagen haben, eine weitere Option, die Sie in Betracht ziehen sollten.

Javas Standard-HashCode()-Implementierung (z. B. von String) ist wahrscheinlich nicht geeignet: Abgesehen von Problemen mit der Qualität des Hashes bedeutet seine 32-Bit-Breite, dass Sie bereits nach 16.000 Elementen oder so eine Kollision erwarten.

Answer 5

Ich schließe mich dem Spruch von Matt B an: "Optimieren Sie nicht, bevor Sie optimieren müssen."

Sollten Sie jedoch später etwas anderes als den Hash-Code benötigen... Ich habe Nachrichten-Digests (in meinem Fall MD5) verwendet, um verschiedene von RSS-Feeds heruntergeladene Artikel "eindeutig" zu identifizieren, damit nicht immer wieder derselbe Artikel in der Liste auftaucht, wenn ich die Abfrage wieder und wieder mache. In der Regel handelte es sich dabei um kleine Einträge, so dass die Zusammenfassung schnell berechnet werden konnte. Meiner Erfahrung nach war dies sehr effektiv und hat gut funktioniert.

Da es sich in der Regel um Einwegfunktionen handelt, die selbst auf sehr kleine Änderungen der Eingabedaten stark reagieren, ist die Wahrscheinlichkeit von Kollisionen mit MD5 oder SHA-1 deutlich geringer.