Algoritmo Hash più veloce in Java per le stringhe

Question

Per semplificare, la mia domanda è: come hash una stringa (circa 200 caratteri) il più rapidamente possibile. La sicurezza non è importante, ma le collisioni SONO un grosso problema.

Nota: dopo un'indagine rapida, sembra che MurmurHash3 potrebbe essere la scelta migliore. Sono aperto a qualsiasi commento dicendo altrimenti th '

Innanzitutto, so che ci sono molte altre domande simili, ma non sono riuscito a trovare una risposta convincente.

Ho un elenco di oggetti, ciascuno contenente un elenco di circa 3k paragrafi che viene salvato in un database. Ogni X ore, quei paragrafi sono rigenerati e ho bisogno di trovare se qualche paragrafo è cambiato, e in tal caso, spingere solo quei nuovi paragrafi.

Il modo più veloce che ho trovato per trovare le differenze (sapendo che la maggior parte del tempo, il contenuto sarà identico) è quello di creare un MerkleTree, salvarlo al DB, e iterare il MerkleTree trovare le differenze, invece di confrontando i paragrafi stessi.

Ciò implica, nel mio caso, che creerò dieci migliaia di hash al secondo da confrontare con ciò che è nel DB. Pertanto, ho bisogno di un modo molto efficiente per creare quegli hash. Non mi interessa la sicurezza, ho solo bisogno di garantire che il numero di collisioni rimanga molto molto basso.

Quale sarebbe il miglior algoritmo disponibile in Java per quello?

---

Nel mio caso, l'oggetto principale è composto da sezioni, che si compone di Lingue, che si compone di paragrafo. La strategia di confronto è:

1) Se l'hash oggetto è identico, fermata, altrimenti vai a 2)

2) Loop su tutti Sezione, mantenere solo la sezione con un diverso hash

3) Effettua il loop su tutte le lingue di quelle sezioni, mantieni solo la lingua con un diverso hash

4) Effettua il ciclo su tutti i paragrafi di tutte quelle lingue, se l'hash è diverso, quindi invia il nuovo contenuto.

Answer 1

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

La versione corta è, utilizzare FNV-1a, aka the Fowler–Noll–Vo hash function, ha prestazioni eccellenti, elevata casualità e bassi collisioni.

Qualsiasi ulteriore spiegazione che potrei fare su questa domanda sarebbe solo una copia e incolla da quella risposta Programmers.SE, che per inciso è la seconda risposta più votata sull'intero sito.

Alcuni altri pensieri:

• In definitiva, si ha un caso abbastanza uso di nicchia. La maggior parte delle persone non ha a che fare con 1 miliardo di set di dati di ingresso regolarmente. Pertanto, potrebbe essere necessario eseguire il proprio benchmarking.
• Detto questo, avere un'alta casualità suggerisce che l'algoritmo è in grado di adattarsi bene agli hash inglesi.
• Non hai davvero parlato di altri problemi; sei in grado di conservare l'intero set di dati in memoria? Quali sono i tuoi requisiti di impronta?

Vedi anche: Fastest Hash Algorithm for Text Data