hashCode() + spiegazione + esempio

[peruzzo]

Non riesco a capire cosa fa hashCode(). Mi potete spiegare e fare un esempio semplicissimo?

grazie

[MItaly]

http://en.wikipedia.org/wiki/Hash_function

[peruzzo]

Non ho capito una mazza! Dovrebbe essere una funzione che converte stringhe in numeri ma non mi è chiaro l'algoritmo e non se ne capisce l'utilità...

Il disegnino a lato proprio non mi aiuta.

[Alex'87]

Originariamente inviato da peruzzo
Non ho capito una mazza! Dovrebbe essere una funzione che converte stringhe in numeri ma non mi è chiaro l'algoritmo e non se ne capisce l'utilità...

Il disegnino a lato proprio non mi aiuta.

L'algoritmo di hash te lo puoi inventare quando reimplementi hashcode() ovviamente. L'importante è che dati N oggetti la probabilità che due (o più) oggetti abbiano lo stesso hashcode sia bassa, per evitare collisioni (utile anche in casi di strutture dati come hashtable/hashmap ecc)

Ad esempio, non si salva in chiaro una password, ma un suo hash. Quando l'utente vuole accedere si confronta l'hash della password che inserisce con l'hash salvato: se coincidono viene eseguito l'accesso, altrimenti no. Capisci perché le collisioni sono un problema ed è importante avere un algoritmo di hashing fatto bene ^^

Ipotizza un algoritmo di hash del genere: data una stringa, converte ogni carattere nella corrispettiva posizione nell'alfabeto (A=0, B=1, C=2, ecc) e somma.

La stringa ABC avrebbe come hash 3. Così come le stringhe BCA, BAC, AAD, AAAAAABBB ecc. Capisci che questo è un PESSIMO algoritmo di hash.

Tutt'altra cosa invece l'MD5. Due esempi, presi direttamente dalla pagina di wikipedia. Le due frasi sono uguali, a meno del punto finale. Eppure il loro hash è completamente differente:

MD5("The quick brown fox jumps over the lazy dog") = 9e107d9d372bb6826bd81d3542a419d6
MD5("The quick brown fox jumps over the lazy dog.") = e4d909c290d0fb1ca068ffaddf22cbd0

[peruzzo]

Capisco, grazie mille, ora comincio a capire. Mi sapresti scrivere un codice molto semplice che implementa quello che dici?

[MItaly]

Originariamente inviato da Alex'87
Ad esempio, non si salva in chiaro una password, ma un suo hash. Quando l'utente vuole accedere si confronta l'hash della password che inserisce con l'hash salvato: se coincidono viene eseguito l'accesso, altrimenti no. Capisci perché le collisioni sono un problema ed è importante avere un algoritmo di hashing fatto bene ^^

Occhio però a non confondere un hash "normale" con un hash crittografico.

Una funzione di hash "normale" serve sostanzialmente per fare confronti rapidi (in cui stabilire velocemente se due stringhe/altri dati sono differenti) e/o come indice in una hashtable; l'hash in questione deve dare poche (idealmente nessuna) collisioni per il set di dati fornito ed essere estremamente veloce da calcolare.

Un hash crittografico, invece, deve dare anche lui dare poche collisioni, ma deve essere invece tendenzialmente lento (per evitare attacchi di bruteforce) e soprattutto deve essere sostanzialmente impossibile da invertire - o comunque, deve essere impossibile generare volontariamente delle collisioni - proprietà che invece è sostanzialmente irrilevante per un hash non crittografico.

Il metodo hashCode non è un hash crittografico (è estremamente veloce ed è facilissimo generare volontariamente delle collisioni), ma un hash da usare in altro genere di algoritmi, ad esempio, appunto, come indice in una hashtable, oppure per un confronto "preliminare" tra moltissime stringhe.

[peruzzo]

perché non usare equals() invece di hashCode per confrontare delle stringhe? perché devo convertire una stringa per confrontarla?

[peruzzo]

Un esempio con hashCode() mi potrebbe essere utile per capirne l'utilità (per ora non la vedo) mentre un esempio con un l'MD5 mi potrebbe interessare parecchio e potrebbe anche servirmi. Java ha un metodo per MD5, un metodo per convertire una password in MD5 e un secondo metodo per confrontare la stringa immessa con l'MD5 creato in precedenza? Se ho capito bene passare da stringa a MD5 è semplice mentre da MD5 a string è impossibile e si deve fare solo per bruteforse ovvero per tentativi, giusto?

[MItaly]

Originariamente inviato da peruzzo
perché non usare equals() invece di hashCode per confrontare delle stringhe? perché devo convertire una stringa per confrontarla?

Se devi fare un confronto tra due stringhe qualunque usi equals; ma supponi di avere un array con un mucchio di stringhe lunghe e dover verificare rapidamente di continuo se delle stringhe che ti arrivano sono già nell'array. Un confronto completo con ogni stringa è lento (confrontare due stringhe di lunghezza uguale implica ciclare sui loro caratteri e confrontarli uno per uno, finché uno non differisce); se invece ti prepari un array separato contenente gli hash di tutte le stringhe dell'array il tuo confronto diventa velocissimo: per ogni stringa devi solo confrontare un intero (operazione estremamente veloce), e in questo modo scremi il grosso delle stringhe differenti. Può essere che ci sia qualche collisione (=stringhe diverse con hash uguale), che risolvi con confronti diretti (con equals), ma rispetto al fare un confronto completo stringa per stringa non c'è paragone in termini di velocità.
(poi ovviamente ci sono ottimizzazioni a questo metodo, ma lasciamo stare)

Ma soprattutto, avere una funzione di hash per ogni tipo è fondamentale per poter implementare le hash table, struttura dati fondamentale (che infatti Java fornisce) che si usa spessissimo. Non a caso, nella documentazione "generica" di hashCode si legge:

Returns a hash code value for the object. This method is supported for the benefit of hashtables such as those provided by java.util.Hashtable.