L’HashMap permette di memorizzare delle coppie < chiave, valore>.
Sintassi:
Map<Chiave, Valore> capoluoghi = new HashMap<>();
il metodo put consente di inserire un nuovo valore in corrispondenza di una chiave; se la chiave è già presente il vecchio valore viene sovrascritto col nuovo;
il metodo get reperisce il valore per la chiave passata come parametro, null se tale chiave non viene trovata all’interno della mappa;
Esempio
HashMap<String, String> h =
new HashMap<String, String>();
h.put("Key1","Pippo");
h.put("Key2","Pluto");
h.put("Key3","Paperino");
h.put("Key4","Qui");
h.put("Key5","Quo");
System.out.println(h.get("Key1"));// stampa Pippo
Questa volta bisogna capire cosa avviene dietro le quinte.
L’hashmap, internamente, usa, per una questione di efficienza, un array di liste per memorizzare le coppie <chiave, valore>.
L’array è anche chiamato buckets e la singola posizione bucket.
Di default, il buckets ha una dimensione di 16.
Immaginiamo, per semplicità, di voler memorizzare delle coppie di stringhe, e inseriamo
<”chiaveUno”,”Pippo”>
L’hashmap deve decidere in quale posizione i (bucket) inserirla.
Per fare ciò, chiama un metodo speciale, detto hashcode, definito all’interno della classe che rappresenta la chiave, in questo caso quindi la stringa “chiaveUno”, che ritorna un numero intero, anch’esso spesso indicato hashcode.
Questo hashcode indica la posizione in cui inserire la coppia.
Ipotizziamo che l’hashcode di “chiaveUno” sia 1450, ma i bucket disponibili sono 16. Allora l’hashcode deve essere convertito in un numeroo compreso tra 0 e 15. Per fare ciò, viene chiamato un metodo indexFor(hashcode, table.lenght).
Nel nostro esempio, ipotizziamo che indexFor restituisca 2, la coppia <”chiaveUno”, “Pippo”> è inserita nel bucket 2.
Notare che per la chiave “chiaveUno” avrà sempre l’hashcode 1450, poi trasformato in 2, a prescindere dal numero di volte che richiamiamo il metodo.
Inseriamo ora la coppia <”chiaveDue”, “Pluto”>.
chiaveDue ritorna l’hashcode 2940 che, trasformato con indexFor, diventa 11. L’hashmap diventa:
Infine aggiungiamo la coppia <”chiaveTre”, “Paperino”>.
L’hashcode di chiaveTre è 1780 che, trasformato con indexFor, diventa 2, ma nel bucket 2 è gia presente una coppia!!!
Questa situazione è nota come problema delle collisioni, ossia, sui grandi numeri, due chiavi diverse possono avere lo stesso hashcode.
Per capire se si tratta della stessa chiave, l’hashmap richiama il metodo equals della chiave.
Se ritorna true il nuovo valore sovrascrive il vecchio:
altrimenti la nuova coppia viene aggiunto nello stesso bucket:
Quando dobbiamo estrarre, data una chiave x, un valore dall’hashtable, le operazioni seguite sono:
- Calcolare l’hashcode della chiave x
- Se nel bucket sono presenti più coppie <chiave, valore>, confrontare, tramite il metodo equals, la chiave x con tutte le altre, fino a trovare quella corretta, se esiste.
Notiamo che il metodo hashcode è anch’esso già presente nella classe Object, e di conseguenza in tutte le class, ma, per un corretto uso dell’hashmp è importante, per la classe che rappresenta la chiave, fare l’override dei metodi equals e hashCode, tenendo conto che:
- due oggetti uguali, quindi equals ritorna true, devono avere lo stesso codice hashcode.
- Se due oggetti non sono uguali, non per forza devono ritornare differenti hash
Non facendo l’override si usa l’hashcode della classe Object, che ritorna l’indirizzo di memoria dell’oggetto stesso.
Questo però potrebbe portare dei problemi perché l’indirizzo di memoria di un oggetto potrebbe cambiare nel tempo, ricordiamoci che è la JVM spesso rialloca in memoria tutti gli oggetti per una questione di ottimizzazione.
E se l’hashcode di una chiave varia nel tempo, non sarà più possibile recuperare la <coppia, valore>, non essendo più possibile individuare il bucket in cui è stata memorizzata.