Il Linguaggio di Programmazione Rust

Memorizzare Chiavi con Valori Associati in Mappe Hash

L’ultima delle nostre collezioni comuni è la mappa hash. Il type HashMap<K, V> memorizza una mappatura di chiavi di type K a valori di type V utilizzando una funzione di hashing, che determina come queste chiavi e valori vengono inseriti in memoria. Molti linguaggi di programmazione supportano questo tipo di struttura dati, ma spesso usano un nome diverso, come hash, map, object, hash table, dictionary o associative array, solo per citarne alcuni.

Le mappe hash (hash map d’ora in poi) sono utili quando si desidera ricercare dati non utilizzando un indice, come è possibile con i vettori, ma utilizzando una chiave che può essere di qualsiasi type. Ad esempio, in una partita, è possibile tenere traccia del punteggio di ogni squadra in una hash map in cui ogni chiave è il nome di una squadra e i valori sono il punteggio di ogni squadra. Dato il nome di una squadra, è possibile recuperarne il punteggio.

In questa sezione esamineremo l’API di base delle hash map, ma molte altre funzionalità si nascondono nelle funzioni definite su HashMap<K, V> dalla libreria standard. Come sempre, consultate la documentazione della libreria standard per ulteriori informazioni.

Creare una Nuova Hash Map

Un modo per creare una hash map vuota è usare new e aggiungere elementi con insert. Nel Listato 8-20, stiamo tenendo traccia del punteggio di due squadre i cui nomi sono Blu e Gialla. La squadra Blu inizia con 10 punti, mentre la squadra Gialla inizia con 50.

fn main() {
    use std::collections::HashMap;

    let mut punteggi = HashMap::new();

    punteggi.insert(String::from("Blu"), 10);
    punteggi.insert(String::from("Gialla"), 50);
}

Nota che dobbiamo prima portare in scope HashMap con use dalla sezione dedicata alle collezioni della libreria standard. Delle nostre tre collezioni comuni, questa è la meno utilizzata, quindi non è inclusa nelle funzionalità aggiunte allo scope dal preludio. Le hash map hanno anche un supporto minore dalla libreria standard; ad esempio, non esiste una macro integrata per costruirle.

Proprio come i vettori, le hash map memorizzano i loro dati nell’heap. Questa HashMap ha chiavi di type String e valori di type i32. Come i vettori, le hash map sono omogenee: tutte le chiavi devono avere lo stesso type e tutti i valori devono avere lo stesso type.

Accedere ai Valori in una Hash Map

Possiamo ottenere un valore dalla hash map fornendo la sua chiave al metodo get, come mostrato nel Listato 8-21.

fn main() {
    use std::collections::HashMap;

    let mut punteggi = HashMap::new();

    punteggi.insert(String::from("Blu"), 10);
    punteggi.insert(String::from("Gialla"), 50);

    let nome_squadra = String::from("Blu");
    let punteggio = punteggi.get(&nome_squadra).copied().unwrap_or(0);
}

Qui, punteggio avrà il valore associato alla squadra Blu e il risultato sarà 10. Il metodo get restituisce Option<&V>; se non c’è alcun valore per quella chiave nella hash map, get restituirà None. Questo programma gestisce Option chiamando copied per ottenere Option<i32> anziché Option<&i32>, quindi unwrap_or per impostare punteggio a zero se punteggio non ha una voce per la chiave.

Possiamo iterare su ogni coppia chiave-valore in una hash map in modo simile a come facciamo con i vettori, utilizzando un ciclo for:

fn main() {
    use std::collections::HashMap;

    let mut punteggi = HashMap::new();

    punteggi.insert(String::from("Blu"), 10);
    punteggi.insert(String::from("Gialla"), 50);

    for (chiave, valore) in &punteggi {
        println!("{chiave}: {valore}");
    }
}

Questo codice stamperà ogni coppia in un ordine arbitrario:

Gialla: 50
Blu: 10

Gestire Ownership nelle Hash Map

Per i type che implementano il trait Copy, come i32, i valori vengono copiati nella hash map. Per i valori con ownership come String, i valori verranno spostati e la hash map assumerà la ownership di tali valori, come dimostrato nel Listato 8-22.

fn main() {
    use std::collections::HashMap;

    let nome_campo = String::from("Colore preferito");
    let valore_campo = String::from("Blu");

    let mut map = HashMap::new();
    map.insert(nome_campo, valore_campo);
    // `nome_campo` e `valore_campo` non sono validi a questo punto,
    // prova a usarli e vedi quale errore di compilazione ottieni!
}

Non possiamo utilizzare le variabili nome_campo e valore_campo dopo che sono state spostate nella hash map con la chiamata a insert.

Se inseriamo reference a valori nella hash map, i valori non verranno spostati nella hash map. I valori a cui puntano i reference devono essere validi almeno per il tempo in cui è valida la hash map. Approfondiremo questi argomenti nella sezione “Validare i Reference con la Lifetime” del Capitolo 10.

Aggiornare una Hash Map

Sebbene il numero di coppie chiave-valore sia espandibile, a ogni chiave univoca può essere associato un solo valore alla volta (ma non viceversa: ad esempio, sia la squadra Blu che quella Gialla potrebbero avere il valore 10 memorizzato nella hash map punteggi).

Quando si desidera modificare i dati in una hash map, è necessario decidere come gestire il caso in cui a una chiave sia già assegnato un valore. È possibile sostituire il vecchio valore con il nuovo valore, ignorando completamente il vecchio valore. È possibile mantenere il vecchio valore e ignorare il nuovo valore, aggiungendo il nuovo valore solo se la chiave non ha già un valore. Oppure è possibile combinare il vecchio valore e il nuovo valore. Vediamo come fare ciascuna di queste cose!

Sovrascrivere un Valore

Se inseriamo una chiave e un valore in una hash map e poi inseriamo la stessa chiave con un valore diverso, il valore associato a quella chiave verrà sostituito. Anche se il codice nel Listato 8-23 chiama insert due volte, la hash map conterrà solo una coppia chiave-valore perché stiamo inserendo il valore per la chiave della squadra Blu entrambe le volte.

fn main() {
    use std::collections::HashMap;

    let mut punteggi = HashMap::new();

    punteggi.insert(String::from("Blu"), 10);
    punteggi.insert(String::from("Blu"), 25);

    println!("{punteggi:?}");
}

Questo codice stamperà {"Blu": 25}. Il valore originale di 10 è stato sovrascritto.

Aggiungere una Chiave e un Valore Solo Se una Chiave Non è Presente

È comune verificare se una particolare chiave esiste già nella hash map con un valore e quindi eseguire le seguenti azioni: se la chiave esiste nella hash map, il valore esistente deve rimanere invariato; se la chiave non esiste, inserirla e assegnarle un valore.

Le hash map dispongono di un’API speciale per questo scopo, chiamata entry, che accetta la chiave che si desidera controllare come parametro. Il valore restituito dal metodo entry è un’enum chiamato Entry che rappresenta un valore che potrebbe esistere o meno. Supponiamo di voler verificare se la chiave per la squadra Gialla ha un valore associato. In caso contrario, vogliamo inserire il valore 50, e lo stesso vale per la squadra Blu. Utilizzando l’API entry, il codice appare come nel Listato 8-24.

fn main() {
    use std::collections::HashMap;

    let mut punteggi = HashMap::new();
    punteggi.insert(String::from("Blu"), 10);

    punteggi.entry(String::from("Gialla")).or_insert(50);
    punteggi.entry(String::from("Blu")).or_insert(50);

    println!("{punteggi:?}");
}

Il metodo or_insert su Entry è definito per restituire un reference mutabile al valore della chiave Entry corrispondente se tale chiave esiste, e in caso contrario, inserisce il parametro come nuovo valore per questa chiave e restituisce un reference mutabile al nuovo valore. Questa tecnica è molto più pulita rispetto alla scrittura manuale della logica e, inoltre, si integra meglio con il borrow checker.

L’esecuzione del codice nel Listato 8-24 stamperà {"Gialla": 50, "Blu": 10}. La prima chiamata a entry inserirà la chiave per la squadra Gialla con il valore 50 perché la squadra Gialla non ha già un valore. La seconda chiamata a entry non modificherà la hash map perché la squadra Blu ha già il valore 10.

Aggiornare un Valore in Base al Valore Precedente

Un altro caso d’uso comune per le hash map è cercare il valore di una chiave e quindi aggiornarlo in base al valore precedente. Ad esempio, il Listato 8-25 mostra un codice che conta quante volte ogni parola appare in un testo. Utilizziamo una hash map con le parole come chiavi e incrementiamo il valore per tenere traccia di quante volte abbiamo visto quella parola. Quando incontriamo una parola nuova, verrà inserita inizializzando il valore associato a 0.

fn main() {
    use std::collections::HashMap;

    let testo = "hello world wonderful world";

    let mut map = HashMap::new();

    for parola in testo.split_whitespace() {
        let conteggio = map.entry(parola).or_insert(0);
        *conteggio += 1;
    }

    println!("{map:?}");
}

Questo codice stamperà {"world": 2, "hello": 1, "wonderful": 1}. Potresti vedere le stesse coppie chiave-valore stampate in un ordine diverso: ricorda che, come menzionato precedentemente in “Accesso ai Valori in una Hash Map”, l’iterazione su una hash map avviene in un ordine arbitrario.

Il metodo split_whitespace restituisce un iteratore su slice, separate da spazi, del valore in testo. Il metodo or_insert restituisce un reference mutabile (&mut V) al valore della chiave specificata. Qui, memorizziamo quel reference mutabile nella variabile conteggio, quindi per assegnare quel valore, dobbiamo prima de-referenziare conteggio usando l’asterisco (*). Il reference mutabile esce dallo scope alla fine del ciclo for, quindi tutte queste modifiche sono sicure e consentite dalle regole di prestito.

Funzioni di Hashing

Come impostazione predefinita, HashMap utilizza una funzione di hashing chiamata SipHash che può fornire resistenza agli attacchi denial-of-service (DoS) che coinvolgono tabelle di hash¹. Questo non è l’algoritmo di hashing più veloce disponibile, ma è un buon compromesso in termini di maggiore sicurezza che ne deriva, nonostante il costo prestazionale derivato. Se si profila il codice e si scopre che la funzione di hashing predefinita è troppo lenta per i propri scopi, è possibile passare a un’altra funzione specificando un hasher diverso. Un hasher è un type che implementa il trait BuildHasher. Parleremo dei trait e di come implementarli nel Capitolo 10. Non è necessario implementare il proprio hasher da zero; crates.io offre librerie condivise da altri utenti Rust che forniscono hasher che implementano molti algoritmi di hashing comuni.

Riepilogo

Vettori, stringhe e hash map forniranno una grande quantità di funzionalità necessarie nei programmi quando avrai necessità di memorizzare, accedere e modificare dati. Ecco alcuni esercizi che ora dovresti essere in grado di risolvere:

1. Dato un elenco di interi, usa un vettore e restituisci la mediana (quando ordinati, il valore in posizione centrale) e la moda (il valore che ricorre più spesso; una hash map sarà utile in questo caso) dell’elenco.
2. Converti delle stringhe in pig latin. La prima consonante di ogni parola viene spostata alla fine della parola e viene aggiunto ay, quindi primo diventa rimo-pay. Le parole che iniziano con una vocale hanno invece hay aggiunto alla fine (ananas diventa ananas-hay). Tieni a mente i dettagli sulla codifica UTF-8!
3. Utilizzando hash map e vettori, crea un’interfaccia testuale che consenta a un utente di aggiungere i nomi dei dipendenti a un reparto di un’azienda; ad esempio, “Aggiungi Sally a Ingegneria” o “Aggiungi Amir a Vendite”. Quindi, consenti all’utente di recuperare un elenco di tutte le persone in un reparto o di tutte le persone in azienda per reparto, ordinate alfabeticamente.

La documentazione API della libreria standard descrive i metodi di vettori, stringhe e hash map che saranno utili per questi esercizi!

Stiamo entrando in programmi più complessi in cui le operazioni possono fallire, quindi è il momento perfetto per discutere della gestione degli errori. Lo faremo in seguito!

1. SipHash su wikipedia (eng) ↩