Credo che sarà più utile se spiego le HashMap in inglese.
Cos’è una HashMap?
Una HashMap è una struttura dati in grado di mappare certe chiavi a certi valori. Le chiavi e i valori possono essere qualsiasi cosa. Per esempio, se stessi facendo un gioco, potrei collegare ogni nome utente ad una lista di amici, rappresentata da una lista di stringhe.
Perché usare una HashMap?
Le HashMap sono molto più veloci per recuperare i dati rispetto agli array e alle liste collegate. Un array ordinato potrebbe trovare un particolare valore in O(log n) con la ricerca binaria. Tuttavia, una HashMap può controllare se contiene una particolare chiave in O(1). Tutte le chiavi devono essere uniche.
Come funzionano le HashMap?
Le HashMap usano un array in background. Ogni elemento nell’array è un’altra struttura di dati (di solito una lista collegata o un albero di ricerca binario). La HashMap usa una funzione sulla chiave per determinare dove posizionare il valore della chiave nell’array. Per esempio, se la mia HashMap accetta stringhe… le possibili funzioni hash possono essere:
A. Return the ASCII value of the first letter.B. Return the sum of the ASCII values of every character in the String.C. Return the ASCII value of the last character in the String.Il valore restituito determinerà l’indice in cui il valore va nell’array.
Ma aspetta! C’è un problema!
È possibile che il valore restituito sia fuori dai limiti dell’array. Pertanto, si suppone che modifichiamo il valore restituito per la lunghezza dell’array.
return Math.abs(number%hashMapArray.length);Collisioni:
Non è possibile che chiavi multiple facciano generare alla funzione hash lo stesso indice? Sì. Per esempio, se abbiamo usato la prima funzione hash mostrata sopra in una mappa hash di stringhe… qualsiasi due stringhe che iniziano con la stessa lettera avranno lo stesso indice di array.
Questo si chiama collisione.
Come gestiamo le collisioni?
Una tecnica di gestione delle collisioni è chiamata Chaining. Poiché ogni elemento nell’array è una lista collegata (o una struttura dati simile), più chiavi che hanno lo stesso valore di hash saranno messe nella stessa lista collegata o “secchio”. In seguito, la mappa hash è in grado di recuperare i valori calcolando il codice hash con la funzione hash, e cercando la particolare lista collegata per vedere se contiene un valore con la stessa chiave.
Si deve scrivere una buona funzione hash per evitare collisioni.
Svantaggi del concatenamento:
-La matrice non può traboccare
-I dati possono essere facilmente rimossi
Svantaggi del concatenamento:
-Può subire un calo di prestazioni se i bucket contengono liste collegate molto lunghe.
Il numero totale di voci rispetto al numero di bucket è chiamato fattore di carico. Se il fattore di carico è troppo basso, viene sprecato molto spazio. Se il fattore di carico è troppo alto, si perde il vantaggio dell’hashing. Un buon compromesso sul fattore di carico è .75
.