Stocker des clés associées à des valeurs dans des tables de hachage
La dernière de nos collections courantes est la hash map. Le type HashMap<K, V> stocké une association de clés de type K vers des valeurs de type V en utilisant une fonction de hachage, qui détermine comment il place ces clés et valeurs en mémoire. De nombreux langages de programmation prennent en charge ce type de structure de données, mais ils utilisent souvent un nom différent, comme hash, map, object, hash table, dictionary ou associative array (tableau associatif), pour n’en citer que quelques-uns.
Les hash maps sont utiles lorsque vous voulez rechercher des données non pas en utilisant un indice, comme vous pouvez le faire avec les vectors, mais en utilisant une clé qui peut être de n’importe quel type. Par exemple, dans un jeu, vous pourriez suivre le score de chaque équipe dans une hash map dans laquelle chaque clé est le nom d’une équipe et les valeurs sont les scores de chaque équipe. À partir d’un nom d’équipe, vous pouvez récupérer son score.
Nous allons parcourir l’API de base des hash maps dans cette section, mais de nombreuses autres fonctionnalités se cachent dans les fonctions définies sur HashMap<K, V> par la bibliothèque standard. Comme toujours, consultez la documentation de la bibliothèque standard pour plus d’informations.
Créer une nouvelle hash map
Une façon de créer une hash map vide est d’utiliser new et d’ajouter des éléments avec insert. Dans l’encart 8-20, nous suivons les scores de deux équipes dont les noms sont Blue et Yellow. L’équipe Blue commence avec 10 points et l’équipe Yellow commence avec 50.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
}Notez que nous devons d’abord importer (use) le HashMap de la partie collections de la bibliothèque standard. Parmi nos trois collections courantes, celle-ci est la moins souvent utilisée, elle n’est donc pas incluse dans les fonctionnalités automatiquement mises en portée par le prelude. Les hash maps bénéficient également de moins de support de la part de la bibliothèque standard ; il n’y a pas de macro intégrée pour les construire, par exemple.
Tout comme les vectors, les hash maps stockent leurs données sur le tas. Ce HashMap à des clés de type String et des valeurs de type i32. Comme les vectors, les hash maps sont homogènes : toutes les clés doivent avoir le même type, et toutes les valeurs doivent avoir le même type.
Accéder aux valeurs dans une hash map
Nous pouvons obtenir une valeur de la hash map en fournissant sa clé à la méthode get, comme montré dans l’encart 8-21.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
let team_name = String::from("Blue");
let score = scores.get(&team_name).copied().unwrap_or(0);
}Ici, score aura la valeur associée à l’équipe Blue, et le résultat sera 10. La méthode get renvoie un Option<&V> ; s’il n’y a pas de valeur pour cette clé dans la hash map, get renverra None. Ce programme gère l’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 la clé.
Nous pouvons itérer sur chaque paire clé-valeur dans une hash map de la même manière que nous le faisons avec les vectors, en utilisant une boucle for : rust {{#rustdoc_include ../listings/ch08-common-collections/no-listing-03-iterate-over-hashmap/src/main.rs:here}}
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);
for (key, value) in &scores {
println!("{key}: {value}");
}
}Ce code affichera chaque paire dans un ordre arbitraire :
Yellow: 50
Blue: 10
Gérer la possession dans les hash maps
Pour les types qui implémentent le trait Copy, comme i32, les valeurs sont copiées dans la hash map. Pour les valeurs possédées comme String, les valeurs seront déplacées et la hash map deviendra propriétaire de ces valeurs, comme démontré dans l’encart 8-22.
fn main() {
use std::collections::HashMap;
let field_name = String::from("Favorite color");
let field_value = String::from("Blue");
let mut map = HashMap::new();
map.insert(field_name, field_value);
// field_name and field_value are invalid at this point, try using them and
// see what compiler error you get!
}Nous ne pouvons pas utiliser les variables field_name et field_value après qu’elles ont été déplacées dans la hash map lors de l’appel à insert.
Si nous insérons des références vers des valeurs dans la hash map, les valeurs ne seront pas déplacées dans la hash map. Les valeurs vers lesquelles les références pointent doivent être valides au moins aussi longtemps que la hash map est valide. Nous parlerons davantage de ces questions dans [“Valider les références avec les durées de vie”][validating-references-with-lifetimes] au chapitre 10.
Mettre à jour une hash map
Bien que le nombre de paires clé-valeur puisse augmenter, chaque clé unique ne peut avoir qu’une seule valeur associée à la fois (mais pas l’inverse : par exemple, l’équipe Blue et l’équipe Yellow pourraient toutes deux avoir la valeur 10 stockée dans la hash map scores).
Lorsque vous voulez modifier les données dans une hash map, vous devez décider comment gérer le cas où une clé a déjà une valeur assignée. Vous pourriez remplacer l’ancienne valeur par la nouvelle, en ignorant complètement l’ancienne valeur. Vous pourriez conserver l’ancienne valeur et ignorer la nouvelle, en n’ajoutant la nouvelle valeur que si la clé n’a pas déjà de valeur. Ou vous pourriez combiner l’ancienne et la nouvelle valeur. Voyons comment faire chacune de ces opérations !
Écraser une valeur
Si nous insérons une clé et une valeur dans une hash map puis insérons cette même clé avec une valeur différente, la valeur associée à cette clé sera remplacée. Même si le code de l’encart 8-23 appelle insert deux fois, la hash map ne contiendra qu’une seule paire clé-valeur car nous insérons la valeur pour la clé de l’équipe Blue les deux fois.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Blue"), 25);
println!("{scores:?}");
}Ce code affichera {"Blue": 25}. La valeur originale de 10 a été écrasée.
Ajouter une clé et une valeur uniquement si la clé n’est pas présente
Il est courant de vérifier si une clé particulière existe déjà dans la hash map avec une valeur, puis de prendre les actions suivantes : si la clé existe dans la hash map, la valeur existante doit rester telle quelle ; si la clé n’existe pas, l’insérer avec une valeur.
Les hash maps ont une API spéciale pour cela appelée entry qui prend en paramètre la clé que vous souhaitez vérifier. La valeur de retour de la méthode entry est une enum appelée Entry qui représente une valeur qui pourrait ou non exister. Disons que nous voulons vérifier si la clé de l’équipe Yellow à une valeur associée. Si ce n’est pas le cas, nous voulons insérer la valeur 50, et de même pour l’équipe Blue. En utilisant l’API entry, le code ressemble à l’encart 8-24.
fn main() {
use std::collections::HashMap;
let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.entry(String::from("Yellow")).or_insert(50);
scores.entry(String::from("Blue")).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 définie pour renvoyer une référence mutable à la valeur correspondant à la clé de l’Entry si cette clé existe, et sinon, elle insère le paramètre comme nouvelle valeur pour cette clé et renvoie une référence mutable à la nouvelle valeur. Cette technique est beaucoup plus propre que d’écrire la logique nous-mêmes et, de plus, fonctionne mieux avec le vérificateur d’emprunt.
L’exécution du code de l’encart 8-24 affichera {"Yellow": 50, "Blue": 10}. Le premier appel à entry insérera la clé pour l’équipe Yellow avec la valeur 50 car l’équipe Yellow n’a pas encore de valeur. Le second appel à entry ne modifiera pas la hash map, car l’équipe Blue a déjà la valeur 10.
Mettre à jour une valeur en fonction de l’ancienne valeur
Un autre cas d’utilisation courant des hash maps est de rechercher la valeur d’une clé puis de la mettre à jour en fonction de l’ancienne valeur. Par exemple, l’encart 8-25 montre du code qui compte combien de fois chaque mot apparaît dans un texte. Nous utilisons une hash map avec les mots comme clés et incrémentons la valeur pour suivre combien de fois nous avons vu ce mot. Si c’est la première fois que nous voyons un mot, nous insérons d’abord la valeur 0.
fn main() {
use std::collections::HashMap;
let text = "hello world wonderful world";
let mut map = HashMap::new();
for word in text.split_whitespace() {
let count = map.entry(word).or_insert(0);
*count += 1;
}
println!("{map:?}");
}Ce code affichera {"world": 2, "hello": 1, "wonderful": 1}. Vous pourriez voir les mêmes paires clé-valeur affichées dans un ordre différent : rappelez-vous de la section [“Accéder aux valeurs dans une hash map”][access] que l’itération sur une hash map se fait dans un ordre arbitraire.
La méthode split_whitespace renvoie un itérateur sur des sous-slices, séparées par des espaces, de la valeur dans text. La méthode or_insert renvoie une référence mutable (&mut V) à la valeur pour la clé spécifiée. Ici, nous stockons cette référence mutable dans la variable count, donc pour assigner une valeur, nous devons d’abord déréférencer count 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
has libraries shared by other Rust users that provide hashers implementing many common hashing algorithms. –> Par défaut, HashMap utilise une fonction de hachage appelée SipHash qui peut fournir une résistance aux attaques par déni de service (DoS) impliquant des tables de hachage1. Ce n’est pas l’algorithme de hachage le plus rapide disponible, mais le compromis pour une meilleure sécurité qui accompagne la baisse de performance en vaut la peine. Si vous profilez votre code et constatez que la fonction de hachage par défaut est trop lente pour vos besoins, vous pouvez passer à une autre fonction en spécifiant un hasher différent. Un hasher est un type qui implémente le trait BuildHasher. Nous parlerons des traits et de leur implémentation au [chapitre 10][traits]. Vous n’avez pas nécessairement besoin d’implémenter votre propre hasher de zéro ; crates.io propose des bibliothèques partagées par d’autres utilisateurs de Rust qui fournissent des hashers implémentant de nombreux algorithmes de hachage courants. 1: https://en.wikipedia.org/wiki/SipHash
Résumé
Les vectors, les strings et les hash maps fournissent une grande quantité de fonctionnalités nécessaires dans les programmes lorsque vous avez besoin de stocker, d’accéder et de modifier des données. Voici quelques exercices que vous devriez maintenant être en mesure de résoudre :
- À partir d’une liste d’entiers, utilisez un vector et renvoyez la médiane (une fois triée, la valeur en position centrale) et le mode (la valeur qui apparaît le plus souvent ; une hash map sera utile ici) de la liste.
- Convertissez des chaînes en Pig Latin. La première consonne de chaque mot est déplacée à la fin du mot et ay est ajouté, donc first devient irst-fay. Les mots qui commencent par une voyelle ont hay ajouté à la fin à la place (apple devient apple-hay). Gardez à l’esprit les détails concernant l’encodage UTF-8 !
- En utilisant une hash map et des vectors, créez une interface textuelle pour permettre à un utilisateur d’ajouter des noms d’employés à un département dans une entreprise ; par exemple, “Add Sally to Engineering” ou “Add Amir to Sales.” Ensuite, permettez à l’utilisateur de récupérer la liste de toutes les personnes d’un département ou de toutes les personnes de l’entreprise par département, triées par ordre alphabétique.
La documentation de l’API de la bibliothèque standard décrit les méthodes que possèdent les vectors, les strings et les hash maps et qui seront utiles pour ces exercices !
Nous abordons des programmes plus complexes dans lesquels les opérations peuvent échouer, c’est donc le moment idéal pour discuter de la gestion des erreurs. C’est ce que nous ferons ensuite !