Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Impara Lavorare con HashMap in Java | Padronanza Delle Mappe in Java
Strutture Dati Java

bookLavorare con HashMap in Java

Ora, esaminiamo più da vicino la classe che implementa l'interfaccia Map — HashMap.

Questa classe è ampiamente utilizzata quando si parla di mappe. Hai già avuto modo di lavorare con questa classe e studiare i suoi metodi. Ma scopriamo come funziona effettivamente questa classe.

Per prima cosa, è necessario comprendere cosa sia un hash code, poiché viene utilizzato internamente in una HashMap.

Hash Code

Ogni oggetto possiede il proprio hash code, che può essere ottenuto utilizzando il metodo Object della classe hashCode(). Vediamo un esempio:

Main.java

Main.java

copy

              
123456789

            
package com.example;

public class Main {
    public static void main(String[] args) {
        String example = "Hello World!";
        int hash = example.hashCode();
        System.out.println("HashCode: " + hash);
    }
}

Come puoi vedere, l'oggetto String con il dato "Hello World!" ha un hash code di "-969099747". Il metodo che determina esattamente quale hash code verrà sovrascritto nella classe String è il seguente:

Main.java

Main.java

copy

              
1234567

            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

L'oggetto String viene suddiviso in un array di byte utilizzando il metodo getBytes(), dopodiché ogni byte viene elaborato e aggiunto al codice hash. In questo modo, il codice hash diventa massimamente unico, aiutando il programma a identificare questo oggetto.

Per gli oggetti di classi personalizzate, è possibile anche sovrascrivere il codice hash definendo un modo unico per ottenere questo numero. Creiamo una classe di test User e sovrascriviamo il metodo hash code per essa.

Main.java

Main.java

copy

              
12345678910111213141516171819202122232425262728293031

            
package com.example;

class User {
    String name;
    int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int h = 0;
        byte[] array = name.getBytes();
        for (byte element :
                array) {
            h += element * age + (age * 15);
        }
        return h;
    }
}

public class Main {
    public static void main(String[] args) {
        User user1 = new User("Bob", 13);
        User user2 = new User("Alice", 20);
        System.out.println("First user's hash code: " + user1.hashCode());
        System.out.println("Second user's hash code: " + user2.hashCode());
    }
}

Nella classe User sono presenti 2 attributi che ho utilizzato nel metodo hashCode(). Ho scelto operazioni casuali nel metodo hashCode() per ottenere un numero il più casuale possibile, rendendolo unico per ogni oggetto User.

Questo è esattamente il codice hash. Ora vediamo come viene utilizzato in una HashMap.

HashMap

Un HashMap può essere visualizzato come un array di bucket. Un bucket è una lista in cui viene memorizzato un elemento. Inizialmente, il HashMap dispone di 16 bucket, che rappresentano il DEFAULT_INITIAL_CAPACITY.

Quando si inserisce un elemento nel HashMap utilizzando il metodo put(), il HashMap deve determinare in quale bucket specifico posizionare questo elemento. Lo fa utilizzando una semplice formula: keyValue.hashCode() & (n - 1), dove n è la dimensione dell'array di bucket nel HashMap. '&' è un'operazione bitwise AND, che rappresenta una programmazione di basso livello, quindi non entreremo nei dettagli.

È importante comprendere che il HashMap utilizza l'hash code del valore della chiave per trovare il bucket appropriato. Pertanto, è fondamentale creare un hash code il più possibile unico per evitare collisioni.

Collisione

Per quanto un hash code possa essere unico, può comunque verificarsi una situazione in cui l'HashMap calcola lo stesso bucket per due elementi. In questi casi, si verifica una collisione. In termini semplici, una collisione è una situazione in cui due o più elementi finiscono nello stesso bucket. Essi vengono memorizzati come un SinglyLinkedList, che hai implementato in precedenza.

Vediamo un'illustrazione:

La collisione non è favorevole poiché influisce sull'ottimizzazione. Se osservi questa tabella, vedrai che nel migliore dei casi, l'HashMap ha complessità algoritmica costante, mentre nel peggiore dei casi è lineare. Questa complessità algoritmica lineare deriva da collisioni significative. Pertanto, si consiglia di utilizzare chiavi con hash code il più possibile unici per evitare collisioni.

Come Gestisce le Collisioni HashMap?

HashMap gestisce anche le collisioni tramite la ridimensionamento costante dell'array dei bucket. Quando il numero di elementi raggiunge il 75% della dimensione dell'array dei bucket, HashMap attiva un ridimensionamento raddoppiando la dimensione dell'array dei bucket. Successivamente, ridistribuisce gli elementi nei nuovi bucket utilizzando il nuovo valore di n nella formula.

Quindi, HashMap è una struttura dati altamente ottimizzata ed è spesso utilizzata come implementazione principale dell'interfaccia Map.

Perché È Importante Conoscere Tutto Questo?

Questa è una teoria di programmazione a basso livello importante perché, quando si lavora con grandi insiemi di dati, le strutture dati possono influenzare significativamente le prestazioni dell'applicazione. Questo accade quando queste strutture dati vengono utilizzate in modo errato.

L'uso improprio delle strutture dati si verifica perché i programmatori non comprendono come funzionano queste strutture dati. Dopotutto, vuoi diventare un buon programmatore, giusto?

Inoltre, domande sulle strutture dati vengono spesso poste nei colloqui.

Se sei interessato ad approfondire il funzionamento interno di HashMap, puoi consultare la documentazione Java in IntelliJ IDEA.

In IntelliJ IDEA, tieni premuto Ctrl (Windows/Linux) o Command (macOS) e clicca sul nome della classe per navigare alla sua definizione e vedere tutti i metodi disponibili.

1. Quale delle seguenti implementazioni utilizza una tabella hash per memorizzare coppie chiave-valore?

2. In un HashMap, cosa succede se due chiavi hanno lo stesso hash code?

question mark

Quale delle seguenti implementazioni utilizza una tabella hash per memorizzare coppie chiave-valore?

Select the correct answer

question mark

In un HashMap, cosa succede se due chiavi hanno lo stesso hash code?

Select the correct answer

Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 3. Capitolo 2

Chieda ad AI

expand

Chieda ad AI

ChatGPT

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

Suggested prompts:

Can you explain more about how hash codes are generated in Java?

What happens if two objects have the same hash code in a HashMap?

Why is it important to override the hashCode() method in custom classes?

bookLavorare con HashMap in Java

Scorri per mostrare il menu

Ora, esaminiamo più da vicino la classe che implementa l'interfaccia Map — HashMap.

Questa classe è ampiamente utilizzata quando si parla di mappe. Hai già avuto modo di lavorare con questa classe e studiare i suoi metodi. Ma scopriamo come funziona effettivamente questa classe.

Per prima cosa, è necessario comprendere cosa sia un hash code, poiché viene utilizzato internamente in una HashMap.

Hash Code

Ogni oggetto possiede il proprio hash code, che può essere ottenuto utilizzando il metodo Object della classe hashCode(). Vediamo un esempio:

Main.java

Main.java

copy

              
123456789

            
package com.example;

public class Main {
    public static void main(String[] args) {
        String example = "Hello World!";
        int hash = example.hashCode();
        System.out.println("HashCode: " + hash);
    }
}

Come puoi vedere, l'oggetto String con il dato "Hello World!" ha un hash code di "-969099747". Il metodo che determina esattamente quale hash code verrà sovrascritto nella classe String è il seguente:

Main.java

Main.java

copy

              
1234567

            
public static int hashCode(byte[] value) {
    int h = 0;
    for (byte v : value) {
        h = 31 * h + (v & 0xff);
    }
    return h;
}

L'oggetto String viene suddiviso in un array di byte utilizzando il metodo getBytes(), dopodiché ogni byte viene elaborato e aggiunto al codice hash. In questo modo, il codice hash diventa massimamente unico, aiutando il programma a identificare questo oggetto.

Per gli oggetti di classi personalizzate, è possibile anche sovrascrivere il codice hash definendo un modo unico per ottenere questo numero. Creiamo una classe di test User e sovrascriviamo il metodo hash code per essa.

Main.java

Main.java

copy

              
12345678910111213141516171819202122232425262728293031

            
package com.example;

class User {
    String name;
    int age;

    public User(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public int hashCode() {
        int h = 0;
        byte[] array = name.getBytes();
        for (byte element :
                array) {
            h += element * age + (age * 15);
        }
        return h;
    }
}

public class Main {
    public static void main(String[] args) {
        User user1 = new User("Bob", 13);
        User user2 = new User("Alice", 20);
        System.out.println("First user's hash code: " + user1.hashCode());
        System.out.println("Second user's hash code: " + user2.hashCode());
    }
}

Nella classe User sono presenti 2 attributi che ho utilizzato nel metodo hashCode(). Ho scelto operazioni casuali nel metodo hashCode() per ottenere un numero il più casuale possibile, rendendolo unico per ogni oggetto User.

Questo è esattamente il codice hash. Ora vediamo come viene utilizzato in una HashMap.

HashMap

Un HashMap può essere visualizzato come un array di bucket. Un bucket è una lista in cui viene memorizzato un elemento. Inizialmente, il HashMap dispone di 16 bucket, che rappresentano il DEFAULT_INITIAL_CAPACITY.

Quando si inserisce un elemento nel HashMap utilizzando il metodo put(), il HashMap deve determinare in quale bucket specifico posizionare questo elemento. Lo fa utilizzando una semplice formula: keyValue.hashCode() & (n - 1), dove n è la dimensione dell'array di bucket nel HashMap. '&' è un'operazione bitwise AND, che rappresenta una programmazione di basso livello, quindi non entreremo nei dettagli.

È importante comprendere che il HashMap utilizza l'hash code del valore della chiave per trovare il bucket appropriato. Pertanto, è fondamentale creare un hash code il più possibile unico per evitare collisioni.

Collisione

Per quanto un hash code possa essere unico, può comunque verificarsi una situazione in cui l'HashMap calcola lo stesso bucket per due elementi. In questi casi, si verifica una collisione. In termini semplici, una collisione è una situazione in cui due o più elementi finiscono nello stesso bucket. Essi vengono memorizzati come un SinglyLinkedList, che hai implementato in precedenza.

Vediamo un'illustrazione:

La collisione non è favorevole poiché influisce sull'ottimizzazione. Se osservi questa tabella, vedrai che nel migliore dei casi, l'HashMap ha complessità algoritmica costante, mentre nel peggiore dei casi è lineare. Questa complessità algoritmica lineare deriva da collisioni significative. Pertanto, si consiglia di utilizzare chiavi con hash code il più possibile unici per evitare collisioni.

Come Gestisce le Collisioni HashMap?

HashMap gestisce anche le collisioni tramite la ridimensionamento costante dell'array dei bucket. Quando il numero di elementi raggiunge il 75% della dimensione dell'array dei bucket, HashMap attiva un ridimensionamento raddoppiando la dimensione dell'array dei bucket. Successivamente, ridistribuisce gli elementi nei nuovi bucket utilizzando il nuovo valore di n nella formula.

Quindi, HashMap è una struttura dati altamente ottimizzata ed è spesso utilizzata come implementazione principale dell'interfaccia Map.

Perché È Importante Conoscere Tutto Questo?

Questa è una teoria di programmazione a basso livello importante perché, quando si lavora con grandi insiemi di dati, le strutture dati possono influenzare significativamente le prestazioni dell'applicazione. Questo accade quando queste strutture dati vengono utilizzate in modo errato.

L'uso improprio delle strutture dati si verifica perché i programmatori non comprendono come funzionano queste strutture dati. Dopotutto, vuoi diventare un buon programmatore, giusto?

Inoltre, domande sulle strutture dati vengono spesso poste nei colloqui.

Se sei interessato ad approfondire il funzionamento interno di HashMap, puoi consultare la documentazione Java in IntelliJ IDEA.

In IntelliJ IDEA, tieni premuto Ctrl (Windows/Linux) o Command (macOS) e clicca sul nome della classe per navigare alla sua definizione e vedere tutti i metodi disponibili.

1. Quale delle seguenti implementazioni utilizza una tabella hash per memorizzare coppie chiave-valore?

2. In un HashMap, cosa succede se due chiavi hanno lo stesso hash code?

question mark

Quale delle seguenti implementazioni utilizza una tabella hash per memorizzare coppie chiave-valore?

Select the correct answer

question mark

In un HashMap, cosa succede se due chiavi hanno lo stesso hash code?

Select the correct answer

Tutto è chiaro?

Come possiamo migliorarlo?

Grazie per i tuoi commenti!

Sezione 3. Capitolo 2
some-alt