Java: le tabelle hash [guida]

Una tabella hash è una struttura dati che associa chiavi uniche a valori. Immagina un grande archivio dove, invece di cercare tutto riga per riga, usi una “funzione hash” per trovare immediatamente la posizione del dato che ti interessa.

Cos’è una tabella hash?

È una struttura dati che mappa (nel senso che collega, unisce tra loro) una chiave a un valore.

Es: numero di telefono (valore) associato a un nome (chiave).

Perché usare una tabella hash?

  • Accesso rapidissimo ai dati tramite chiave
  • Ottima per cercare, inserire o cancellare elementi in modo efficiente
  • Usata per implementare dizionari, rubrica, cache e molto altro

Come funziona la tabella hash

  1. Tu dai una chiave (es. “Marco”)
  2. La tabella applica una funzione hash (una specie di trasformazione) alla chiave, che genera un indice
  3. Usa quell’indice per trovare la posizione dove è memorizzato il valore (es. l’età di Marco)

La classe HashMap in Java

In Java, la tabella hash si usa tramite la classe HashMap (fa parte del package java.util).

Caratteristiche:

  • Permette di mappare chiavi (di tipo generico K) a valori (di tipo V)
  • Non mantiene l’ordine degli elementi
  • Supporta chiavi e valori null
  • Accesso e inserimento in media molto veloci (complessità O(1))

Sintassi base

HashMap<K, V> nomeMappa = new HashMap<>();
  • K = tipo chiave (es. String)
  • V = tipo valore (es. Integer)

Operazioni principali

OperazioneMetodoDescrizione
Inserire o aggiornareput(K chiave, V valore)Aggiunge o sovrascrive valore
Ottenere valoreget(K chiave)Restituisce valore associato
Verificare chiavecontainsKey(K chiave)Controlla se la chiave esiste
Rimuovere coppiaremove(K chiave)Elimina chiave e valore
Ottenere dimensionesize()Numero coppie chiave-valore
Ottenere chiavikeySet()Set di tutte le chiavi

Esempio pratico minimal

Hashtable senza collisioni

public class HashTable {
String[] keys = new String[10];
int[] vals = new int[10];

int hash(String k) { return Math.abs(k.hashCode()) % keys.length; }

void put(String k, int v) {
int i = hash(k);
keys[i] = k;
vals[i] = v;
}

Integer get(String k) {
int i = hash(k);
return (keys[i] != null && keys[i].equals(k)) ? vals[i] : null;
}

public static void main(String[] args) {
HashTable ht = new HashTable();
ht.put("A", 1);
ht.put("B", 2);
System.out.println(ht.get("A")); // 1
System.out.println(ht.get("B")); // 2
System.out.println(ht.get("C")); // null
}
}

Esempio più avanzato

import java.util.HashMap;

public class EsempioHashMap {
    public static void main(String[] args) {
        HashMap<String, Integer> etàPersone = new HashMap<>();

        etàPersone.put("Alice", 28);
        etàPersone.put("Bob", 35);

        System.out.println("Età di Alice: " + etàPersone.get("Alice"));
        System.out.println("Chiavi nella mappa: " + etàPersone.keySet());
    }
}

Quando usare una HashMap

  • Quando ti serve cercare velocemente dati tramite una chiave
  • Quando non importa l’ordine degli elementi
  • Quando vuoi una struttura facile da usare e performante per associazioni chiave/valore

Esempio minimal

Ecco un esempio minimale e funzionale di HashMap in Java, che mostra come aggiungere, leggere e stampare valori associati a chiavi:

import java.util.HashMap;

public class HashMapMinimale {
    public static void main(String[] args) {
        HashMap<String, Integer> mappa = new HashMap<>();

        mappa.put("Alice", 25);
        mappa.put("Bob", 30);

        System.out.println("Alice ha " + mappa.get("Alice") + " anni.");
        System.out.println("Bob ha " + mappa.get("Bob") + " anni.");
    }
}

Compila e avvia così:

javac HashMapMinimale.java
java HashMapMinimale

Output:

Alice ha 25 anni.
Bob ha 30 anni.

In Java: HashMap

La classe più usata è HashMap, che fa proprio questo:

  • HashMap<K, V> dove K è tipo chiave e V è tipo valore.

Esempio

import java.util.HashMap;

public class HashMapDemo {
    public static void main(String[] args) {
        HashMap<String, Integer> mappa = new HashMap<>();

        // aggiungi coppie chiave-valore
        mappa.put("Alice", 25);
        mappa.put("Marco", 30);
        mappa.put("Luca", 28);

        // prendi un valore da una chiave
        System.out.println("Età di Marco: " + mappa.get("Marco"));

        // verifica se una chiave esiste
        if (mappa.containsKey("Alice")) {
            System.out.println("Alice è nella mappa");
        }

        // rimuovi una coppia
        mappa.remove("Luca");

        // stampa tutte le chiavi e valori
        for (String nome : mappa.keySet()) {
            System.out.println(nome + " ha " + mappa.get(nome) + " anni.");
        }
    }
}

Metodi utili di HashMap

MetodoDescrizione
put(K chiave, V valore)Aggiunge o aggiorna una coppia
get(K chiave)Restituisce valore associato
remove(K chiave)Rimuove coppia per chiave
containsKey(K chiave)Verifica esistenza chiave
size()Numero coppie presenti
clear()Pulisce tutta la mappa
keySet()Insieme di tutte le chiavi
values()Collezione di tutti i valori

HashMap con oggetti personalizzati

Puoi anche usare anche oggetti come chiave o valore, ma se usi oggetti come chiavi, devi implementare hashCode() e equals() nella classe chiave, altrimenti rischi problemi.

Assolutamente! Quando usi oggetti personalizzati come chiavi in una HashMap (o in qualsiasi tabella hash in Java), devi implementare correttamente i metodi hashCode() e equals() nella classe chiave. Questo perché:

  • hashCode() determina in quale “secchio” (bucket) va messa la chiave nella tabella hash
  • equals() serve per distinguere due oggetti diversi ma con stesso hash (collisione)

Se non li implementi, due oggetti con stessi valori potrebbero non essere riconosciuti come uguali, causando problemi nella ricerca o inserimento. Supponiamo di avere una classe semplice Punto (x,y), che vogliamo usare come chiave.

Senza hashCode() e equals() (NON funziona bene):

import java.util.HashMap;

class Punto {
    int x, y;

    Punto(int x, int y) {
        this.x = x; this.y = y;
    }
}

public class EsempioMappa {
    public static void main(String[] args) {
        HashMap<Punto, String> mappa = new HashMap<>();

        Punto p1 = new Punto(1, 2);
        Punto p2 = new Punto(1, 2);

        mappa.put(p1, "Primo punto");

        // p2 ha gli stessi valori di p1, ma è un oggetto diverso
        System.out.println(mappa.get(p2)); // stampa null, NON trova p2!
    }
}

Con hashCode() e equals() corretti (FUNZIONA):

import java.util.HashMap;
import java.util.Objects;

class Punto {
    int x, y;

    Punto(int x, int y) {
        this.x = x; this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;                 // stessa istanza
        if (o == null || getClass() != o.getClass()) return false; // classe diversa
        Punto punto = (Punto) o;
        return x == punto.x && y == punto.y;       // valori uguali
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

public class EsempioMappa {
    public static void main(String[] args) {
        HashMap<Punto, String> mappa = new HashMap<>();

        Punto p1 = new Punto(1, 2);
        Punto p2 = new Punto(1, 2);

        mappa.put(p1, "Primo punto");

        System.out.println(mappa.get(p2)); // stampa "Primo punto" — funziona!
    }
}

In questo caso:

  • hashCode() restituisce un codice (int) basato su x e y
  • equals() dice se due oggetti Punto sono uguali confrontando x e y
  • Ora p1 e p2 sono considerati uguali come chiave nella HashMap
Tag: