Ich möchte einige große Objekte, die Bäume darstellen, vergleichen und etwas zwischenspeichern, um zu vermeiden, dass jedes Mal das neue Objekt mit einem bereits bestehenden ...
verglichen wirdDie Frage ist, was wäre das Beste? (ein Kompromiss zwischen Leistung und Kollisionen ...).
Auf der einen Seite habe ich eine reguläre hashCode-Funktion, die auf dem Wert verschiedener Felder basiert (siehe Kapitel 3 von effektives Java , aber ich bin nicht in der Lage, die möglichen Kollisionen, die mit einem solchen Ansatz verbunden sind, 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 habe vielleicht weniger Kollision. 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ß, wie groß die Objekte wären. Bitte beachten Sie auch, dass der berechnete Wert nicht in einer HashTable verwendet wird.
thx ...
Siehe Folgendes:
Beachten Sie Folgendes:
Im Allgemeinen können Sie die Wahrscheinlichkeit einer Kollision anhand der Anzahl erwarteter Objekte und der Anzahl möglicher Hashes (max. Hash-Wert) ermitteln. Eine ausführliche Erläuterung finden Sie Ссылка .
Persönlich? Java-Objekte (instanziierte Klassen) & lt; 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 verwende 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).
Aufgrund des Geburtstagsproblems hängt die Wahrscheinlichkeit einer Kollision davon ab, mit wie vielen Artikeln 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 erst dann eine signifikante Anzahl von Kollisionen aufweisen, wenn 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.
Normalerweise ist MD5 für die Erkennung doppelter Dateien / Daten 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 gegen vorsätzliche Kollisionsangriffe (theoretische, aber keine praktischen Angriffe mit SHA-1 sind bekannt; für die Eingabe von Daten lohnt es sich selten, über eine 160-Bit-Hash-Code-Breite zu gehen). SHA-1 ist etwa die halbe Geschwindigkeit von MD5.
Sicher, wenn Sie MD5 verwenden, sollte die Leistung wahrscheinlich kein allzu großes Problem darstellen. Das hängt natürlich von der Größe Ihrer Daten ab. Sie könnten an einigen Informationen interessiert sein, die ich über Leistung von sicheren Hash-Funktionen in Java zusammenstelle.
>Wenn Sie wirklich etwas schneller brauchen und Sie nur mit ein paar Millionen Datenelementen zu tun haben, dann ist eine weitere Option, die Sie in Betracht ziehen, der 64-Bit-Hash-Algorithmus, der von den Numerical Recipes-Autoren vorgeschlagen wird.
Die Java-Standard-hashCode () - Implementierung (von, sagen wir, String) ist wahrscheinlich nicht geeignet: abgesehen von irgendwelchen Problemen bezüglich der Qualität des Hashes bedeutet seine 32-Bit-Breite, dass Sie nach nur 16.000 Items eine Kollision erwarten so.
Ich werde matt b mit den Worten unterstützen: "Optimiere nicht, bevor du optimieren musst."
Sollten Sie jedoch entscheiden, dass Sie etwas mehr als den Hash-Code brauchen, habe ich die Message-Digests (in meinem Fall MD5) verwendet, um verschiedene Elemente aus RSS-Feeds "eindeutig" zu identifizieren mit demselben Gegenstand, der viele Male 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 funktionierte gut.
Da es sich normalerweise um One-Way-Funktionen handelt, die stark auf sehr kleine Änderungen in den Eingabedaten reagieren sollen, ist es weniger wahrscheinlich, dass Sie Kollisionen mit MD5 oder SHA-1 bekommen.