HashMap è una struttura di dati che memorizza i dati in coppie (Key, Value), simile a Dictionary in python se ti piace!
Per capire il funzionamento interno di Hashmap, familiarizziamo con i seguenti termini:
HASHING:
Hashing è il processo di conversione di una data chiave in un altro valore basato su una formula utilizzando una funzione. Una funzione di hash è usata per generare il nuovo valore secondo un algoritmo matematico. Il risultato di una funzione di hash è noto come valore di hash o semplicemente, un hash. È usato per indicizzare e recuperare oggetti e per
algoritmi di crittografia.
Una vera funzione hash deve seguire questa regola –
“La funzione hash dovrebbe restituire lo stesso codice hash ogni volta che la funzione viene applicata su oggetti uguali o uguali. In altre parole, due oggetti uguali devono produrre lo stesso codice hash in modo coerente.”
Tutti gli oggetti in Java ereditano un’implementazione predefinita della funzione hashCode() definita nella classe Object.
COLLISIONI :
Tenete presente che due chiavi possono generare lo stesso hash che può portare allo stesso indirizzo. Questo fenomeno è noto come collisione.
Funzioni HashMap
1. Public V get(Object key) : cioè per recuperare un valore dalla mappa sulla base della chiave.
2. Public V put(K key, V value) : o per inserire una coppia chiave, valore nella mappa.
Nota: è generalmente necessario sovrascrivere il metodo hashCode() ogni volta che il metodo equals() viene sovrascritto, in modo da mantenere il contratto generale per il metodo hashCode(), che afferma che oggetti uguali devono avere codici hash uguali.
HashMap in JAVA
Modi per istanziare una HashMap in java:
1. Costruisce una HashMap vuota con la
capacità iniziale e il fattore di carico specificati.
public HashMap(int initialCapacity, float loadFactor)
2. Costruisce una HashMap vuota con la
capacità iniziale specificata e il fattore di carico predefinito (0,75).
public HashMap(int initialCapacity)
3. Costruisce una HashMap vuota con la capacità iniziale predefinita (16) e il fattore di carico predefinito (0.75).
public HashMap()
Fattore di carico e capacità iniziale.
Un’istanza di HashMap ha due parametri che influenzano le sue prestazioni:
1. Capacità iniziale
2. Fattore di carico.
Capacità iniziale:
La capacità è il numero di secchi nella tabella hash, e la capacità iniziale è semplicemente la capacità al momento della creazione della tabella hash.
Fattore di carico:
Il fattore di carico è una misura di quanto la tabella hash possa essere piena prima che la sua capacità venga automaticamente aumentata. Quando il numero di voci nella tabella hash supera il prodotto del fattore di carico e la capacità corrente, la tabella hash viene riorganizzata (cioè le strutture dati interne vengono ricostruite) in modo che la tabella hash abbia approssimativamente il doppio del numero di bucket.
NOTE:
Come regola generale, il fattore di carico predefinito (.75) offre un buon compromesso tra tempo e costi di spazio. Valori più alti diminuiscono l’overhead di spazio ma aumentano il costo di ricerca (riflesso nella maggior parte delle operazioni della classe HashMap, inclusi get e put.
Il numero previsto di voci nella mappa e il suo fattore di carico dovrebbero essere presi in considerazione quando si imposta la sua capacità iniziale, in modo da minimizzare il numero di operazioni di rehash. Se la capacità iniziale è maggiore del numero massimo di voci diviso per il fattore di carico, non si verificheranno mai operazioni di rehash.
HashMap in Java 8
Una HashMap (da java 8) memorizza i dati in più liste di voci collegate singolarmente o più Red BlacK Trees o una miscela di entrambi, a seconda della soglia, chiamati anche secchi o bidoni.
Tutti gli elenchi/alberi sono registrati in un array di Entry (tabella Entry<K,V>) e la capacità predefinita di questo array interno è 16.
Ogni singolo record o una singola coppia di Chiave e un valore in una HashMap è chiamata Entry<Key,Value>.
Entry
HashMap usa una classe interna per memorizzare i dati: Entry<K, V>.
Questa entrata è una semplice coppia chiave-valore con due valori extra che sono i seguenti:
1. Un riferimento ad un’altra voce in modo che una HashMap possa memorizzare voci come liste collegate singolarmente, o come alberi con nodi a sinistra e a destra per fornire una migliore ricerca.
2. Un valore hash che rappresenta il valore hash della chiave. Questo valore di hash è memorizzato per evitare il calcolo dell’hash ogni volta che la HashMap ne ha bisogno.
Entry in java 8 può essere di 2 tipi LinkedList Node o RedBlack Tree Node.
*size di questo come discusso sopra è definito durante l’istanza o di default 16. Sulla base del fattore di carico, aumenta al doppio della dimensione precedente in modo da ospitare ulteriori voci.
Transient Node<K,V> table; //contiene tutte le voci.
In table, ogni indice è un Nodo di una LinkedList o di un RedBlackTree.
La gerarchia di Entry va così:
Map.Entry<K,V> → implements → Node<K,V> → extends → TreeNode<K,V>
LinkedList Node:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; //per mantenere una LinkedList.
Nodo(int hash, K chiave, V valore, Nodo<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
TreeNode:
HashMap, in java 8 , usa RedBlackTree dopo una certa soglia nota come TREEIFY_THRESHOLD(valore predefinito 8), poiché dà una complessità di tempo nel caso peggiore di O(log n), rispetto a LinkedList che dà la ricerca in O(n).
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // collegamenti ad albero rosso-nero
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // necessario per scollegare next alla cancellazione
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
Funzione di HashMap
1. Controlla se la chiave è null o no. Si noti che ci può essere solo una chiave nulla in HashMap.Se la chiave è nulla, allora le chiavi nulle mappano sempre su hash 0, quindi indice 0 della tabella.
2. Se la chiave non è nulla, il metodo chiama il metodo hashCode() sull’oggetto chiave (sovrascritto dall’utente nella rispettiva classe Key) e applica l’hashValue restituito alla propria funzione hash statica per trovare una posizione del secchio (array di supporto) dove le chiavi e i valori sono memorizzati sotto forma di una classe annidata chiamata Entry.
La posizione del secchio è un indice della tabella Entry.
NOTA: stiamo calcolando il valore di hash di nuovo usando hash(hashValue) come difende contro la scarsa qualità della funzione hash.
3. Il valore di hash finale è usato per trovare la posizione del secchio in cui l’oggetto Entry è memorizzato.
La complessità di get() e put() è O(1), assumendo che la funzione hash disperda correttamente gli elementi tra i bucket.
Nota: Come sappiamo ora, in caso di collisione hash gli oggetti entry sono memorizzati come un nodo in un elenco collegato e il metodo equals() è usato per confrontare le chiavi. Questo confronto per trovare la chiave corretta con in un elenco collegato è un’operazione lineare quindi nel peggiore dei casi la complessità diventa O(n).
Per affrontare questo problema, gli elementi hash di Java 8 usano alberi bilanciati invece di elenchi collegati dopo una certa soglia. Il che significa che HashMap inizia con la memorizzazione di oggetti Entry in linked list, ma dopo che il numero di elementi in un hash diventa più grande di una certa soglia, l’hash passerà dall’uso di una linked list a un albero bilanciato, che migliorerà le prestazioni nel caso peggiore da O(n) a O(log n).
Cosa succede se due chiavi diverse hanno lo stesso hashcode?
4. In un indice possiamo avere più valori poiché possiamo avere collisioni in hashing. Per capire di quale abbiamo bisogno, HashMap prende l’aiuto di equals().
Soluzione, il metodo equals() viene in soccorso. Poiché il secchio è uno e abbiamo due oggetti con lo stesso codice hash.
Quindi, dopo aver recuperato l’indice della chiave, recupera il primo nodo presente su quell’indice. Il primo nodo viene poi confrontato con la chiave usando equals(), se questo è il nodo desiderato, restituisce il valore direttamente da qui.
Altrimenti, scopre l’istanza del nodo, per capire se i dati contenenti memorizzati in questo indice sono nel formato di lista collegata o albero RedBlack.
Una volta capito questo, attraversiamo la LinkedList o l’albero, confrontando le chiavi in ogni voce usando keys.equals() fino a quando non ritorna vero. Poi viene restituito l’oggetto corrispondente all’entrata Value .
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}finale Node<K,V> getNode(int hash, Object key) {
Node<K,V> tab; //rappresenta l’Array di Entry
Node<K,V> first, e;
int n; K k;/* Controllo se la tabella ha entries .*/
/* Inoltre, trovando l’indice sulla base dell’hash calcolato nei passi precedenti, dove la voce è memorizzata come lista o nodo dell’albero.*/if ((tab = tabella) != null && (n = lunghezza tab) > 0 &&(first = tab) != null) {
/*Ricerca del primo nodo nell’indice ottenuto sulla base dell’hash.*/
if (first.hash == hash && /*controlla sempre il primo nodo*/
((k = first.key) == key|| (key != null && key.equals(k))))
return first;/*Se il primo nodo di quell’indice non è il valore che stiamo cercando, allora va a capo.*/
if ((e = first.next) != null) {
if (prima istanza di TreeNode)
/*Fetching da Red Black Tree se inizia Node sull’indice if di TreeNode .*/return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {/*Fetching da LinkedList se il nodo di partenza è di tipo Node e non Tree.*/
if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
while ((e = e.next) != null);
}}
return null;
}
PUT:
1. Se la chiave è nulla, allora le chiavi nulle mappano sempre all’hash 0, quindi all’indice 0 della tabella.
2. Se la chiave non è nulla, il metodo chiama il metodo hashCode() sull’oggetto chiave (sovrascritto dall’utente nella rispettiva classe Key) e applica hashValue restituito alla propria funzione hash statica per trovare una posizione del secchio (array di supporto) dove le chiavi e i valori devono essere memorizzati sotto forma di una classe annidata chiamata Entry.La posizione del secchio è un indice della Entry cioè la tabella.
3. Il valore hash finale è usato per trovare la posizione del secchio in cui l’oggetto Entry deve essere memorizzato. Poi, le chiavi sono attraversate nello stesso modo descritto in get(), per controllare se la chiave esiste già, se esiste il valore viene sostituito con il nuovo valore.
Altrimenti, viene controllata la dimensione della lista,
Se supera la TREEIFY_THRESHOLD(default 8), i nodi vengono ristrutturati in RedBlackTree e la nuova chiave viene memorizzata con il valore in essa.
Se la soglia non viene superata, la nuova Entry viene creata con il rispettivo chiave-valore, e viene memorizzata.
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);}finale V putVal(int hash, K chiave, V valore, boolean onlyIfAbsent, boolean evict) {
Node<K,V> tab;
Node<K,V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab) == null)
tab = newNode(hash, key, value, null);
else {
/*SAME che attraversa come in get()*/
Node<K,V> e; K k;
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
/*Controllare se il TREEIFY_THRESHOLD è superato o no.*/if (binCount >= TREEIFY_THRESHOLD – 1) /* -1 per 1st*/
treeifyBin(tab, hash);
break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}}if (e != null) { /* mappatura esistente per chiave*/
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}}++modCount;
if (++size > soglia)
resize();
afterNodeInsertion(evict);
return null;}
più da leggere
Chiave immutabili:
Perché stringhe e interi sono una buona implementazione di chiavi per HashMap? Soprattutto perché sono immutabili! Se scegliete di creare la vostra classe Key e non la rendete immutabile, potreste perdere i dati all’interno della HashMap.
Rehashing:
Rehashing è il processo di ricalcolo dell’hashcode di voci già memorizzate (coppie Chiave-Valore), per spostarle in un’altra hashmap di dimensioni maggiori quando viene raggiunta la soglia del Load factor.
Quando il numero di elementi nella mappa supera il limite del fattore di carico, in quel momento la hashmap raddoppia la sua capacità e l’hashcode viene ricalcolato degli elementi già memorizzati per una distribuzione uniforme delle coppie chiave-valore nei nuovi bucket.
Perché è necessario?
Dopo aver raddoppiato la capacità, cosa fare con le coppie chiave-valore già presenti nei bucket?
Se manteniamo le coppie chiave-valore esistenti così come sono, allora raddoppiare la capacità potrebbe non aiutare, perché la complessità O(1) sarà raggiunta solo se gli elementi sono distribuiti uniformemente in tutti i bucket.
Quindi per ogni coppia chiave-valore esistente, l’hashcode viene calcolato di nuovo con la capacità hashmap aumentata come parametro, il che risulta nel collocare l’elemento nello stesso bucket o in un bucket diverso.