Utiliser HashMap en C++

1. Utiliser HashMap avec std::map en C++
2. Utiliser HashMap avec std::unordered_map en C++
3. Principales différences et quand utiliser chaque carte en C++

Le HashMap est une structure de données vitale contenant des paires clé-valeur où une valeur peut être récupérée à l’aide de la clé appropriée. Chaque clé est mappée à une valeur particulière dans un HashMap.

En utilisant des clés lors des itérations, nous pouvons accéder aux valeurs correspondantes beaucoup plus rapidement. Par conséquent, le HashMap est considéré comme une structure de données efficace et essentielle lors de la récupération de valeurs, avec à la fois une clé et une valeur de tout type.

Avant C++ 11, une table de hachage standard n’était pas présente dans la bibliothèque standard de C++, mais des implémenteurs quelque peu différents avaient des variantes non standard de la table de hachage, souvent appelées HashMap. Avec C++ 11, une implémentation standard de la table de hachage a été ajoutée à la bibliothèque standard.

Néanmoins, en raison de diverses variantes de la table de hachage en tant que HashMap provenant de différentes bibliothèques, il a été décidé d’utiliser un nom distinct pour appeler la nouvelle implémentation afin d’éviter toute confusion.

Par conséquent, en C++, std::unordered_map est le nom alternatif pour le HashMap, mais une autre carte utilise le concept de paire clé-valeur, le std::map.

Il existe des différences essentielles entre std::unordered_map et std::map. Comme son nom l’indique, les éléments à l’intérieur de std::unordered_map ne sont pas ordonnés tandis que les éléments de std::map sont ordonnés.

Utiliser HashMap avec std::map en C++

std::map appartient à la catégorie des conteneurs associatifs où les éléments sont stockés dans des paires clé-valeur mappées. Dans std::map et std::unordered_map, la clé doit toujours être unique, mais il peut y avoir plusieurs clés uniques où la valeur mappée est similaire.

Le std::map est implémenté à l’aide de Arbre de recherche binaire auto-équilibré (arbre AVL / arbre rouge-noir). La principale caractéristique de BST (Self-Balancing Binary Search Tree) est que la hauteur est toujours automatiquement maintenue à un minimum lors de l’insertion et de la suppression d’éléments.

Dans std::map, la complexité temporelle moyenne dépend logarithmiquement du nombre d’éléments stockés ; par conséquent, il faut en moyenne un temps O(log n) pour qu’une opération se produise. Dans O(log n), O désigne la notation Big O, et n désigne le nombre d’éléments stockés.

Par conséquent, les BST sont utiles lors de la création et de la maintenance de listes ordonnées.

Exemple:

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main() {
  map<int, string> Players;

  Players.insert(std::pair<int, string>(2, "Lin Dan"));
  Players.insert(std::pair<int, string>(1, "Chen Long"));

  cout << "Number of Players " << Players.size() << endl;
  for (map<int, string>::iterator it = Players.begin(); it != Players.end();
       ++it) {
    cout << (*it).first << ": " << (*it).second << endl;
  }
}

Production:

Number of Players 2
1: Chen Long
2: Lin Dan

Utiliser HashMap avec std::unordered_map en C++

std::unordered_map est implémenté à l’aide de la table de hachage en C++. Les tables de hachage appartiennent également aux conteneurs associatifs. Les valeurs mappées sont stockées dans une table de hachage dans un tableau de compartiments ou d’emplacements, à partir desquels les valeurs nécessaires peuvent être récupérées.

Cette indexation se fait à l’aide de la fonction de hachage, code de hachage. La complexité temporelle moyenne pour la recherche, l’insertion et la suppression d’un std::unordered_map est de O(1), où O est la notation Big O, c’est la principale raison pour laquelle le std::unordered_map est très efficace.

Exemple:

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
  unordered_map<string, int> info;

  info["Age"] = 18;
  info["Year"] = 2022;
  info["Number of Players"] = 15;

  for (auto x : info) cout << x.first << " " << x.second << endl;
}

Production:

Number of Players 15
Year 2022
Age 18

Principales différences et quand utiliser chaque carte en C++

Lorsque std::unordered_map et std::map sont comparés, l’écart d’efficacité entre les deux est énorme.

std::unordered_map a clairement un avantage de performance considérable sur std::map. Ceci est principalement dû au fait que std::unordered_map peut adresser directement la valeur lorsqu’elle est placée dans des emplacements et, par conséquent, n’a pas d’ordre à préserver.

Par contre, un std::map a un ordre qu’il faut conserver ; par conséquent, cela prend plus de temps. Cette efficacité peut ne pas être visible pour les petits ensembles de données, mais cette différence est énorme pour les grands ensembles de données.

std::unordered_map peut être utilisé lors de l’accès à un seul élément à partir d’un ensemble de données ou pour conserver un nombre d’éléments lorsqu’aucun ordre n’est requis.

std::map présente également quelques avantages par rapport à std::unordered_map. Généralement, les BST peuvent être implémentés plus rapidement qu’une table de hachage, et nous pouvons le faire de notre manière préférée, mais pour le hachage, nous devons nous appuyer fortement sur les bibliothèques.

Par conséquent, std::map peut être implémenté facilement par rapport à std::unordered_map. De plus, quand il s’agit de trier, il est beaucoup plus facile de trier les clés dans std::map que dans std::unordered_map parce que inorder traversing n’est pas une opération naturelle pour les tables de hachage, mais c’est pour les BST.

std::map peut être utilisé dans des situations telles que l’impression de données dans un ordre trié, où les données doivent être triées pour les requêtes de recherche, les statistiques de commande, etc.

std::map et std::unordered_map présentent certaines similitudes et différences qui peuvent être manipulées en fonction des besoins du moment.