HashCode vs SHA-1

Question

mi piacerebbe confrontare alcuni oggetti di grandi dimensioni che rappresentano alberi e la cache qualcosa per evitare il confronto ogni volta che il nuovo oggetto con quello già esistente ...

La domanda è: che cosa sarebbe essere il migliore? (un compromesso tra prestazioni e collisioni ...).

Da un lato, ho una funzione hashCode regolare in base al valore dei vari campi (a seguito del capitolo 3 del effective Java. Ma io non sono in grado di valutare le potenziali collisioni derivanti da un tale approccio.

D'altra parte, ho l'approccio MessageDigest dalla distribuzione java standard con l'algoritmo SHA-1. Suppongo che non sarà efficiente ma potrei avere meno collisioni.Io ho ragione? È una soluzione corretta nel mio contesto o ho completamente torto?

Il fatto è che non so quale sarebbe la dimensione degli oggetti. Si noti inoltre che il valore calcolato non verrà utilizzato n una HashTable.

thx ...

Answer 1

vedere il seguente:

• 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

Tenete a mente i seguenti:

• Un oggetto può essere diseguale, hanno ancora lo stesso codice hash
• Il potenziale delle collisioni dipende dal numero di oggetti che si incontrano.
• Quanto utile codici hash sarà dipende da come si sceglie di implementare il controllo

In generale, è possibile determinare la probabilità di una collisione in base al numero di oggetti attesi e il numero di possibili hash (valore massimo di hash). Vedere http://en.wikipedia.org/wiki/Birthday_paradox per la spiegazione dettagliata.

Personalmente? Oggetti Java (classi istanziate) < 10.000? Codice hash. Rappresentare file/BLOB/molti dati? SHA-1. Uso l'hashing SHA-1 nel mio database per impedire alle persone di far funzionare ETL sullo stesso file più di una volta. Quindi uso nuovamente l'hashing SHA-1 a un secondo livello per impedire agli utenti di effettuare il ETLing della stessa sezione in più di un file (ad esempio, file diversi ma lo stesso ordine compare due volte).

Answer 2

Personalmente vorrei utilizzare hashCode() per gli oggetti fino a quando è stato dimostrato che eventuali collisioni sono un problema reale per evitare preventivamente l'ottimizzazione di un problema che non si potrebbe effettivamente avere.

Answer 3

Approverò matt b dicendo "non ottimizzare prima di dover ottimizzare".

Tuttavia, se dovessi decidere di avere bisogno di qualcosa di più del codice hash lungo la strada ... Ho utilizzato i digest dei messaggi (MD5 nel mio caso) per identificare "in modo univoco" vari elementi scaricati dai feed RSS, quindi non ho concluso con lo stesso oggetto che appare più volte nella lista mentre eseguivo il polling più e più volte.Quelli erano in genere piccoli post in modo che il digest potesse essere calcolato rapidamente. Nella mia esperienza è stato molto efficace e ha funzionato bene.

Poiché normalmente sono funzioni unidirezionali che hanno lo scopo di reagire con forza anche a cambiamenti molto piccoli nei dati di input, è decisamente meno probabile che si verifichino collisioni con MD5 o SHA-1.

Answer 4

A causa dello birthday problem, la possibilità di una collisione dipende dal numero di articoli con cui si sta lavorando.

Lo spazio 160-bit di SHA-1 è così grande che dubito che potresti mai avere abbastanza elementi per vedere una collisione.

Lo spazio a 32 bit di hashCode() non deve avere un numero significativo di collisioni finché non si dispone di oltre 50.000 articoli. Tuttavia, questo dipende dall'uso di un buon algoritmo di hash.

Per applicare un digest crittografico come SHA-1, è necessario convertire il grafico in una stringa di byte, che è probabile che sia computazionalmente costoso e potrebbe essere complicato.

Answer 5

Solitamente per il rilevamento di file/dati duplicati, MD5 rappresenta un buon compromesso tra velocità e possibilità di collisione. MD5 è inappropriato se qualcuno potrebbe creare intenzionalmente file per ingannare il tuo programma (è leggermente vulnerabile agli attacchi di collisione). Ma se sei solo preoccupato per le collisioni per caso, allora la sua larghezza di 128 bit è praticamente sempre sufficiente al momento.

SHA-1 e SHA-256 vi darà una certa protezione contro gli attacchi di collisione deliberati (teorica, ma nessun attacco pratici con SHA-1 sono noti; per keying di dati, è raramente la pena di andare beyon una larghezza codice hash di 160 bit). SHA-1 è circa la metà della velocità di MD5.

Certamente se si utilizza MD5, le prestazioni probabilmente non dovrebbero essere un problema. Ma ovviamente questo dipende dalla dimensione dei tuoi dati. Potresti essere interessato ad alcune informazioni che ho messo insieme su performance of secure hash functions in Java.

Se hai davvero bisogno di qualcosa di più veloce e hai a che fare solo con qualche milione di dati, allora un'altra opzione da considerare è l'algoritmo di hash a 64 bit proposto dagli autori delle Ricette Numeriche.

L'implementazione di hashCode() standard di Java (di, per esempio, String) non è probabilmente adatta: oltre ai problemi relativi alla qualità dell'hash, la sua larghezza a 32 bit significa che ci si aspetta una collisione dopo appena 16.000 elementi o così.