Corso Gratuito di Programmazione Rust Lezione 030 – Memorizzazione di chiavi con valori associati in mappe Hash

SE VUOI PRENDERE LA CERTIFICAZIONE PER QUESTO CORSO CLICCA QUI

Memorizzazione delle Chiavi con Valori Associati in Mappe Hash

L’ultima delle nostre comuni collezioni è la mappa hash. Il tipo HashMap<K, V> memorizza una mappatura di chiavi di tipo K a valori di tipo V utilizzando una funzione hash, che determina come colloca queste chiavi e valori in memoria. Molte lingue di programmazione supportano questo tipo di struttura dati, ma spesso usano un nome diverso, come hash, mappa, oggetto, tabella hash, dizionario o array associativo, solo per citarne alcuni.

Le mappe hash sono utili quando vuoi cercare dati non usando un indice, come puoi fare con i vettori, ma usando una chiave che può essere di qualsiasi tipo. Ad esempio, in un gioco, potresti tenere traccia del punteggio di ogni squadra in una mappa hash in cui ogni chiave è il nome di una squadra e i valori sono i punteggi di ogni squadra. Dato un nome di squadra, puoi recuperarne il punteggio.

Affronteremo l’API di base delle mappe hash in questa sezione, ma molte altre funzionalità sono nascoste nelle funzioni definite su HashMap<K, V> dalla libreria standard. Come sempre, controlla la documentazione della libreria standard per ulteriori informazioni. Creazione di una Nuova Mappa Hash

Un modo per creare una mappa hash vuota è utilizzare new e aggiungere elementi con insert. In questo esempio, teniamo traccia dei punteggi di due squadre chiamate Blu e Giallo. La squadra Blu inizia con 10 punti e la squadra Giallo con 50.

rust

use std::collections::HashMap;

let mut punteggi = HashMap::new();

punteggi.insert(String::from(“Blu”), 10);
punteggi.insert(String::from(“Giallo”), 50);

Nota che dobbiamo prima utilizzare HashMap dalla sezione collections della libreria standard. Di queste tre collezioni comuni, questa è quella meno utilizzata, quindi non è inclusa nelle funzionalità importate automaticamente nello scope nel preludio. Le mappe hash hanno anche meno supporto dalla libreria standard; ad esempio, non c’è una macro integrata per costruirle.

Proprio come i vettori, le mappe hash memorizzano i loro dati nell’heap. Questa HashMap ha chiavi di tipo String e valori di tipo i32. Come i vettori, le mappe hash sono omogenee: tutte le chiavi devono avere lo stesso tipo tra loro e tutti i valori devono avere lo stesso tipo. Accesso ai Valori in una Mappa Hash

Possiamo ottenere un valore dalla mappa hash fornendo la sua chiave al metodo get, come mostrato nell’esempio seguente.

rust

use std::collections::HashMap;

let mut punteggi = HashMap::new();

punteggi.insert(String::from(“Blu”), 10);
punteggi.insert(String::from(“Giallo”), 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 un Option<&V>; se non c’è un valore per quella chiave nella mappa hash, get restituirà None. Questo programma gestisce l’Option chiamando copied per ottenere un Option<i32> anziché un Option<&i32>, quindi unwrap_or per impostare punteggio su zero se scores non ha una voce per la chiave.

Possiamo iterare su ogni coppia chiave/valore in una mappa hash in modo simile a quanto facciamo con i vettori, usando un ciclo for:

rust

use std::collections::HashMap;

let mut punteggi = HashMap::new();

punteggi.insert(String::from(“Blu”), 10);
punteggi.insert(String::from(“Giallo”), 50);

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

Questo codice stamperà ogni coppia in un ordine arbitrario:

bash

Giallo: 50
Blu: 10


Mappe Hash e Proprietà di Proprietà

Per i tipi che implementano il Copy trait, come i32, i valori vengono copiati nella mappa hash. Per i valori di proprietà come String, i valori verranno spostati e la mappa hash sarà la proprietaria di quei valori, come dimostrato nell’esempio seguente.

rust

use std::collections::HashMap;

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

let mut mappa = HashMap::new();
mappa.insert(nome_campo, valore_campo);
// nome_campo e valore_campo sono invalidi a questo punto, prova a usarli e
// vedi quale errore del compilatore ottieni!

Non siamo in grado di utilizzare le variabili nome_campo e valore_campo dopo che sono stati spostati nella mappa hash con la chiamata a insert.

Se inseriamo riferimenti a valori nella mappa hash, i valori non verranno spostati nella mappa hash. I valori a cui i riferimenti puntano devono essere validi per almeno quanto la mappa hash è valida. Parleremo di più di questi problemi nella sezione “Convalida dei Riferimenti con Lifetimes” nel Capitolo 10. Aggiornamento di una Mappa Hash

Anche se il numero di coppie chiave-valore è modificabile, ogni chiave univoca può avere solo un valore associato ad essa in un dato momento (ma non viceversa: ad esempio, sia la squadra Blu che la squadra Giallo potrebbero avere valore 10 memorizzato nella mappa hash dei punteggi).

Quando vuoi modificare i dati in una mappa hash, devi decidere come gestire il caso in cui una chiave ha già un valore assegnato. Potresti sostituire il vecchio valore con il nuovo valore, ignorando completamente il vecchio valore. Potresti mantenere il vecchio valore e ignorare il nuovo valore, aggiungendo solo il nuovo valore se la chiave non ha già un valore. Oppure potresti combinare il vecchio valore e il nuovo valore. Vediamo come fare ognuno di questi! Sovrascrittura di un Valore

Se inseriamo una chiave e un valore in una mappa hash e quindi inseriamo quella stessa chiave con un valore diverso, il valore associato a quella chiave verrà sostituito. Anche se il codice nell’esempio seguente chiama insert due volte, la mappa hash conterrà solo una coppia chiave/valore perché stiamo inserendo il valore per la chiave della squadra Blu entrambe le volte.

rust

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.

Aggiunta di una Chiave e un Valore Solo se una Chiave Non è Presente

È comune verificare se una particolare chiave esiste già nella mappa hash con un valore e quindi prendere le seguenti azioni: se la chiave esiste già nella mappa hash, il valore esistente dovrebbe rimanere com’è. Se la chiave non esiste, inseriscila e un valore per essa.

Le mappe hash hanno un’API speciale per questo chiamata entry che prende la chiave che vuoi controllare come parametro. Il valore di ritorno del metodo entry è un enum chiamato Entry che rappresenta un valore che potrebbe o potrebbe non esistere. Diciamo che vogliamo verificare se la chiave per la squadra Giallo ha un valore associato ad essa. Se non lo ha, vogliamo inserire il valore 50, e lo stesso per la squadra Blu. Utilizzando l’API entry, il codice assomiglia a quanto segue.

rust

use std::collections::HashMap;

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

punteggi.entry(String::from(“Giallo”)).or_insert(50);
punteggi.entry(String::from(“Blu”)).or_insert(50);

println!(“{:?}”, punteggi);

Il metodo or_insert su Entry è definito per restituire un riferimento mutevole al valore per la chiave di Entry corrispondente se quella chiave esiste e, se no, inserisce il parametro come nuovo valore per questa chiave e restituisce un riferimento mutevole al nuovo valore. Questa tecnica è molto più pulita rispetto alla scrittura della logica noi stessi e, inoltre, si integra meglio con il controllo dei prestiti.

Eseguire il codice nell’esempio sopra stamperà {“Giallo”: 50, “Blu”: 10}. La prima chiamata a entry inserirà la chiave per la squadra Giallo con il valore 50 perché la squadra Giallo non ha già un valore. La seconda chiamata a entry non cambierà la mappa hash perché la squadra Blu ha già il valore 10. Aggiornamento di un Valore Basato sul Vecchio Valore

Un altro caso d’uso comune per le mappe hash è cercare il valore di una chiave e quindi aggiornarlo in base al vecchio valore. Ad esempio, il codice nell’esempio seguente conta quante volte ogni parola appare in un testo. Utilizziamo una mappa hash con le parole come chiavi e incrementiamo il valore per tenere traccia di quante volte abbiamo visto quella parola. Se è la prima volta che vediamo una parola, inseriamo prima il valore 0.

rust

use std::collections::HashMap;

let testo = “ciao mondo mondo meraviglioso”;

let mut mappa = HashMap::new();

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

println!(“{:?}”, mappa);

Questo codice stamperà {“mondo”: 2, “ciao”: 1, “meraviglioso”: 1}. Potresti vedere le stesse coppie chiave/valore stampate in un ordine diverso: ricorda dalla sezione “Accesso ai Valori in una Mappa Hash” che l’iterazione su una mappa hash avviene in un ordine arbitrario.

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

Per default, HashMap utilizza una funzione hash chiamata SipHash che può fornire resistenza agli attacchi di Denial of Service (DoS) che coinvolgono tabelle hash. Questo non è l’algoritmo di hash più veloce disponibile, ma il compromesso per una migliore sicurezza che arriva con il calo delle prestazioni ne vale la pena. Se profilate il vostro codice e trovate che la funzione hash predefinita è troppo lenta per i vostri scopi, potete passare a un’altra funzione specificando un hasher diverso. Un hasher è un tipo che implementa il trait BuildHasher. Parleremo dei trait e di come implementarli nel Capitolo 10. Non è necessario implementare necessariamente il proprio hasher da zero; crates.io ha librerie condivise da altri utenti di Rust che forniscono hashers che implementano molti algoritmi di hash comuni.

Riepilogo

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

• Dato un elenco di interi, utilizza un vettore e restituisci la mediana (quando ordinata, il valore nella posizione centrale) e la moda (il valore che si verifica più spesso; una mappa hash sarà utile qui) dell’elenco.
• Converti le stringhe in pig latin. La prima consonante di ogni parola viene spostata alla fine della parola e viene aggiunto “ay”, quindi “first” diventa “irst-fay”. Le parole che iniziano con una vocale hanno “hay” aggiunto alla fine invece (“apple” diventa “apple-hay”). Tieni presente i dettagli sull’encoding UTF-8!
• Utilizzando una mappa hash e vettori, crea un’interfaccia testuale per consentire all’utente di aggiungere nomi di dipendenti a un dipartimento in un’azienda. Ad esempio, “Aggiungi Sally a Ingegneria” o “Aggiungi Amir a Vendite”. Quindi permetti all’utente di recuperare un elenco di tutte le persone in un dipartimento o tutte le persone nell’azienda per dipartimento, ordinato alfabeticamente.

La documentazione dell’API della libreria standard descrive i metodi che i vettori, le stringhe e le mappe hash hanno che saranno utili per questi esercizi!

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