HashSet e BTreeMap in Rust

Un HashSet è una collezione di valori unici. Se metti due volte lo stesso valore, viene salvato una volta sola. Pensa alla lista degli invitati all’ingresso di una festa: al buttafuori interessa solo se il tuo nome è sulla lista, non quante volte è stato scritto.

Conosci già Vec e HashMap. Questa pagina aggiunge le altre collezioni che userai più spesso: HashSet, le collezioni ordinate BTreeMap e BTreeSet, e VecDeque per le code. Alla fine c’è una tabella che ti aiuta a scegliere quella giusta.

Creare un HashSet

HashSet si trova in std::collections, quindi ti serve una riga use. Il metodo insert restituisce un bool: true se il valore era nuovo, false se c’era già.

use std::collections::HashSet;

fn main() {
    let mut tags = HashSet::new();

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // c'è già

    println!("{} tag unici", tags.len());
}

Output:

true
true
false
2 tag unici

▶ Provalo tu

Quel bool è più utile di quanto sembri. Risponde a «l’ho già visto?» nello stesso passaggio in cui aggiungi il valore, quindi non ti serve un controllo separato.

Controllare e rimuovere valori

contains ti dice se un valore è nell’insieme. remove lo toglie e, come insert, restituisce un bool che ti dice se è stato davvero rimosso qualcosa.

use std::collections::HashSet;

fn main() {
    let mut online: HashSet<&str> = HashSet::from(["ana", "ben", "chen"]);

    println!("ben è online? {}", online.contains("ben"));

    println!("rimosso ben: {}", online.remove("ben"));
    println!("rimosso di nuovo ben: {}", online.remove("ben"));

    println!("ben è online? {}", online.contains("ben"));
    println!("{} persone online", online.len());
}

Output:

ben è online? true
rimosso ben: true
rimosso di nuovo ben: false
ben è online? false
2 persone online

▶ Provalo tu

Perché qui usare un insieme invece di un Vec? contains su un Vec guarda tutti gli elementi, uno per uno. Un HashSet salta direttamente alla risposta, per quanto diventi grande. Con un milione di utenti, la differenza è enorme.

Attenzione

Un HashSet non ha un ordine fisso. Se lo stampi con {:?} o lo scorri, l’ordine può cambiare da un’esecuzione all’altra. Quando per la stampa ti serve un ordine stabile, copia i valori in un Vec e ordinalo, oppure usa un BTreeSet (lo vediamo più sotto).

Togliere i duplicati da un Vec

Un compito molto comune: hai una lista con delle ripetizioni e vuoi ogni valore una volta sola. Ci sono due buoni modi, a seconda che ti interessi o no l’ordine originale.

use std::collections::HashSet;

fn main() {
    let visits = vec![3, 1, 3, 2, 1, 5, 2];

    // Modo 1: raccogli in un insieme, poi ordina per avere un ordine stabile
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("unici ordinati:   {:?}", sorted);

    // Modo 2: tieni la prima comparsa di ogni valore, nell'ordine originale
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("ordine originale: {:?}", in_order);
}

Output:

unici ordinati:   [1, 2, 3, 5]
ordine originale: [3, 1, 2, 5]

▶ Provalo tu

Il modo 2 usa il bool di insert. retain tiene un elemento solo quando la closure restituisce true, e insert restituisce true solo la prima volta che vede un valore.

Operazioni sugli insiemi: unione, intersezione, differenza

Gli insiemi si possono combinare come i cerchi di un diagramma di Venn. Ogni metodo restituisce un iteratore, quindi raccogliamo i risultati in un Vec e li ordiniamo prima di stamparli, per avere sempre lo stesso output.

use std::collections::HashSet;

fn main() {
    let alice: HashSet<&str> = HashSet::from(["rust", "python", "go"]);
    let bob: HashSet<&str> = HashSet::from(["go", "java", "rust"]);

    let mut both: Vec<_> = alice.intersection(&bob).collect();
    both.sort();
    println!("li sanno entrambi:  {:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("li sa almeno uno:   {:?}", either);

    let mut only_alice: Vec<_> = alice.difference(&bob).collect();
    only_alice.sort();
    println!("solo alice:         {:?}", only_alice);

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("li sa uno solo:     {:?}", only_one);
}

Output:

li sanno entrambi:  ["go", "rust"]
li sa almeno uno:   ["go", "java", "python", "rust"]
solo alice:         ["python"]
li sa uno solo:     ["java", "python"]

▶ Provalo tu

difference va in una sola direzione: alice.difference(&bob) è «quello che Alice sa e Bob no». Scambiali e ottieni invece la lista di Bob. symmetric_difference prende entrambi i lati insieme: tutto quello che sa uno solo dei due.

BTreeMap e BTreeSet: sempre ordinati

BTreeMap funziona proprio come HashMap, e BTreeSet proprio come HashSet. La differenza: tengono le chiavi ordinate. Quando li scorri, ottieni le chiavi in ordine, ogni volta.

use std::collections::{BTreeMap, BTreeSet};

fn main() {
    let text = "il gatto e il topo e il cane";

    let mut counts: BTreeMap<&str, u32> = BTreeMap::new();
    for word in text.split_whitespace() {
        *counts.entry(word).or_insert(0) += 1;
    }
    for (word, count) in &counts {
        println!("{word}: {count}");
    }

    let scores: BTreeSet<u32> = BTreeSet::from([72, 95, 58, 88]);
    println!("il più basso: {:?}", scores.first());
    println!("il più alto: {:?}", scores.last());
    println!("tutti: {:?}", scores);
}

Output:

cane: 1
e: 2
gatto: 1
il: 3
topo: 1
il più basso: Some(58)
il più alto: Some(95)
tutti: {58, 72, 88, 95}

▶ Provalo tu

L’API entry è la stessa che hai incontrato nella pagina su HashMap. Visto che la mappa è una BTreeMap, le parole escono in ordine alfabetico senza bisogno di ordinarle. (La frase non ha lettere accentate apposta: l’ordinamento confronta i byte, e una «è» finirebbe dopo tutte le lettere senza accento.)

Quale scegliere?

• Di default scegli HashMap / HashSet. Di solito le ricerche sono più veloci.
• Scegli BTreeMap / BTreeSet quando ti servono i dati in ordine: stampare un report ordinato, trovare la chiave più piccola o più grande, o prendere un intervallo di chiavi.

VecDeque: una coda

Un VecDeque (si legge «vec deck») è una lista a cui puoi aggiungere e togliere elementi velocemente da entrambe le estremità. Per questo è la scelta naturale per una coda: il primo che entra è il primo che esce, come le persone in fila.

use std::collections::VecDeque;

fn main() {
    let mut line: VecDeque<&str> = VecDeque::new();
    line.push_back("ana");
    line.push_back("ben");
    line.push_back("chen");

    while let Some(person) = line.pop_front() {
        println!("tocca a {person}, {} ancora in attesa", line.len());
    }
}

Output:

tocca a ana, 2 ancora in attesa
tocca a ben, 1 ancora in attesa
tocca a chen, 0 ancora in attesa

▶ Provalo tu

Potresti usare Vec::remove(0) per farlo, ma così sposti di un posto tutti gli altri elementi. pop_front su un VecDeque non lo fa, quindi resta veloce anche con una fila lunga.

Quale collezione usare?

Collezione	Usala quando ti serve…	Esempio
Vec<T>	Una lista ordinata, letta per posizione	Le righe di un file, una lista di punteggi
HashMap<K, V>	Cercare velocemente un valore tramite una chiave	Nome utente → profilo utente
HashSet<T>	Valori unici e controlli veloci del tipo «c’è qui dentro?»	Pagine visitate, parole vietate
BTreeMap<K, V>	Chiave → valore, con le chiavi tenute in ordine	Un conteggio di parole stampato in ordine alfabetico
VecDeque<T>	Aggiungere/togliere da entrambe le estremità	Una coda di task o di messaggi

Nel dubbio, parti con un Vec. Cambia quando ti accorgi che ci cerchi dentro di continuo (usa un insieme o una mappa) o che togli spesso elementi dall’inizio (usa un VecDeque).

Errori comuni

Mettere una tua struct in un HashSet senza i derive giusti. Un HashSet deve calcolare l’hash dei suoi valori e confrontarli per vedere se sono uguali. La tua struct non lo fa in automatico:

use std::collections::HashSet;

struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
}

error[E0277]: the trait bound `Point: Eq` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Eq` is not implemented for `Point`

error[E0277]: the trait bound `Point: Hash` is not satisfied
  --> src/main.rs:10:13
   |
10 |     visited.insert(Point { x: 0, y: 0 });
   |             ^^^^^^ the trait `Hash` is not implemented for `Point`

Il compilatore dice che Point non implementa i trait Eq e Hash. La soluzione è una riga sopra la struct: #[derive(PartialEq, Eq, Hash)]. Per un BTreeSet ti servirebbero anche PartialOrd e Ord, così sa come ordinarli. Vedi Trait comuni per sapere cosa significa ciascuno.

use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut visited = HashSet::new();
    visited.insert(Point { x: 0, y: 0 });
    visited.insert(Point { x: 1, y: 0 });
    visited.insert(Point { x: 0, y: 0 }); // duplicato, ignorato
    println!("caselle visitate: {}", visited.len());
}

Output:

caselle visitate: 2

▶ Provalo tu

Per andare oltre

Ti serve una coda (il primo che entra è il primo che esce) o qualcosa che ti dia «sempre il più grande come prossimo»? VecDeque e BinaryHeap parla delle due collezioni pensate proprio per questo.

Pratica

1. La prima ripetizione

Date le parole ["rosso", "blu", "verde", "blu", "rosso"], stampa la prima parola che compare per la seconda volta. Suggerimento: insert restituisce false quando il valore è già nell’insieme, e break ferma il ciclo.

Mostra la soluzione

use std::collections::HashSet;

fn main() {
    let words = ["rosso", "blu", "verde", "blu", "rosso"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("Prima ripetizione: {word}");
            break;
        }
    }
}

Output:

Prima ripetizione: blu

▶ Provalo tu

!seen.insert(word) si legge «l’inserimento è fallito», cioè «questa l’ho già vista». "blu" è la prima parola che si ripete. Anche "rosso" si ripete, ma dopo.

2. Lettere in ordine

Conta quante volte compare ogni lettera in "mississippi" e stampa i conteggi in ordine alfabetico. Suggerimento: usa una BTreeMap con lo stesso trucco entry(...).or_insert(0) della sezione su BTreeMap, e scorri word.chars().

Mostra la soluzione

use std::collections::BTreeMap;

fn main() {
    let word = "mississippi";
    let mut counts = BTreeMap::new();

    for letter in word.chars() {
        *counts.entry(letter).or_insert(0) += 1;
    }

    for (letter, count) in &counts {
        println!("{letter}: {count}");
    }
}

Output:

i: 4
m: 1
p: 2
s: 4

▶ Provalo tu

Con una HashMap, queste quattro righe potrebbero uscire in qualsiasi ordine. La BTreeMap tiene le chiavi ordinate, quindi i, m, p, s vengono stampate in ordine alfabetico ogni volta.

Riepilogo

• HashSet salva valori unici. insert e remove restituiscono un bool che ti dice se è cambiato qualcosa.
• contains su un insieme è veloce, anche con insiemi enormi. Su un Vec controlla ogni elemento.
• union, intersection, difference e symmetric_difference fanno le operazioni sugli insiemi. Ordina i risultati prima di stamparli.
• BTreeMap e BTreeSet tengono le chiavi ordinate; usali quando l’ordine conta.
• VecDeque è la coda per eccellenza: push_back per mettersi in fila, pop_front per uscire.

Verifica veloce

Verifica veloce

1. Che cosa restituisce set.insert(x) se x è già nell'insieme?

true Un errore false Il valore vecchio

2. Vuoi un conteggio di parole stampato in ordine alfabetico senza ordinarlo tu. Quale mappa è la più adatta?

HashMap BTreeMap Vec VecDeque

3. Perché stampare un HashSet con {:?} può dare output diversi in esecuzioni diverse?

Un HashSet non ha un ordine fisso {:?} è casuale Gli insiemi perdono valori col tempo Succede solo in modalità debug

4. Quale collezione è la migliore per una coda in cui il primo che entra è il primo che esce?

HashSet BTreeSet HashMap VecDeque

Punteggio: 0 / 4

Per approfondire

• Panoramica di std::collections — documentazione della libreria standard (in inglese): una guida più lunga per scegliere una collezione, con la velocità di ogni operazione.
• HashSet — Rust by Example (in inglese): un esempio eseguibile di union, intersection e difference.
• HashSet — documentazione della libreria standard (in inglese): tutti i metodi degli insiemi, compresi is_subset e retain.
• BTreeMap — documentazione della libreria standard (in inglese): le mappe ordinate, compreso range per prendere una fetta di chiavi.
• VecDeque — documentazione della libreria standard (in inglese): tutti i metodi delle code, come push_front, pop_back e front.