LabEx
EntrerRejoindre

Stockage de paires clé-valeur avec les tables de hachage Rust

Beginner

This tutorial is from open-source community. Access the source code

Introduction

Bienvenue dans Storing Keys With Associated Values in Hash Maps (Stockage de clés avec des valeurs associées dans des tables de hachage). Ce laboratoire fait partie du Rust Book. Vous pouvez pratiquer vos compétences en Rust sur LabEx.

Dans ce laboratoire, nous allons explorer le concept des tables de hachage et comment elles peuvent être utilisées pour stocker des clés avec des valeurs associées.

Storing Keys with Associated Values in Hash Maps (Stockage de clés avec des valeurs associées dans des tables de hachage)

La dernière de nos collections courantes est la table de hachage (hash map). Le type HashMap<K, V> stocke une correspondance entre des clés de type K et des valeurs de type V en utilisant une fonction de hachage, qui détermine la façon dont ces clés et valeurs sont placées 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 hachage (hash), carte (map), objet (object), table de hachage (hash table), dictionnaire (dictionary) ou tableau associatif (associative array), pour n'en nommer que quelques-uns.

Les tables de hachage sont utiles lorsque vous souhaitez rechercher des données non pas en utilisant un index, comme vous le pouvez avec les vecteurs, 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 table de hachage où chaque clé est le nom d'une équipe et les valeurs sont les scores de chaque équipe. Étant donné 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 trucs sympas 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.

Creating a New Hash Map (Création d'une nouvelle table de hachage)

Une façon de créer une table de hachage vide consiste à utiliser new et à ajouter des éléments avec insert. Dans la liste 8 - 20, nous suivons le score de deux équipes dont les noms sont Blue et Yellow. L'équipe Bleue commence avec 10 points, et l'équipe Jaune commence avec 50 points.

use std::collections::HashMap;

let mut scores = HashMap::new();

scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);

Liste 8 - 20 : Création d'une nouvelle table de hachage et insertion de quelques clés et valeurs

Notez que nous devons d'abord utiliser (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, donc elle n'est pas incluse dans les fonctionnalités automatiquement importées dans la portée par le préambule. Les tables de hachage ont également 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 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. Comme les vecteurs, les tables de hachage sont homogènes : toutes les clés doivent avoir le même type, et toutes les valeurs doivent avoir le même type.

Accessing Values in a Hash Map (Accès aux valeurs dans une table de hachage)

Nous pouvons extraire une valeur de la table de hachage en fournissant sa clé à la méthode get, comme indiqué dans la liste 8 - 21.

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

Liste 8 - 21 : Accès au score de l'équipe Bleue stocké dans la table de hachage

Ici, score aura la valeur associée à l'équipe Bleue, 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 table de hachage, 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 définir 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 table de hachage de la même manière que nous le faisons avec les vecteurs, en utilisant une boucle for :

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

Hash Maps and Ownership (Tables de hachage et propriété)

Pour les types qui implémentent le trait Copy, comme i32, les valeurs sont copiées dans la table de hachage. Pour les valeurs possédées comme String, les valeurs sont déplacées et la table de hachage deviendra le propriétaire de ces valeurs, comme démontré dans la liste 8 - 22.

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!

Liste 8 - 22 : Montrant que les clés et les valeurs sont possédées par la table de hachage une fois qu'elles ont été insérées

Nous ne pouvons pas utiliser les variables field_name et field_value après qu'elles ont été déplacées dans la table de hachage lors de l'appel à insert.

Si nous insérons des références à des valeurs dans la table de hachage, les valeurs ne seront pas déplacées dans la table de hachage. Les valeurs auxquelles les références pointent doivent être valides au moins aussi longtemps que la table de hachage est valide. Nous parlerons plus de ces problèmes dans "Validating References with Lifetimes" (Validation des références avec des durées de vie).

Updating a Hash Map (Mise à jour d'une table de hachage)

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, tant l'équipe Bleue que l'équipe Jaune pourraient avoir la valeur 10 stockée dans la table de hachage scores).

Lorsque vous souhaitez modifier les données dans une table de hachage, vous devez décider comment gérer le cas où une clé a déjà une valeur assignée. Vous pouvez remplacer l'ancienne valeur par la nouvelle, en ignorant complètement l'ancienne valeur. Vous pouvez conserver l'ancienne valeur et ignorer la nouvelle, en ajoutant la nouvelle valeur seulement si la clé n'a pas déjà de valeur. Ou vous pouvez combiner l'ancienne valeur et la nouvelle valeur. Voyons comment faire chacun de ces cas!

Overwriting a Value (Écrasement d'une valeur)

Si nous insérons une clé et une valeur dans une table de hachage, puis que nous insérons la même clé avec une valeur différente, la valeur associée à cette clé sera remplacée. Bien que le code de la liste 8 - 23 appelle insert deux fois, la table de hachage ne contiendra qu'une seule paire clé - valeur car nous insérons la valeur pour la clé de l'équipe Bleue les deux fois.

use std::collections::HashMap;

let mut scores = HashMap::new();

scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Blue"), 25);

println!("{:?}", scores);

Liste 8 - 23 : Remplacement d'une valeur stockée avec une clé particulière

Ce code affichera {"Blue": 25}. La valeur originale de 10 a été écrasée.

Adding a Key and Value Only If a Key Isn't Present (Ajout d'une clé et d'une valeur seulement si la clé n'existe pas)

Il est courant de vérifier si une clé particulière existe déjà dans la table de hachage avec une valeur, puis de prendre les actions suivantes : si la clé existe déjà 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é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 énumération appelée Entry qui représente une valeur qui peut exister ou non. Disons que nous voulons vérifier si la clé de l'équipe Jaune a 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 Bleue. En utilisant l'API entry, le code ressemble à la liste 8 - 24.

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

Liste 8 - 24 : Utilisation de la méthode entry pour insérer seulement si la clé n'a pas déjà de valeur

La méthode or_insert sur Entry est définie pour retourner une référence mutable à la valeur pour la clé Entry correspondante si cette clé existe, et sinon, elle insère le paramètre comme nouvelle valeur pour cette clé et retourne une référence mutable à la nouvelle valeur. Cette technique est beaucoup plus propre que d'écrire la logique nous - mêmes et, en outre, fonctionne mieux avec le vérificateur d'emprunts.

L'exécution du code de la liste 8 - 24 affichera {"Yellow": 50, "Blue": 10}. Le premier appel à entry insérera la clé de l'équipe Jaune avec la valeur 50 car l'équipe Jaune n'a pas déjà de valeur. Le deuxième appel à entry ne changera pas la table de hachage car l'équipe Bleue a déjà la valeur 10.

Updating a Value Based on the Old Value (Mise à jour d'une valeur en fonction de l'ancienne valeur)

Un autre cas d'utilisation courant des tables de hachage consiste à rechercher la valeur d'une clé, puis à la mettre à jour en fonction de l'ancienne valeur. Par exemple, la liste 8 - 25 montre un code qui compte combien de fois chaque mot apparaît dans un texte. Nous utilisons une table de hachage avec les mots comme clés et incrémentons la valeur pour suivre combien de fois nous avons vu ce mot. S'il s'agit de la première fois que nous voyons un mot, nous insérerons d'abord la valeur 0.

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

Liste 8 - 25 : Comptage des occurrences de mots à l'aide d'une table de hachage qui stocke les mots et les compteurs

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 "Accessing Values in a Hash Map" (Accès aux valeurs dans une table de hachage) que l'itération sur une table de hachage se fait dans un ordre arbitraire.

La méthode split_whitespace retourne un itérateur sur les sous - tranches, séparées par des espaces, de la valeur dans text. La méthode or_insert retourne 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 à cette variable, nous devons d'abord déréférencer count en utilisant l'astérisque (*). La référence mutable sort de portée à la fin de la boucle for, donc tous ces changements sont sûrs et autorisés par les règles d'emprunt.

Hashing Functions (Fonctions de hachage)

Par défaut, HashMap utilise une fonction de hachage appelée SipHash qui peut offrir une résistance aux attaques par déni de service (DoS - Denial-of-Service) impliquant des tables de hachage. Ce n'est pas le plus rapide algorithme de hachage disponible, mais le compromis entre une meilleure sécurité et la baisse de performance est justifié. Si vous effectuez un profilage de votre code et que vous 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 autre hasher (fonction de hachage). Un hasher est un type qui implémente le trait BuildHasher. Nous parlerons des traits et de leur implémentation au chapitre 10. Vous n'avez pas nécessairement à implémenter votre propre hasher depuis le début ; https://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.

Summary (Résumé)

Félicitations! Vous avez terminé le laboratoire « Storing Keys With Associated Values in Hash Maps » (Stockage de clés avec des valeurs associées dans des tables de hachage). Vous pouvez pratiquer davantage de laboratoires sur LabEx pour améliorer vos compétences.