Rust HashMap : comment rechercher et insérer efficacement des données

Comment rechercher et insérer efficacement des données dans un HashMap en Rust : un coup d'œil sous le capot

Avez-vous déjà écrit du code en Rust en pensant : "Comment puis-je vérifier si une clé existe dans un HashMap, et si ce n'est pas le cas, insérer une nouvelle valeur ?" Cette question hante des milliers de développeurs sur Stack Overflow. Et pour cause : une solution naïve peut tuer les performances de votre application. Aujourd'hui, nous ne nous contentons pas de donner la réponse — nous allons plonger à l'intérieur du HashMap de Rust et voir comment il est conçu. Vous découvrirez pourquoi utiliser get et insert séparément est une source de douleur, et comment utiliser correctement l'API entry.

Cet article s'adresse à ceux qui connaissent déjà les bases de Rust, mais qui souhaitent comprendre plus en profondeur le fonctionnement des collections sous le capot. C'est parti !

Le problème : deux appels — double travail

Imaginez une tâche typique : vous avez un HashMap dans lequel vous devez compter le nombre d'occurrences de mots dans un texte. L'approche naïve ressemble à ceci :

use std::collections::HashMap;\n\nfn count_words_naive(words: &[&str]) -> HashMap<String, u32> {\n    let mut map = HashMap::new();\n    \n    for word in words {\n        if map.contains_key(*word) {\n            let count = map.get(*word).unwrap();\n            map.insert(word.to_string(), count + 1);\n        } else {\n            map.insert(word.to_string(), 1);\n        }\n    }\n    \n    map\n}\n

Qu'est-ce qui ne va pas ici ? Nous accédons deux fois au HashMap pour chaque mot : d'abord contains_key, puis get, et ensuite encore insert. Chaque appel implique le calcul du hachage, la recherche dans le seau et la comparaison des clés. Pour un texte court, cela est imperceptible, mais pour des millions d'entrées, c'est une catastrophe.

Sous le capot : comment est structuré le HashMap en Rust

Pour comprendre pourquoi c'est mauvais, examinons comment fonctionne le HashMap en Rust. Il est basé sur une table de hachage à adressage ouvert (Robin Hood hashing). Voici les points clés :

\n
• Hachage : La clé est transformée en un code de hachage à l'aide d'une fonction de hachage (par défaut SipHash-2-4).
\n
• Seaux (buckets) : Le code de hachage détermine l'indice dans un tableau de seaux. En Rust, chaque seau est un emplacement qui peut être vide, occupé ou supprimé.
\n
• Collisions : Lorsque deux clés différentes tombent dans le même seau, le Robin Hood hashing tente de "voler" la place d'un voisin plus "riche" afin d'équilibrer les distances de recherche.
\n
• Redimensionnement : Lorsque la table est pleine (facteur de charge ~0.9), elle est multipliée par 2 et tous les éléments sont re-hachés.
\n

Imaginez maintenant : chaque appel à get ou insert est un cycle complet : hachage, recherche par index, comparaison des clés (peut-être plusieurs fois à cause des collisions). Deux appels = double travail. Et si un redimensionnement se produit entre les appels ? Triple travail !

La solution : l'API Entry — votre bouée de sauvetage

Rust propose une solution élégante — l'API Entry. C'est un mécanisme qui permet d'effectuer la recherche et, éventuellement, l'insertion en une seule passe. Voici à quoi ressemble le code correct pour compter les mots :

use std::collections::HashMap;\n\nfn count_words_efficient(words: &[&str]) -> HashMap<String, u32> {\n    let mut map = HashMap::new();\n    \n    for word in words {\n        let entry = map.entry(word.to_string());\n        *entry.or_insert(0) += 1;\n    }\n    \n    map\n}\n

Concis, élégant, efficace. Mais comment cela fonctionne-t-il sous le capot ? Décomposons-le étape par étape.

Étape 1 : La méthode entry()

L'appel map.entry(key) retourne une énumération Entry, qui peut être dans deux états :

\n
• Entry::Occupied — la clé existe déjà dans la table.
\n
• Entry::Vacant — la clé n'existe pas, et nous avons un emplacement prêt pour l'insertion.
\n

Important : à ce