HashMap?

Oggi andiamo ad approfondire insieme i concetti alla base di una delle strutture dati più usate in Java: le HashMap. Sì proprio loro: tutti le conosciamo, tutti le usiamo, ma internamente come funzionano? Scopriremo insieme che il loro comportamento è tutt’altro che scontato.

Aspetta, io non le conosco!

Per chi non le avesse mai usate le HashMap sono una implementazione contenuta nelle API Java dell’interfaccia java.util.Map. La mappa (chiamata Dictionary nel mondo .Net) non è altro che una collezione di oggetti il cui scopo principale è quello di rendere veloci ed efficienti operazioni quali inserimento e ricerca di elementi.

Per fare questo una mappa memorizza coppie (chiave, valore) e ha due implementazioni, del tutto generali: HashMap e TreeMap. Per approfondimenti potete consultare il nostro post sulle .

Esempio di utilizzo di HashMap

Vediamo come si utilizza una HashMap in Java utilizzando un :

public class HashMap1Test {

        private static Map capoluoghi = new HashMap<>();

        @BeforeClass
        public static void init() {
                capoluoghi.put("Toscana", "Firenze");
                capoluoghi.put("Lombardia", "Milano");
                capoluoghi.put("Sardegna", "Cagliari");

        }

        @Test
        public void utilizza() {
                Assert.assertEquals("Firenze", capoluoghi.get("Toscana"));
                Assert.assertEquals("Milano", capoluoghi.get("Lombardia"));
                Assert.assertEquals("Cagliari", capoluoghi.get("Sardegna"));

                Assert.assertNull(capoluoghi.get("Lazio"));

                capoluoghi.put("Lazio", "Roma");

                Assert.assertTrue(capoluoghi.containsKey("Lazio"));

                Assert.assertEquals("Roma", capoluoghi.get("Lazio"));

                capoluoghi.put("Lazio", "Roma2");

                Assert.assertEquals("Roma2", capoluoghi.get("Lazio"));

                Assert.assertEquals(4, capoluoghi.size());
        }
}

Come si può vedere l’utilizzo è molto semplice:

• 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;
• il metodo contains restituisce true se la mappa contiene la chiave passata come parametro, false altrimenti.

Sei sicuro che devo anche sapere come funzionano internamente?

Si dice di solito che le API si utilizzano prescindendo dalla loro implementazione: questa affermazione è sostanzialmente corretta. In questo caso però può valer la pena approfondire alcuni concetti che sono alla base della implementazione delle HashMap, in quanto in caso di problemi (comportamento diverso da quello atteso) capire cosa succede internamente alle classi che si utilizzano può aiutarci a uscire dall’empasse.

Javisti d’onore

Esiste un codice d’onore nell’implementazione dei metodi hashCode e equals che sta assiomaticamente alla base del fatto che ad esempio le HashMap funzionino correttamente: se due oggetti sono uguali devono avere lo stesso hashCode. Vediamo cosa succede se violo questo contratto: abbiamo una classe Citta e una classe Regione:

public class Citta {
        private final String cap;

        public Citta(String cap) {
                this.cap = cap;
        }

        public String getCap() {
                return cap;
        }

        @Override
        public int hashCode() {
                final int prime = 31;
                int result = 1;
                result = prime * result + ((cap == null) ? 0 : cap.hashCode());
                return result;
        }

        @Override
        public boolean equals(Object obj) {
                if (this == obj)
                        return true;
                if (obj == null)
                        return false;
                if (getClass() != obj.getClass())
                        return false;
                Citta other = (Citta) obj;
                if (cap == null) {
                        if (other.cap != null)
                                return false;
                } else if (!cap.equals(other.cap))
                        return false;
                return true;
        }
}

public class Regione {
        private final String nome;

        public Regione(String nome) {
                this.nome = nome;
        }

        public String getNome() {
                return nome;
        }

        @Override
        public boolean equals(Object obj) {
                if (this == obj)
                        return true;
                if (obj == null)
                        return false;
                if (getClass() != obj.getClass())
                        return false;
                Regione other = (Regione) obj;
                if (nome == null) {
                        if (other.nome != null)
                                return false;
                } else if (!nome.equals(other.nome))
                        return false;
                return true;
        }
}

Due città sono uguali se hanno lo stesso cap e in tal caso hanno anche lo stesso hashcode. Invece due regioni sono uguali se hanno lo stesso nome, ma hashCode non è ridefinito, quindi viene utilizzato quello di Object.

Se lanciamo il test seguente vediamo che viene eseguito con sucesso:

public class HashMap2Test {

        private static Map capoluoghi = new HashMap<>();

        private static Regione toscana;

        @BeforeClass
        public static void init() {
                Citta firenze = new Citta("50100");

                toscana = new Regione("Toscana");

                capoluoghi.put(toscana, firenze);
        }

                @Test
        public void utilizza() {
                Regione toscana2 = new Regione("Toscana");

                Assert.assertTrue(toscana2.hashCode() != toscana.hashCode());
                Assert.assertTrue(toscana2.equals(toscana));

                Assert.assertNull(capoluoghi.get(toscana2));
        }
}

Non viene infatti reperita la chiave toscana2 dentro alla mappa, anche se è vero che toscana2.equals(toscana). Questo accade perché quando utilizziamo il metodo put per inserire una nuova coppia (chiave, valore) nella mappa viene invocato il metodo hashCode sull’oggetto chiave: l’hashcode calcolato viene utilizzato per individuare un bucket, una locazione dove memorizzare il valore. In realtà, per essere precisi, nel bucket vengono memorizzati sia la chiave che il valore.

Abbiamo quindi imparato che se violiamo il contratto sulla chiave rischiamo di inserire nella mappa un oggetto, ma di non essere più in grado di reperirlo, in quanto la get andrebbe a cercarlo in un bucket diverso!

Collisione in vista!

Il contratto afferma che due oggetti uguali devono avere lo stesso hashcode. Nessun vincolo esiste sul fatto che due oggetti diversi debbano avere diverso hashcode e questa è una condizione difficilmente garantibile in modo assoluto.

Se ci troviamo in un (poco probabile) caso in cui due oggetti chiave diversi hanno stesso hashcode allora i due valori inseriti nella mappa sono memorizzati nello stesso bucket e si parla in questo caso di collisione; tuttavia il primo non viene sovrascritto: il secondo oggetto memorizzato viene inserito successivamente al primo in una lista linkata. Come viene individuato l’oggetto giusto da reperire dalla lista linkata quando utilizzo get in caso di collisione? Semplice, viene scorsa la lista utilizzando equals sull’oggetto chiave per reperire il valore corretto!

Vediamo un esempio: creiamo una classe Persona così fatta:

public class Persona {
        private final String nome;
        private final String cognome;

        public Persona(String nome, String cognome) {
                super();
                this.nome = nome;
                this.cognome = cognome;
        }

        public String getNome() {
                return nome;
        }

        public String getCognome() {
                return cognome;
        }

        @Override
        public int hashCode() {
                return 1;
        }

        @Override
        public boolean equals(Object obj) {
                if (this == obj)
                        return true;
                if (obj == null)
                        return false;
                if (getClass() != obj.getClass())
                        return false;
                Persona other = (Persona) obj;
                if (cognome == null) {
                        if (other.cognome != null)
                                return false;
                } else if (!cognome.equals(other.cognome))
                        return false;
                if (nome == null) {
                        if (other.nome != null)
                                return false;
                } else if (!nome.equals(other.nome))
                        return false;
                return true;
        }
}

Due persone sono uguali se hanno stesso nome e cognome: l’hashcode è uguale per tutte ed è pari ad 1 (non fatelo a casa!). Andiamo a lanciare ora la classe di JUnit test seguente:

public class HashMap3Test {

        // per ogni persona memorizzo nella mappa la sua età
        private static Map people = new HashMap<>();

        @BeforeClass
        public static void init() {
                Persona manuele = new Persona("Manuele", "Piastra");
                Persona andrea = new Persona("Andrea", "Como");
                Persona fabio = new Persona("Fabio", "Collini");

                people.put(manuele, 38);
                people.put(andrea, 31);
                people.put(fabio, 33);
        }

        @Test
        public void utilizza() {

                Assert.assertTrue(people.get(new Persona("Manuele", "Piastra")).equals(
                                38));
                Assert.assertTrue(people.get(new Persona("Andrea", "Como")).equals(31));
                Assert.assertTrue(people.get(new Persona("Fabio", "Collini"))
                                .equals(33));
        }
}

Come vediamo la put e la get funzionano correttamente, ma i tre valori che andiamo ad inserire si trovano tutti nello stesso bucket.

Ovviamente se ci mettiamo in condizioni di probabile collisione le prestazioni quando preleviamo elementi dalla HashMap degradano notevolmente, in quanto ci troviamo a dover scorrere una lunga lista linkata.

Vediamo un esempio: creiamo una nuova classe, Persona2, esattamente identica a Persona, a parte il fatto che implementa un metodo hashCode appropriato (il modo migliore di ridefinire hashCode e equals è quello di farlo fare a Eclipse: source -> Generate hashCode() and equals()…) :

...   ...
@Override
        public int hashCode() {
                final int prime = 31;
                int result = 1;
                result = prime * result + ((cognome == null) ? 0 : cognome.hashCode());
                result = prime * result + ((nome == null) ? 0 : nome.hashCode());
                return result;
        }
...   ...

Ora creiamo la seguente classe e lanciamo i JUnit Test:

public class HashMap4Test {

        private static Map people = new HashMap<>();

        private static Map people2 = new HashMap<>();

        @BeforeClass
        public static void init() {
                for (int i = 0; i < 10000; i++) {
                        people.put(new Persona(String.valueOf(i), String.valueOf(i)), i);
                        people2.put(new Persona2(String.valueOf(i), String.valueOf(i)), i);
                }
        }

        @Test
        public void getPeople() {

                for (int i = 0; i < 10000; i++) {
                        people.get(new Persona(String.valueOf(i), String.valueOf(i)));
                }
        }

        @Test
        public void getPeople2() {

                for (int i = 0; i < 10000; i++) {
                        people2.get(new Persona2(String.valueOf(i), String.valueOf(i)));
                }
        }
}

Il test getPeople() gira in 2.286s sulla mia macchina, mentre getPeople2() gira in 0.009s: 254 volte più veloce!

Aspetta, prima di andare: devo usare HashMap o HashTable?

Questa è una domanda molto ricorrente sul web. Le differenze principali sono:

• in HashMap è possibile inserire valori null, in HashTable no;
• HashTable è sincronizzata, HashMap non lo è.

In generale è preferibile utilizzare HashMap che è l’implementazione più recente e consigliata dalla stessa Oracle.

Conclusioni

Le mappe sono strutture dati potenti e performanti quando sono frequenti le operazioni di inserimento e di ricerca. Tuttavia bisogna essere molto scrupolosi con le implementazioni di hashCode e equals per l’oggetto chiave per evitare comportamenti non desiderati e/o poco performanti.

Alla prossima.