HashSet et BTreeMap en Rust

Un HashSet est une collection de valeurs uniques. Si vous y mettez deux fois la même valeur, elle n’est stockée qu’une seule fois. Imaginez une liste d’invités à l’entrée d’une soirée : le videur veut seulement savoir si votre nom est sur la liste, pas combien de fois il y a été écrit.

Vous connaissez déjà Vec et HashMap. Cette page présente les autres collections dont vous aurez le plus souvent besoin : HashSet, les collections triées BTreeMap et BTreeSet, et VecDeque pour les files d’attente. À la fin, un tableau vous aide à choisir la bonne.

Créer un HashSet

HashSet se trouve dans std::collections, il vous faut donc une ligne use. La méthode insert renvoie un bool : true si la valeur est nouvelle, false si elle était déjà présente.

use std::collections::HashSet;

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

    println!("{}", tags.insert("rust"));
    println!("{}", tags.insert("web"));
    println!("{}", tags.insert("rust")); // déjà présent

    println!("{} étiquettes uniques", tags.len());
}

Sortie :

true
true
false
2 étiquettes uniques

▶ Essayez par vous-même

Ce bool est plus utile qu’il n’y paraît. Il répond à la question « est-ce que j’ai déjà vu cette valeur ? » au moment même où vous l’ajoutez : pas besoin d’une vérification séparée.

Vérifier et retirer des valeurs

contains vous dit si une valeur se trouve dans l’ensemble. remove la retire et, comme insert, renvoie un bool qui indique si quelque chose a vraiment été retiré.

use std::collections::HashSet;

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

    println!("ben est-il en ligne ? {}", online.contains("ben"));

    println!("ben retiré : {}", online.remove("ben"));
    println!("ben retiré à nouveau : {}", online.remove("ben"));

    println!("ben est-il en ligne ? {}", online.contains("ben"));
    println!("{} personnes en ligne", online.len());
}

Sortie :

ben est-il en ligne ? true
ben retiré : true
ben retiré à nouveau : false
ben est-il en ligne ? false
2 personnes en ligne

▶ Essayez par vous-même

Pourquoi utiliser un ensemble plutôt qu’un Vec ici ? Appeler contains sur un Vec examine chaque élément, un par un. Un HashSet va directement à la réponse, quelle que soit sa taille. Avec un million d’utilisateurs, la différence est énorme.

Attention

Un HashSet n’a pas d’ordre fixe. Si vous l’affichez avec {:?} ou le parcourez avec une boucle, l’ordre peut changer d’une exécution à l’autre. Quand vous avez besoin d’un ordre stable pour l’affichage, copiez les valeurs dans un Vec et triez-le, ou utilisez un BTreeSet (présenté plus bas).

Supprimer les doublons d’un Vec

Une tâche très courante : vous avez une liste avec des répétitions et vous voulez chaque valeur une seule fois. Il existe deux bonnes méthodes, selon que l’ordre d’origine compte pour vous ou non.

use std::collections::HashSet;

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

    // Méthode 1 : collecter dans un ensemble, puis trier pour un ordre stable
    let unique: HashSet<i32> = visits.iter().copied().collect();
    let mut sorted: Vec<i32> = unique.into_iter().collect();
    sorted.sort();
    println!("uniques triés :   {:?}", sorted);

    // Méthode 2 : garder la première apparition de chaque valeur, dans l'ordre d'origine
    let mut seen = HashSet::new();
    let mut in_order = visits.clone();
    in_order.retain(|x| seen.insert(*x));
    println!("ordre d'origine : {:?}", in_order);
}

Sortie :

uniques triés :   [1, 2, 3, 5]
ordre d'origine : [3, 1, 2, 5]

▶ Essayez par vous-même

La méthode 2 utilise le bool renvoyé par insert. retain ne garde un élément que si la closure (fonction anonyme) renvoie true, et insert ne renvoie true que la première fois qu’il voit une valeur.

Opérations d’ensembles : union, intersection, différence

On peut combiner des ensembles comme les cercles d’un diagramme de Venn. Chaque méthode renvoie un itérateur : on collecte donc les résultats dans un Vec et on les trie avant de les afficher, pour obtenir la même sortie à chaque fois.

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!("connus des deux :      {:?}", both);

    let mut either: Vec<_> = alice.union(&bob).collect();
    either.sort();
    println!("connus d'au moins un : {:?}", either);

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

    let mut only_one: Vec<_> = alice.symmetric_difference(&bob).collect();
    only_one.sort();
    println!("connus d'un seul :     {:?}", only_one);
}

Sortie :

connus des deux :      ["go", "rust"]
connus d'au moins un : ["go", "java", "python", "rust"]
seulement alice :      ["python"]
connus d'un seul :     ["java", "python"]

▶ Essayez par vous-même

difference ne marche que dans un sens : alice.difference(&bob), c’est « ce que connaît Alice et que Bob ne connaît pas ». Inversez-les et vous obtenez la liste de Bob. symmetric_difference regarde les deux côtés à la fois : tout ce qu’une seule des deux personnes connaît.

BTreeMap et BTreeSet : toujours triés

BTreeMap fonctionne exactement comme HashMap, et BTreeSet exactement comme HashSet. La différence : ils gardent leurs clés triées. Quand vous les parcourez, vous obtenez les clés dans l’ordre, à chaque fois.

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

fn main() {
    let text = "le chat dort sur le tapis le soir";

    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!("le plus bas : {:?}", scores.first());
    println!("le plus haut : {:?}", scores.last());
    println!("tous : {:?}", scores);
}

Sortie :

chat : 1
dort : 1
le : 3
soir : 1
sur : 1
tapis : 1
le plus bas : Some(58)
le plus haut : Some(95)
tous : {58, 72, 88, 95}

▶ Essayez par vous-même

L’API entry est la même que celle de la page HashMap. Comme la table est une BTreeMap, les mots sortent dans l’ordre alphabétique sans étape de tri supplémentaire. (Attention : ce tri compare les octets, donc un mot qui commence par une lettre accentuée comme « été » passerait après « zéro ». C’est pour ça que la phrase de l’exemple n’a pas d’accents.)

Lequel choisir ?

• Prenez HashMap / HashSet par défaut. Les recherches y sont généralement plus rapides.
• Prenez BTreeMap / BTreeSet quand vous avez besoin des données dans l’ordre : afficher un rapport trié, trouver la plus petite ou la plus grande clé, ou obtenir une plage de clés.

VecDeque : une file d’attente

Un VecDeque (prononcez « vec dèque ») est une liste à laquelle vous pouvez ajouter et retirer des éléments rapidement aux deux bouts. C’est donc le choix naturel pour une file d’attente : premier arrivé, premier servi, comme des gens qui font la queue.

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!("on sert {person}, encore {} en attente", line.len());
    }
}

Sortie :

on sert ana, encore 2 en attente
on sert ben, encore 1 en attente
on sert chen, encore 0 en attente

▶ Essayez par vous-même

Vous pourriez utiliser Vec::remove(0) pour cela, mais cette méthode décale tous les autres éléments d’une case. pop_front sur un VecDeque ne le fait pas, et reste donc rapide même avec une longue file.

Quelle collection utiliser ?

Collection	Utilisez-la quand vous avez besoin…	Exemple
Vec<T>	D’une liste ordonnée, accessible par position	Les lignes d’un fichier, une liste de scores
HashMap<K, V>	De retrouver vite une valeur par sa clé	Nom d’utilisateur → profil
HashSet<T>	De valeurs uniques et de vérifier vite « est-ce que c’est dedans ? »	Pages visitées, mots interdits
BTreeMap<K, V>	D’associer clé → valeur, avec des clés triées	Un comptage de mots affiché par ordre alphabétique
VecDeque<T>	D’ajouter/retirer aux deux bouts	Une file de tâches ou de messages

Dans le doute, commencez par un Vec. Changez quand vous remarquez que vous y cherchez des valeurs encore et encore (prenez un ensemble ou une table) ou que vous retirez souvent des éléments au début (prenez un VecDeque).

Erreurs courantes

Mettre votre propre struct dans un HashSet sans les bons derive. Un HashSet doit calculer le hash de ses valeurs et les comparer pour savoir si elles sont égales. Votre struct ne le fait pas automatiquement :

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`

Le compilateur vous dit que Point n’implémente pas les traits Eq (égalité) et Hash dont le HashSet a besoin. La solution tient en une ligne au-dessus de la struct : #[derive(PartialEq, Eq, Hash)]. Pour un BTreeSet, il vous faudrait aussi PartialOrd et Ord, pour qu’il sache trier. Consultez Les traits courants pour comprendre le rôle de chacun.

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 }); // doublon, ignoré
    println!("{} cases visitées", visited.len());
}

Sortie :

2 cases visitées

▶ Essayez par vous-même

Exercices

1. La première répétition

À partir des mots ["rouge", "bleu", "vert", "bleu", "rouge"], affichez le premier mot qui apparaît une deuxième fois. Indice : insert renvoie false quand la valeur est déjà dans l’ensemble, et break arrête la boucle.

Voir la solution

use std::collections::HashSet;

fn main() {
    let words = ["rouge", "bleu", "vert", "bleu", "rouge"];
    let mut seen = HashSet::new();

    for word in words {
        if !seen.insert(word) {
            println!("Première répétition : {word}");
            break;
        }
    }
}

Sortie :

Première répétition : bleu

▶ Essayez par vous-même

!seen.insert(word) se lit « l’insertion a échoué », c’est-à-dire « j’ai déjà vu ce mot ». "bleu" est le premier mot à se répéter. "rouge" se répète aussi, mais plus tard.

2. Les lettres dans l’ordre

Comptez combien de fois chaque lettre apparaît dans "mississippi", et affichez les totaux par ordre alphabétique. Indice : utilisez une BTreeMap avec la même astuce entry(...).or_insert(0) que dans la section sur BTreeMap, et parcourez word.chars().

Voir la solution

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}");
    }
}

Sortie :

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

▶ Essayez par vous-même

Avec une HashMap, ces quatre lignes pourraient sortir dans n’importe quel ordre. La BTreeMap garde ses clés triées, donc i, m, p, s s’affichent dans l’ordre alphabétique à chaque fois.

Récapitulatif

• HashSet stocke des valeurs uniques. insert et remove renvoient un bool qui vous dit si quelque chose a changé.
• contains est rapide sur un ensemble, même énorme. Sur un Vec, il examine chaque élément.
• union, intersection, difference et symmetric_difference font les opérations d’ensembles. Triez les résultats avant de les afficher.
• BTreeMap et BTreeSet gardent leurs clés triées ; utilisez-les quand l’ordre compte.
• VecDeque est la file d’attente par excellence : push_back pour entrer dans la file, pop_front pour en sortir.

Petit quiz

Petit quiz

1. Que renvoie set.insert(x) si x est déjà dans l'ensemble ?

true Une erreur false L'ancienne valeur

2. Vous voulez afficher un comptage de mots par ordre alphabétique sans le trier vous-même. Quelle table convient le mieux ?

HashMap BTreeMap Vec VecDeque

3. Pourquoi afficher un HashSet avec {:?} peut-il donner une sortie différente d'une exécution à l'autre ?

Un HashSet n'a pas d'ordre fixe {:?} est aléatoire Les ensembles perdent des valeurs avec le temps Ça n'arrive qu'en mode debug

4. Quelle collection est la meilleure pour une file « premier arrivé, premier servi » ?

HashSet BTreeSet HashMap VecDeque

Score : 0 / 4

Pour aller plus loin

• std::collections overview — documentation de la bibliothèque standard (en anglais) : un guide plus complet pour choisir une collection, avec la vitesse de chaque opération.
• HashSet — Rust by Example (en anglais) : un exemple exécutable de union, intersection et difference.
• HashSet — documentation de la bibliothèque standard (en anglais) : toutes les méthodes des ensembles, dont is_subset et retain.
• BTreeMap — documentation de la bibliothèque standard (en anglais) : les tables triées, dont range pour obtenir une plage de clés.
• VecDeque — documentation de la bibliothèque standard (en anglais) : toutes les méthodes de file, comme push_front, pop_back et front.