Schnellster Hash-Algorithmus in Java für Strings

Question

Um es einfach zu machen, ist meine Frage: wie man einen String (etwa 200 Zeichen) so schnell wie möglich hasht. Sicherheit ist nicht wichtig, aber Kollisionen sind eine große Sache.

Hinweis: Nach einer kurzen Untersuchung scheint es so, als wäre MurmurHash3 die beste Wahl. Ich bin offen für jeden Kommentar zu sagen, sonst '

Erstens weiß ich, dass es viele andere ähnliche Frage, aber ich konnte keine überzeugende Antwort noch finden.

Ich habe eine Liste von Objekten, die jeweils eine Liste von etwa 3k Absätzen enthält, die in einer Datenbank gespeichert ist. Alle X Stunden werden diese Absätze neu generiert, und ich muss herausfinden, ob sich Absätze geändert haben, und wenn dies der Fall ist, nur diese neuen Absätze drücken.

Der schnellste Weg, um die Unterschiede zu finden (zu wissen, dass die meiste Zeit der Inhalt identisch sein wird), ist ein MerkleTree zu erstellen, speichern Sie es in der DB, und durchlaufen Sie den MerkleTree, um die Unterschiede statt zu finden Vergleichen Sie die Absätze selbst.

Dies impliziert in meinem Fall, dass ich zehntausend Hashes pro Sekunde erstellen werde, um mit dem zu vergleichen, was in der DB ist. Daher brauche ich eine sehr effiziente Möglichkeit, diese Hashes zu erstellen. Mir ist die Sicherheit egal, ich muss nur sicherstellen, dass die Anzahl der Kollisionen sehr, sehr niedrig bleibt.

Was wäre der beste verfügbare Algorithmus in Java?

In meinem Fall besteht das Hauptobjekt aus Abschnitten, die aus Sprachen besteht, die aus Absatz besteht. Der Vergleich Strategie ist:

1) Wenn das Objekt Hash identisch ist, stoppen, gehen sonst zu 2)

2) Schleife auf alle Abschnitt, halten nur der Abschnitt mit einem anderen Hash

3) Schleife in allen Sprachen dieser Sektionen, behalte nur die Sprache mit einem anderen Hash

4) Loop auf allen Absatz aller dieser Sprachen, wenn der Hash ist anders, dann schieben Sie den neuen Inhalt.

Answer 1

This amazing answer on Programmers Stack Exchange tells you all you need to know.

Die kurze Version ist, verwenden Sie FNV-1a, aka the Fowler–Noll–Vo hash function, hat es eine hervorragende Leistung, hohe Zufälligkeit und niedrigen Kollisionen.

Jede weitere Erklärung, die ich auf diese Frage werfen könnte, wäre nur ein Kopieren und Einfügen von dieser Programmers.SE Antwort, die übrigens die zweithöchste Antwort auf der gesamten Website ist.

Einige andere Gedanken:

• Letztendlich haben Sie eine ziemlich Use-Case-Nische. Die meisten Menschen beschäftigen sich nicht regelmäßig mit 1 Milliarde Eingangsdatensätzen. Daher müssen Sie möglicherweise Ihr eigenes Benchmarking durchführen.
• Das heißt, eine hohe Zufälligkeit deutet darauf hin, dass der Algorithmus wahrscheinlich gut für englische Hashes skalieren wird.
• Sie haben nicht wirklich über andere Themen gesprochen; Können Sie den gesamten Datensatz im Speicher behalten? Was sind Ihre Fußabdruckanforderungen?

Siehe auch: Fastest Hash Algorithm for Text Data