Il s'agit de la deuxième partie de la série sur le choix du conteneur associatif (dictionnaire) le plus adapté en C++23. Dans la première partie, nous avons abordé les conteneurs ordonnés , et dans cette partie, nous aborderons en détail les conteneurs non ordonnés.

Conteneurs non ordonnés

Ces conteneurs ne fournissent aucun ordre défini pour leurs clés. De plus, l'ordre des clés peut changer à chaque modification, le programme ne doit donc jamais s'y fier. Ces conteneurs sont toujours implémentés sous forme de tables de hachage.

En général, lors de l'ajout, de la suppression ou de la recherche d'une clé, une table de hachage calcule d'abord une valeur de hachage intégrale à partir de cette clé à l'aide de la fonction de hachage. Le hachage (ou plutôt sa partie) est ensuite utilisé comme index dans le tableau pré-alloué contigu. Chaque entrée de ce tableau est appelée un bucket . Certaines entrées de ce tableau seront vides, certaines contiendront un seul élément et certaines peuvent correspondre à plusieurs éléments en raison de collisions de hachage. Cela se produit lorsque différentes clés ont des valeurs de hachage qui pointent vers le même index de tableau. Les tables de hachage utilisent diverses stratégies pour gérer les collisions de hachage (voir cet article de Wikipédia ). Le nombre d'éléments dans la table de hachage divisé par la taille totale du tableau est appelé le facteur de charge . Plus le facteur de charge est élevé, plus les collisions de hachage possibles sont nombreuses avec chaque élément nouvellement inséré.

Contrairement aux conteneurs ordonnés, les tables de hachage ne prennent pas en charge les requêtes de plage, les opérations de classement/sélection, l'itération sur les clés dans l'ordre et la recherche de la clé plus petite/plus grande que la clé donnée. En retour, les tables de hachage atteignent les meilleures performances réalisables : la complexité temporelle des opérations de recherche/insertion/suppression est amortie O(1) ). Je dis « amortie » ici, car lorsque le nombre d'éléments devient trop important, une table de hachage doit réorganiser son contenu pour réduire le facteur de charge (en augmentant effectivement le tableau de compartiments). La complexité temporelle du réorganisation est O(n) . Cependant, on s'attend à ce que cela se produise rarement, donc en moyenne, chaque opération est toujours O(1) . Une autre raison de performances potentiellement réduites est une fonction de hachage avec une mauvaise distribution, ce qui augmentera la fréquence des collisions.

Cartes de hachage standard

À partir de C++11, la bibliothèque standard fournit les tables de hachage suivantes : std::unordered_map ( link ), std::unordered_set ( link ), std::unordered_multimap ( link ) et std::unordered_multiset ( link ). Les tables associent une clé à la valeur, tandis que les ensembles ne stockent que la clé et sont utiles pour vérifier si la clé est présente dans le conteneur, mais pas pour récupérer la valeur associée. Les conteneurs multiples permettent de stocker plusieurs clés en double.

Tous les conteneurs non ordonnés standard sont basés sur des nœuds et utilisent un chaînage séparé pour gérer les collisions de hachage, ce qui signifie qu'ils stockent chaque clé ou paire clé-valeur dans un nœud de liste chaînée distinct. La mémoire de chaque nouveau nœud est allouée individuellement, ce qui n'est pas particulièrement efficace. Cela rend également la structure de données peu adaptée au cache du processeur, car chaque accès à la clé nécessite une indirection supplémentaire. Voici à quoi peut ressembler la structure interne unordered_map :

Sur la gauche, il y a un tableau de buckets, qui est pré-alloué à une taille fixe ( 8 dans notre exemple). Initialement, tous les buckets sont vides. Lorsque nous commençons à ajouter des éléments à la table de hachage, certains buckets seront occupés. Dans l'exemple ci-dessus, il y a un élément avec la clé 10 (qui est entré dans le bucket 1 ), et deux éléments avec les clés 50 et 256 , tous deux ont fini dans le même bucket 3 parce que leurs valeurs de hachage sont entrées en collision. Il y a aussi un élément avec la clé 3 , qui a atterri dans le bucket 6 Chaque bucket pointe vers la liste chaînée, qui ne contient idéalement pas plus d'un élément. Les buckets 0 , 2 , 4 , 5 et 7 sont vides et pointent vers nullptr .

Supposons que nous devons trouver la valeur de la clé 256 .

• Tout d'abord, la carte calcule le hachage de la clé et obtient le reste en divisant la valeur de hachage par le nombre total de buckets ( 8 dans notre cas). Dans notre exemple, la valeur restante est 3 .
• Ensuite, la carte commence à lire les éléments de la liste chaînée pointée par le bucket 3 .
• Le premier élément a la clé 50 , qui n'est pas la même que la 256 que nous recherchons, donc la carte va continuer à itérer. L'élément suivant a la clé 256 , qui est exactement celle dont nous avons besoin. La valeur correspondante est xyz .
• Si la clé ne se trouvait pas dans le dictionnaire, la carte atteindrait un bucket vide ou parcourrait la liste chaînée jusqu'à la fin. Dans les deux cas, la carte renverrait un itérateur end , indiquant que la clé n'existe pas.

Vous remarquerez peut-être que le dernier élément de chaque liste pointe vers le premier élément de la liste suivante. Cela est fait dans certaines implémentations pour améliorer l'efficacité de l'itération. Au lieu de vérifier bucket par bucket lors de l'itération sur tous les éléments de la table de hachage, nous pouvons utiliser ces connexions pour passer d'une liste chaînée non vide à une autre beaucoup plus rapidement.

Si nous continuons à ajouter des éléments à la table de hachage ci-dessus, à un moment donné, le facteur de charge deviendra trop élevé (par exemple, 80 %) et la table de hachage décidera de procéder à un nouveau hachage. Elle agrandira le tableau pré-alloué (par exemple de 8 à 16 éléments), recalculera les hachages pour tous les éléments existants et placera les éléments dans les nouveaux compartiments.

Les conteneurs standards offrent des garanties de stabilité des références et des itérateurs, mais elles sont plus faibles que celles offertes par les conteneurs ordonnés. Les références aux éléments existants ne sont jamais invalidées. Les itérateurs aux éléments existants ne peuvent être invalidés que lorsque l'ajout d'un nouvel élément provoque un rehash, ou lorsque le rehash est déclenché manuellement :

 #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; auto& value = map["abc"]; auto valueIt = map.find("abc"); // Might cause a rehash if the load factor // is too high map.emplace("zzz", 1000); // Triggers the rehash manually map.rehash(1000); // References remain valid in any case: std::cout << value << "\n"; // Iterators are invalidated: the line below // is undefined behavior and might crash std::cout << valueIt->second << "\n"; }

Depuis C++17, les conteneurs non ordonnés permettent la manipulation des nœuds : il est possible de prendre un nœud d'une carte et de le déplacer vers une autre carte sans copier la clé et la valeur :

 #include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> map1{ {"test", 123}, {"xyz", 456}, {"abc", 10} }; // Take the node from map1: auto node = map1.extract("xyz"); // We can even change its key // (we can also change the value // if needed): node.key() = "xyzxyz"; std::unordered_map<std::string, int> map2; // Insert the node into another map: map2.insert(std::move(node)); // Prints "xyzxyz: 456": for (const auto& [k, v] : map2) { std::cout << k << ": " << v << "\n"; } }

Voici ce qui se passe dans le programme ci-dessus :

Une autre stratégie pour gérer les collisions de hachage est appelée adressage ouvert . Dans les cartes de hachage à adressage ouvert, chaque compartiment stocke au plus un élément. Si le compartiment est déjà occupé, l'élément avec la même valeur de hachage va dans un autre compartiment libre. Ces cartes de hachage tentent de regrouper les éléments dans des blocs de mémoire contigus pour améliorer l'efficacité et rendre la structure de données plus conviviale pour le cache du processeur. La bibliothèque standard C++ ne fournit pas de cartes de hachage à adressage ouvert, mais il existe de nombreuses alternatives tierces.

Cartes de hachage tierces

Boost.Unordered est une bibliothèque impressionnante qui fournit une large gamme d'implémentations de cartes de hachage.

Il existe boost::unordered_set , boost::unordered_map , boost::unordered_multiset et boost::unordered_multimap , qui sont des analogues des conteneurs std , et tout ce qui est écrit ci-dessus s'applique à eux. Ces conteneurs utilisent une structure interne un peu plus complexe avec des « groupes de compartiments » pour améliorer l'efficacité des itérations.

La bibliothèque fournit également boost::unordered_node_set , boost::unordered_node_map , boost::unordered_flat_set et boost::unordered_flat_map , qui sont des conteneurs d'adressage ouverts. La structure interne est différente des variantes d'adressage ouvert :

Vous pouvez en savoir plus sur la structure interne dans cet article de blog .

Les conteneurs basés sur des nœuds ( boost::unordered_node_set , boost::unordered_node_map ) utilisent toujours des nœuds, vers lesquels pointent les buckets. Ces conteneurs fournissent la même stabilité d'itérateur et de référence garantie que les conteneurs std et fournissent également la même API pour la manipulation des nœuds (c'est-à-dire la méthode extract ).

Dans les conteneurs plats ( boost::unordered_flat_set , boost::unordered_flat_map ), les clés et les valeurs sont stockées directement dans le tableau bucket. Les conteneurs plats sont les plus efficaces, mais offrent les garanties les plus faibles : les itérateurs et les références à tous les éléments sont invalidés lors du rehachage. L'API de manipulation des nœuds n'est pas du tout fournie. Les conteneurs plats peuvent utiliser plus de mémoire que ceux basés sur des nœuds, en particulier si la clé ou la valeur sizeof est grande.

Folly F14 (fournie par Meta) est une autre bibliothèque tierce qui implémente des conteneurs à adressage ouvert. Il existe quelques variantes de dictionnaire qui sont très proches des conteneurs de la bibliothèque Boost décrits ci-dessus :

• folly::F14NodeSet est identique à boost::unordered_node_set , folly::F14NodeMap est identique à boost::unordered_node_map .
• folly::F14ValueSet est identique à boost::unordered_flat_set , et folly::F14ValueMap est identique à boost::unordered_flat_map .
• folly::F14VectorMap / folly::F14VectorSet conserve les clés/valeurs regroupées dans un tableau contigu, et les buckets contiennent des index dans ce tableau.
• folly::F14FastMap / folly::F14FastSet est une classe parapluie. Elle choisit l'implémentation la plus efficace ( F14Value ou F14Vector ) en fonction des paramètres que vous spécifiez (tels que les types de clé et de valeur).

Une fonctionnalité intéressante et efficace des tables de hachage F14 est le pré-hachage . Par exemple, si vous devez rechercher la même clé plusieurs fois et que son hachage est coûteux (par exemple, une clé est une chaîne), vous pouvez la pré-hacher une fois, puis utiliser le F14HashToken dans tous les appels de table de hachage ultérieurs pour éviter de re-hacher la même clé plusieurs fois. Le point de départ est la méthode prehash ( lien ).

Vous pouvez en savoir plus sur la structure interne des conteneurs de hachage F14 dans cet article de blog FB .

La bibliothèque Abseil Swiss Tables (fournie par Google) implémente également des conteneurs de hachage plats et basés sur des nœuds à adressage ouvert : absl::flat_hash_map , absl::flat_hash_set , absl::node_hash_map , absl::node_hash_set . Ils sont similaires à ceux de Boost et F14. Vous pouvez en savoir plus à leur sujet ici et ici .

Une bibliothèque ankerl moins connue ( github ) prétend être très efficace dans la plupart des scénarios. L'auteur de cette bibliothèque fournit des résultats de référence complets pour de nombreuses cartes de hachage dans différents cas d'utilisation ( article de blog ). Vous pouvez suivre ces résultats, mais prenez-les avec des pincettes. Testez toujours la carte de hachage que vous choisissez dans l'environnement de production. Les tests sont toujours synthétiques et ne couvrent pas les cas où le processeur et la mémoire effectuent d'autres tâches en plus des opérations de carte de hachage. Les tests ne couvrent pas non plus les cas où diverses parties de la mémoire de la carte de hachage ne se trouvent pas dans le cache du processeur, ce qui se produit fréquemment dans les programmes réels.

Qualité de la fonction de hachage

La qualité de la fonction de hachage est importante pour maintenir la complexité temporelle des opérations de recherche O(1) . Les cartes de hachage plates sont particulièrement sensibles à la qualité de la fonction de hachage. Une fonction de hachage idéale peut être définie comme ceci : si un seul bit de la clé change, la valeur de hachage correspondante changera la moitié de ses bits de manière aléatoire. Une telle fonction de hachage est appelée avalanche .

Malheureusement, certaines implémentations de la bibliothèque standard C++ des fonctions de hachage d'entiers et de pointeurs ne sont pas des fonctions d'avalanche. Par exemple, libstdc++ renvoie simplement la valeur du pointeur ou de l'entier directement sans aucune transformation supplémentaire : github .

Les tables de hachage avancées, telles que les implémentations boost et F14 , traitent ce problème en introduisant le trait hash_is_avalanching . Si la fonction de hachage ne se déclare pas comme avalanching, la table de hachage effectuera une étape de mixage supplémentaire pour améliorer la qualité du hachage. Cela a un coût supplémentaire. Si vous implémentez une fonction de hachage personnalisée et que vous savez qu'elle est de bonne qualité, vous pouvez la marquer comme avalanching comme indiqué dans cet exemple . Boost utilise le nom de propriété is_avalanching et la propriété F14 est nommée folly_is_avalanching . Idéalement, vous devriez ajouter les deux.

Si vous utilisez les types de clés pris en charge prêts à l'emploi (par exemple, string , int , pointeurs) et les fonctions de hachage par défaut fournies par boost ou F14 , ils seront déjà marqués correctement selon les besoins, et vous n'aurez pas besoin d'y penser à moins que vous ne décidiez d'implémenter un type de clé personnalisé, qui nécessitera une fonction de hachage personnalisée.

Sécurité des fils

En général, tous les conteneurs ci-dessus ne sont pas thread-safe et vous devrez implémenter une synchronisation externe (par exemple, en utilisant des mutex) si un thread peut modifier la table de hachage lorsqu'un autre thread y accède.

Si tous les threads ne lisent que la carte, aucune synchronisation n'est nécessaire. Assurez-vous d'appeler uniquement les méthodes marquées avec const . Toutes les méthodes non const peuvent modifier le conteneur. Gardez à l'esprit que operator[] n'est pas const et modifiera le conteneur. Un piège courant dans le code multithread est :

 std::unordered_map<std::string, bool> map; // ... if (map["key"]) { // ... }

Dans le code ci-dessus, l'objectif est de vérifier si la valeur correspondant à la key est true . Cependant, map["key"] ajoutera la key à la map si elle n'y est pas déjà. La valeur nouvellement ajoutée sera définie sur default ( false dans l'exemple ci-dessus). Cela signifie qu'un tel code n'est pas thread-safe et n'est pas trop optimal. Une manière plus efficace et thread-safe de vérifier la même condition est la suivante :

 if (auto it = map.find("key"); it != map.end() && it->second == true) { // ... }

• Ici, nous obtenons d'abord l'itérateur vers l'élément identifié par la « clé ».
• Nous vérifions ensuite si l'élément existe dans la carte ( it != map.end() ).
• Si c'est le cas, nous vérifions finalement sa valeur ( it->second == true ).

Dans cet exemple, find et end ne modifient pas la carte, et la recherche devient thread-safe. Si l'objectif était uniquement de vérifier si la clé existe dans la carte, vous pourriez simplement appeler map.contains("key") .

Cartes non ordonnées thread-safe

Il existe quelques implémentations de cartes de hachage thread-safe.

• Une option est boost::concurrent_flat_set et boost::concurrent_flat_map de la bibliothèque Boost.Unordered . Les conteneurs Boost fournissent une API basée sur les visites qui est très différente de l'API fournie par la bibliothèque standard C++.
• Une autre option est folly::ConcurrentHashMap ( github ). Folly essaie de garder son API aussi proche que possible des conteneurs non ordonnés standard C++.
• libcds est une grande bibliothèque de conteneurs sans verrou qui fournit plusieurs implémentations de tables de hachage sans verrou (par exemple MichaelHashMap , SkipListMap , SkipListSet , FeldmanHashMap , FeldmanHashSet ). Cette bibliothèque n'a pas été mise à jour depuis un certain temps et ne fournit pas de documentation détaillée, mais je la partage toujours car les conteneurs qu'elle propose sont uniques. Si votre cas d'utilisation implique une forte contention sur une table de hachage, essayez ces dictionnaires sans verrou proposés par libcds .
• Si l'efficacité n'est pas un problème, vous pouvez synchroniser les accès aux cartes non thread-safe à l'aide de mutex. Vous pouvez également éviter complètement les accès simultanés, ce qui est souvent plus efficace que l'utilisation de conteneurs thread-safe ou l'ajout d'une synchronisation.

Lequel dois-je utiliser ?

Voyons les points résumés qui expliquent comment choisir le conteneur le plus approprié.

• Si vous devez associer une clé à la valeur, choisissez une carte , sinon, utilisez un ensemble .
• S'il est nécessaire de conserver des clés en double dans la carte, utilisez plusieurs conteneurs.
• Si vous avez besoin des garanties de stabilité d'itérateur et de référence les plus strictes possibles, utilisez des conteneurs basés sur des nœuds std , boost , folly ou abseil (tels que std::unordered_map , boost::unordered_map , boost::unordered_node_map ou folly::F14NodeMap ). boost::unordered_node_... et folly seront probablement les plus efficaces.
• Si la stabilité de l'itérateur et de la référence n'est pas importante (ce qui signifie que vous ne stockez pas d'itérateurs, de références ou de pointeurs vers des éléments de carte/ensemble en externe ou que vous ne vous attendez pas à ce qu'ils restent valides après la modification de la carte), alors choisissez un conteneur plat (tel que boost::unordered_flat_map ou folly::F14FastMap ).
• Les conteneurs plats utilisent plus de mémoire que ceux basés sur des nœuds, en particulier lorsque sizeof de la clé et/ou de la valeur est importante. Si l'utilisation de la mémoire est un problème, utilisez plutôt des conteneurs basés sur des nœuds.
• Les conteneurs F14 fournissent une fonctionnalité de pré-hachage pour une efficacité accrue. Si vous recherchez/ajoutez/supprimez des clés identiques plusieurs fois, F14 permettra d'économiser sur le coût de hachage en pré-hachant les clés.
• Tous les points ci-dessus s'appliquent à l'utilisation d'un conteneur monothread (ou à un accès en lecture multithread sans modifications simultanées). Si des modifications multithread sont requises, sélectionnez l'une des options thread-safe répertoriées ci-dessus. Elles peuvent présenter des performances variables dans le code de production réel, pensez donc à les tester dans votre application et à comparer les résultats.