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 realmente 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


              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


              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, è anche possibile 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


              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 collocare 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 approfondiremo i dettagli.

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

Collisione

Nonostante un codice hash sia 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 una SinglyLinkedList, che hai implementato in precedenza.

Osserviamo un'illustrazione:

La collisione non è favorevole poiché influisce sull'ottimizzazione. Se osservi questa tabella, noterai che nel miglior caso, l'HashMap presenta complessità algoritmica costante, mentre nel peggior caso è lineare. Questa complessità algoritmica lineare deriva da collisioni significative. Pertanto, si consiglia di utilizzare chiavi con codici hash il più possibile unici per evitare collisioni.

Come gestisce le collisioni HashMap?

HashMap gestisce anche le collisioni tramite 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.

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

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?

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 1. Capitolo 14

Chieda ad AI

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

Sezione 1. Capitolo 14

Lavorare con HashMap in Java

Hash Code

HashMap

Collisione

Come gestisce le collisioni HashMap?

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?

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