HashCode vs SHA-1

Question

Ich mag würde einige große Objekte vergleichen Bäume und Cache etwas repräsentiert jedes Mal mit einem das neue Objekt bereits zu vermeiden Vergleich bestehende ...

Die Frage ist, was würde das Beste sein? (ein Kompromiss zwischen Leistung und Kollisionen ...).

Auf der einen Seite habe ich eine regelmäßige hashCode Funktion basierend auf dem Wert der einzelnen Felder haben (im Anschluss an das Kapitel 3 von effective Java. Aber ich bin nicht in der Lage die möglichen Kollisionen durch einen solchen Ansatz zur Folge zu bewerten.

Auf der anderen Seite habe ich den MessageDigest-Ansatz aus der Standard-Java-Distribution mit SHA-1-Algorithmus.Ich nehme an, es wird nicht effizient sein, aber ich kann weniger Kollision haben. Habe ich Recht? Ist es eine richtige Lösung in meinem Kontext oder bin ich völlig falsch?

Die Sache ist, dass ich nicht weiß, was die Größe der Objekte wäre. Bitte beachten Sie auch, dass der berechnete Wert wird nicht verwendet werden i n eine Hashtabelle.

thx ...

Answer 1

Siehe folgend:

• Ein Objekt kann ungleich sein, noch hat:
  • 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

  im Sinne der folgenden Halt der gleiche Hash-Code

• Ihr Kollisionspotenzial hängt davon ab, wie viele Objekte Sie treffen.
• Wie nützlich Codes Hash sein wird, hängt davon ab, wie Sie

Im Allgemeinen implementieren überprüfen, können Sie die Chance einer Kollision auf die Anzahl der erwarteten Objekte und die Anzahl der möglichen Hash-Werte (max Hash-Wert) auf der Basis bestimmen. Eine detaillierte Erklärung finden Sie unter http://en.wikipedia.org/wiki/Birthday_paradox.

Persönlich? Java-Objekte (instanziierte Klassen) < 10.000? Hash-Code. Darstellen von Dateien/Blobs/viele Daten? SHA-1. Ich verwende SHA-1-Hashing in meiner Datenbank, um zu verhindern, dass Benutzer ETL mehr als einmal an derselben Datei arbeiten. Ich benutze dann SHA-1-Hashing erneut auf einer zweiten Ebene, um zu verhindern, dass Benutzer denselben Abschnitt in mehr als einer Datei ablegen (z. B. unterschiedliche Dateien, aber die gleiche Reihenfolge wird zweimal angezeigt).

Answer 2

Persönlich würde ich hashCode() für die Objekte verwenden, bis festgestellt worden ist, dass mögliche Kollisionen ein tatsächliches Problem sind präventiv zu vermeiden, ein Problem zu optimieren, die Sie vielleicht nicht wirklich haben.

Answer 3

Ich befürworte matt b sagt: "nicht optimieren, bevor Sie optimieren müssen."

Sollten Sie jedoch entscheiden, dass Sie etwas mehr als den Hash-Code benötigen ... Ich habe Nachrichtenauszüge (MD5 in meinem Fall) verwendet, um verschiedene Elemente aus RSS-Feeds "eindeutig" zu identifizieren mit demselben Gegenstand auftauchen, der oft in der Liste erscheint, während ich immer wieder pollte.Dies waren in der Regel kleine Buchungen, so dass der Digest schnell berechnet werden konnte. Nach meiner Erfahrung war es sehr effektiv und hat gut funktioniert.

Da es sich normalerweise um One-Way-Funktionen handelt, die stark auf sehr kleine Änderungen der Eingabedaten reagieren sollen, ist die Wahrscheinlichkeit von Kollisionen mit MD5 oder SHA-1 deutlich geringer.

Answer 4

Aufgrund der birthday problem, hängt die Wahrscheinlichkeit einer Kollision davon ab, mit wie vielen Elementen Sie arbeiten.

Der 160-Bit-Bereich von SHA-1 ist so groß, dass ich bezweifle, dass Sie jemals genug Objekte haben könnten, um eine Kollision zu sehen.

Der 32-Bit-Bereich von hashCode() sollte keine signifikante Anzahl von Kollisionen haben, bis Sie über 50.000 Elemente haben. Dies hängt jedoch von der Verwendung eines guten Hash-Algorithmus ab.

Um ein kryptographisches Digest wie SHA-1 anzuwenden, müssen Sie Ihr Diagramm in eine Bytefolge umwandeln, die wahrscheinlich rechenintensiv ist und kompliziert sein könnte.

Answer 5

Normalerweise ist MD5 für die doppelte Datei-/Datendetektion ein guter Kompromiss zwischen Geschwindigkeit und Kollisionswahrscheinlichkeit. MD5 ist unangemessen, wenn jemand absichtlich Dateien manipulieren könnte, um Ihr Programm zu täuschen (es ist leicht anfällig für Kollisionsangriffe). Aber wenn Sie nur zufällig über Kollisionen besorgt sind, dann ist seine 128-Bit-Breite derzeit praktisch immer ausreichend.

SHA-1 und SHA-256 bieten Ihnen einen gewissen Schutz vor absichtlichen Kollisionsangriffen (theoretische, aber keine praktischen Angriffe mit SHA-1 sind bekannt; zum Verschlüsseln von Daten lohnt es sich selten, über eine 160-Bit-Hash-Code-Breite zu gehen). SHA-1 ist ungefähr die Hälfte der Geschwindigkeit von MD5.

Sicher, wenn Sie MD5 verwenden, sollte die Leistung wahrscheinlich nicht zu viel von einem Problem sein. Das hängt natürlich von der Größe Ihrer Daten ab. Möglicherweise interessieren Sie sich für einige Informationen, die ich über performance of secure hash functions in Java zusammengestellt habe.

Wenn Sie wirklich etwas schneller benötigen und Sie nur mit ein paar Millionen Datenelementen zu tun haben, dann ist eine andere Option in Betracht zu ziehen, die von den Numerical Recipes Autoren vorgeschlagenen 64-Bit Hash-Algorithmus.

Die Java-HashCode() - Standardimplementierung (von, sagen wir, String) ist wahrscheinlich nicht geeignet: abgesehen von irgendwelchen Problemen mit der Qualität des Hashes, seine 32-Bit-Breite bedeutet, dass Sie eine Kollision nach nur 16.000 Elemente erwarten oder so.