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

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

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.

Une autre façon de construire une table de hachage est d'utiliser les itérateurs et la méthode collect sur un vecteur de tuples, où chaque tuple représente une clé et sa valeur. Nous aborderons en détail les itérateurs et leurs méthodes associées dans une section du chapitre 13. La méthode collect regroupe les données dans quelques types de collections, dont HashMap. Par exemple, si nous avions les noms des équipes et les scores initiaux dans deux vecteurs séparés, nous pourrions utiliser la méthode zip pour créer un itérateur de tuples où “Bleu” est associé à 10, et ainsi de suite. Ensuite, nous pourrions utiliser la méthode collect pour transformer cet itérateur de tuples en table de hachage, comme dans l'encart 8-21.

fn main() {
    use std::collections::HashMap;

    let equipes = vec![String::from("Bleu"), String::from("Jaune")];
    let scores_initiaux = vec![10, 50];

    let mut scores: HashMap<_, _> =
        equipes.into_iter().zip(scores_initiaux.into_iter()).collect();
}

Encart 8-21 : création d'une table de hachage à partir d'une liste d'équipes et d'une liste de scores

L'annotation de type HashMap<_, _> est nécessaire ici car collect peut générer plusieurs types de structures de données et Rust ne sait pas laquelle vous souhaitez si vous ne le précisez pas. Mais pour les paramètres qui correspondent aux types de clé et de valeur, nous utilisons des tirets bas, et Rust peut déduire les types que la table de hachage contient en fonction des types des données présentes dans les vecteurs. Dans l'encart 8-21, le type des clés sera String et le type des valeurs sera i32, comme dans l'encart 8-20.

Les tables de hachage et la possession

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 !
}

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

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 une section du chapitre 10.

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-23.

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

Encart 8-23 : récupération du score de l'équipe Bleu, stocké dans la table de hachage

Dans notre cas, score aura la valeur qui est associée à l'équipe Bleu, et le résultat sera Some(&10). Le résultat est encapsulé dans un Some car 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. Le programme doit gérer cette Option d'une des manières dont nous avons parlé au chapitre 6.

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

Modifier une table de hachage

Bien que le nombre de paires de clé-valeur puisse augmenter, chaque clé ne peut être associée qu'à une seule valeur à la fois. 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-24 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);
}

Encart 8-24 : remplacement d'une valeur stockée sous une clé spécifique

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 a déjà une valeur, et si ce n'est pas le cas, de lui associer une valeur. 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-25.

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

Encart 8-25 : utilisation de la méthode entry pour ajouter la clé uniquement si elle n'a pas déjà de valeur associée

La 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-25 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-26 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);
}

Encart 8-26 : comptage des occurrences des mots en utilisant une table de hachage qui stocke les mots et leur quantité

Ce code va afficher {"monde": 2, "bonjour": 1, "magnifique": 1, "le": 1}. La méthode split_whitespace va itérer 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 hachage¹. 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.

https://en.wikipedia.org/wiki/SipHash

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 l et est rétablie à la fin du mot suivie du suffixe argotique “em” ; ainsi, “bonjour” devient “lonjourbem”. Si le mot commence par une voyelle, ajouter un l au 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 !

Le langage de programmation Rust