Stocker des clés associées à des valeurs dans des tables de hachage
La dernière des collections les plus courantes est la table de hachage (hash map). Le type HashMap<K, V> stocke une association de clés de type K à des valeurs de type V en utilisant une fonction de hachage, qui détermine comment elle va ranger ces clés et valeurs dans la mémoire. De nombreux langages de programmation prennent en charge ce genre de structure de données, mais elles ont souvent un nom différent, tel que hash, map, objet, table d’association, dictionnaire ou tableau associatif, pour n’en nommer que quelques-uns.
Les tables de hachage sont utiles lorsque vous voulez rechercher des données non pas en utilisant des indices, comme vous pouvez le faire avec les vecteurs, mais en utilisant une clé qui peut être de n’importe quel type. Par exemple, dans un jeu, vous pouvez consigner le score de chaque équipe dans une table de hachage dans laquelle chaque clé est le nom d’une équipe et la valeur est le score de l’équipe. Si vous avez le nom d’une équipe, vous pouvez récupérer son score.
Nous allons passer en revue l’API de base des tables de hachage dans cette section, mais bien d’autres fonctionnalités se cachent dans les fonctions définies sur HashMap<K, V> par la bibliothèque standard. Comme d’habitude, consultez la documentation de la bibliothèque standard pour plus d’informations.
Créer une nouvelle table de hachage
Une façon de créer une table de hachage vide est d’utiliser new et d’ajouter des éléments avec insert. Dans l’encart 8-20, nous consignons les scores de deux équipes qui s’appellent Bleu et Jaune. L’équipe Bleu commence avec 10 points, et l’équipe Jaune commence avec 50.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Bleu"), 10);
scores.insert(String::from("Jaune"), 50);
}Notez que nous devons d’abord importer HashMap via use depuis la partie des collections de la bibliothèque standard. De nos trois collections courantes, cette dernière est la moins utilisée, donc elle n’est pas présente dans les fonctionnalités importées automatiquement dans la portée par l’étape préliminaire. Les tables de hachage sont aussi moins gérées par la bibliothèque standard ; il n’y a pas de macro intégrée pour les construire, par exemple.
Exactement comme les vecteurs, les tables de hachage stockent leurs données sur le tas. Cette HashMap a des clés de type String et des valeurs de type i32. Et comme les vecteurs, les tables de hachage sont homogènes : toutes les clés doivent être du même type, et toutes les valeurs doivent aussi être du même type.
Accéder aux valeurs dans une table de hachage
Nous pouvons obtenir une valeur d’une table de hachage en passant sa clé à la méthode get, comme dans l’encart 8-21.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Bleu"), 10);
scores.insert(String::from("Jaune"), 50);
let nom_equipe = String::from("Bleu");
let score = scores.get(&nom_equipe).copied().unwrap_or(0);
}Dans notre cas, score aura la valeur qui est associée à l’équipe Bleu, et le résultat sera 10. La méthode get retourne une Option<&V> : s’il n’y a pas de valeur pour cette clé dans la table de hachage, get va retourner None. Ce programme gère cette Option en appelant copied pour obtenir un Option<i32> plutôt qu’un Option<&i32>, puis unwrap_or pour mettre score à zéro si scores n’a pas d’entrée pour cette clé.
Nous pouvons itérer sur chaque paire de clé-valeur dans une table de hachage de la même manière que nous le faisons avec les vecteurs, en utilisant une boucle for :
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Bleu"), 10);
scores.insert(String::from("Jaune"), 50);
for (cle, valeur) in &scores {
println!("{cle} : {valeur}");
}
}Ce code va afficher chaque paire dans un ordre arbitraire :
Jaune : 50
Bleu : 10
Gestion de la possession dans les tables de hachage
Pour les types qui implémentent le trait Copy, comme i32, les valeurs sont copiées dans la table de hachage. Pour les valeurs qui sont possédées comme String, les valeurs seront déplacées et la table de hachage sera la propriétaire de ces valeurs, comme démontré dans l’encart 8-22.
fn main() {
use std::collections::HashMap;
let nom_champ = String::from("Couleur favorite");
let valeur_champ = String::from("Bleu");
let mut table = HashMap::new();
table.insert(nom_champ, valeur_champ);
// nom_champ et valeur_champ ne sont plus en vigueur à partir d'ici,
// essayez de les utiliser et vous verrez l'erreur du compilateur que
// vous obtiendrez !
}Nous ne pouvons plus utiliser les variables nom_champ et valeur_champ après qu’elles ont été déplacées dans la table de hachage lors de l’appel à insert.
Si nous insérons dans la table de hachage des références vers des valeurs, ces valeurs ne seront pas déplacées dans la table de hachage. Les valeurs vers lesquelles les références pointent doivent rester en vigueur au moins aussi longtemps que la table de hachage. Nous verrons ces problématiques dans la section “La conformité des références avec les durées de vies” du chapitre 10.
Modifier une table de hachage
Bien que le nombre de paires de clé-valeur puisse augmenter, chaque clé unique ne peut être associée qu’à une seule valeur à la fois (mais la réciproque n’est pas vraie : par exemple, les équipes Bleu et Jaune pourraient toutes deux avoir la valeur 10 stockée dans la table de hachage scores).
Lorsque vous souhaitez modifier les données d’une table de hachage, vous devez choisir comment gérer le cas où une clé a déjà une valeur qui lui est associée. Vous pouvez remplacer l’ancienne valeur avec la nouvelle valeur, en ignorant complètement l’ancienne valeur. Vous pouvez garder l’ancienne valeur et ignorer la nouvelle valeur, en insérant la nouvelle valeur uniquement si la clé n’a pas déjà une valeur. Ou vous pouvez fusionner l’ancienne valeur et la nouvelle. Découvrons dès maintenant comment faire chacune de ces actions !
Réécrire une valeur
Si nous ajoutons une clé et une valeur dans une table de hachage et que nous ajoutons à nouveau la même clé avec une valeur différente, la valeur associée à cette clé sera remplacée. Même si le code dans l’encart 8-23 appelle deux fois insert, la table de hachage contiendra une seule paire de clé/valeur car nous ajoutons la valeur pour l’équipe Bleu à deux reprises.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Bleu"), 10);
scores.insert(String::from("Bleu"), 25);
println!("{scores:?}");
}Ce code va afficher {"Bleu": 25}. La valeur initiale 10 a été remplacée.
Ajouter une valeur seulement si la clé n’a pas déjà de valeur
Il est courant de vérifier si une clé spécifique existe déjà dans la table de hachage avec une valeur, et ensuite de procéder aux actions suivantes : si la clé existe dans la table de hachage, la valeur existante doit rester telle quelle ; si la clé n’existe pas, l’insérer avec une valeur associée.
Les tables de hachage ont une API spécifique pour ce cas-là qui s’appelle entry et qui prend en paramètre la clé que vous voulez vérifier. La valeur de retour de la méthode entry est une énumération qui s’appelle Entry qui représente une valeur qui existe ou non. Imaginons que nous souhaitons vérifier si la clé pour l’équipe Jaune a une valeur qui lui est associée. Si ce n’est pas le cas, nous voulons lui associer la valeur 50, et faire de même pour l’équipe Bleu. En utilisant l’API entry, ce code va ressembler à l’encart 8-24.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Bleu"), 10);
scores.entry(String::from("Jaune")).or_insert(50);
scores.entry(String::from("Bleu")).or_insert(50);
println!("{scores:?}");
}entry method to only insert if the key does not already have a valueLa méthode or_insert sur Entry est conçue pour retourner une référence mutable vers la valeur correspondant à la clé du Entry si cette clé existe, et sinon, d’ajouter son paramètre comme nouvelle valeur pour cette clé et retourner une référence mutable vers la nouvelle valeur. Cette technique est plus propre que d’écrire la logique nous-mêmes et, de plus, elle fonctionne mieux avec le vérificateur d’emprunt.
L’exécution du code de l’encart 8-24 va afficher {"Jaune": 50, "Bleu": 10}. Le premier appel à entry va ajouter la clé pour l’équipe Jaune avec la valeur 50 car l’équipe Jaune n’a pas encore de valeur. Le second appel à entry ne va pas changer la table de hachage car l’équipe Bleu a déjà la valeur 10.
Modifier une valeur en fonction de l’ancienne valeur
Une autre utilisation courante avec les tables de hachage est de regarder la valeur d’une clé et ensuite la modifier en fonction de l’ancienne valeur. Par exemple, l’encart 8-25 contient du code qui compte combien de fois chaque mot apparaît dans du texte. Nous utilisons une table de hachage avec les mots comme clés et nous incrémentons la valeur pour compter combien de fois nous avons vu ce mot. Si c’est la première fois que nous voyons un mot, nous allons d’abord insérer la valeur 0.
fn main() {
use std::collections::HashMap;
let texte = "bonjour le monde magnifique monde";
let mut table = HashMap::new();
for mot in texte.split_whitespace() {
let compteur = table.entry(mot).or_insert(0);
*compteur += 1;
}
println!("{table:?}");
}Ce code va afficher {"monde": 2, "bonjour": 1, "magnifique": 1, "le": 1}. Il se peut que vous voyez les mêmes paires clé-valeurs ordonnées différemment : rappelez-vous du paragraphe “Accéder aux valeurs dans une table de hachage”, l’itération sur une table de hachage se fait dans un ordre aléatoire.
La méthode split_whitespace renvoie un itérateur sur les sous-slices, séparées par des espaces vides, sur la valeur dans texte. La méthode or_insert retourne une référence mutable (&mut V) vers la valeur de la clé spécifiée. Nous stockons ici la référence mutable dans la variable compteur, donc pour affecter une valeur, nous devons d’abord déréférencer compteur en utilisant l’astérisque (*). La référence mutable sort de la portée à la fin de la boucle for, donc tous ces changements sont sûrs et autorisés par les règles d’emprunt.
Fonctions de hachage
Par défaut, HashMap utilise une fonction de hachage nommée SipHash qui résiste aux attaques par déni de service (DoS) envers les tables de hachage1. Ce n’est pas l’algorithme de hachage le plus rapide qui existe, mais le compromis entre une meilleure sécurité et la baisse de performances en vaut la peine. Si vous analysez la performance de votre code et que vous vous rendez compte que la fonction de hachage par défaut est trop lente pour vos besoins, vous pouvez la remplacer par une autre fonction en spécifiant un hacheur différent. Un hacheur est un type qui implémente le trait BuildHasher. Nous verrons les traits et comment les implémenter au chapitre 10. Vous n’avez pas forcément besoin d’implémenter votre propre hacheur à partir de zéro ; crates.io héberge des bibliothèques partagées par d’autres utilisateurs de Rust qui fournissent de nombreux algorithmes de hachage répandus.
Résumé
Les vecteurs, Strings, et tables de hachage vont vous apporter de nombreuses fonctionnalités nécessaires à vos programmes lorsque vous aurez besoin de stocker, accéder, et modifier des données. Voici quelques exercices que vous devriez maintenant être en mesure de résoudre :
- À partir d’une liste d’entiers, utiliser un vecteur et retourner la médiane (la valeur au milieu lorsque la liste est triée) et le mode (la valeur qui apparaît le plus souvent ; une table de hachage sera utile dans ce cas) de la liste.
- Convertir des chaînes de caractères dans une variante du louchébem. La consonne initiale de chaque mot est remplacée par la lettre
let est rétablie à la fin du mot suivie du suffixe argotique “em” ; ainsi, “bonjour” devient “l_onjour_bem”. Si le mot commence par une voyelle, ajouter unlau début du mot et ajouter à la fin le suffixe “muche”. Et gardez en tête les détails à propos de l’encodage UTF-8 ! - En utilisant une table de hachage et des vecteurs, créez une interface textuelle pour permettre à un utilisateur d’ajouter des noms d’employés dans un département d’une entreprise. Par exemple, “Ajouter Sally au bureau d’études” ou “Ajouter Amir au service commercial”. Ensuite, donnez la possibilité à l’utilisateur de récupérer une liste de toutes les personnes dans un département, ou tout le monde dans l’entreprise trié par département, et classés dans l’ordre alphabétique dans tous les cas.
La documentation de l’API de la bibliothèque standard décrit les méthodes qu’ont les vecteurs, chaînes de caractères et tables de hachage, ce qui vous sera bien utile pour mener à bien ces exercices !
Nous nous lançons dans des programmes de plus en plus complexes dans lesquels les opérations peuvent échouer, c’est donc le moment idéal pour voir comment bien gérer les erreurs. C’est ce que nous allons faire au prochain chapitre !