Complexité du temps de hashmap et C ++

«La complexité du temps est l'exécution relative d'un codage. Avant de discuter de la complexité temporelle d'un hashmap, le lecteur doit connaître le rôle d'une fonction de hachage dans une carte de hachage.

En théorie, une fonction de hachage convertirait les données de n'importe quelle taille (tout grand texte) en un nombre entier qui est supérieur ou égal à zéro. Différents grands textes sont convertis en différents nombres. L'intérêt pour cet article n'est pas de convertir un gros texte en un entier. L'intérêt pour cet article est de cartographier les données de toute taille à un nombre entier. Cela comprend la possibilité de cartographier (conversion) un seul numéro en un autre numéro unique.

Les données (à gauche) à mapper sont appelées clés. Ainsi, chaque clé est convertie en un nombre entier qui est égal ou supérieur à zéro. Imaginez qu'il y a cinq clés qui ont été converties en chiffres: 0, 1, 2, 3 et 4. Si ces clés sont les index d'un tableau contenant cinq valeurs du même type, ces clés ont été mappées à cinq valeurs différentes.

Et donc, qu'est-ce qu'un hashmap (carte de hachage)? Un hashmap est une structure de données composée de paires de clés / valeur, où chaque clé a été mappée à une valeur. En fait, chaque clé a été hachée dans un certain nombre d'un tableau, et la cellule du tableau correspondant doit maintenir une valeur. Dans le sujet Hashmap, l'emplacement de la cellule de chaque indice de tableau est appelé un seau."

Problème de collision et résolution

En pratique, différentes clés peuvent être mappées à plus d'une valeur. Considérez le cas de dix clés pour un tableau de longueur 5, avec 5 seaux. Dans ce cas, une structure comme un tableau de terrains serait construite. Chaque seau serait en fait un tableau de longueur 2. Deux clés partageraient le même seau. Dans ce partage, la première clé se mlongerait vers le premier élément de tableau pour le seau, et la deuxième clé se dresserait vers le deuxième élément de tableau pour le même seau. Ce schéma résout le problème de collision, et dix clés ont été cartographiées à 10 valeurs, comme prévu.

Pour le reste de cet article, imaginez un hashmap avec le problème de collision résolu. Le but de cet article est de fournir la complexité du temps du codage pour l'insertion dans un hashmap, le codage de suppression dans un hashmap et le codage pour la recherche dans un hashmap. La complexité temporelle de HashMap est décrite avec ces trois fonctionnalités. La cartographie de hash pour C ++ est également abordée dans cet article.

Paires de clés / valeur et de valeur_type

Imaginez un hashmap de noms de personnes contre les numéros de téléphone pour un annuaire téléphonique. Les noms des utilisateurs de téléphone sont de type de données, texte (chaîne). Les valeurs des numéros de téléphone sont du type de données et du texte, en supposant que les espaces et / ou les traits. Les noms d'utilisateur sont les clés et les numéros de téléphone sont les valeurs. N'oubliez pas que, en interne, les clés sont en fait converties en index de tableau dans la structure de données. Ainsi, le type de clé est le texte, et le type de valeur est toujours du texte.

Type de valeur signifie que la paire de touches / valeur comme un élément. En C ++, chaque élément (paire) est pointé par un itérateur. Donc, en C ++, il y a aussi un mappage itérateur / paire,. Une paire (clé et sa valeur) est appelée type de valeur.

Complexité du temps pour l'insertion de hashmap

La complexité du temps pour un hashmap ne fait pas référence au temps pris pour créer le hashmap. Il se réfère au temps pris pour insérer, supprimer ou rechercher une valeur basée sur une clé donnée. La complexité du temps est normalement écrite en utilisant la notation Big-O. La notation Big-O se compose de O en majuscules, suivie de parenthèses. Dans les parenthèses sont des variables et des nombres, qui donnent le temps d'exécution relatif pour un morceau de code et pas nécessairement tout le programme. Avec le hashmap, k signifie le nombre de clés, et n signifie le nombre de seaux. N'oubliez pas qu'avec certains hashmaps, un seau peut avoir plus d'une valeur pour les clés différentes en conséquence. Dans ce cas, plus d'une clé est hachée dans le même index de seau. Un bon hashmap résout cette collision.

Insertion

Compte tenu d'une nouvelle clé, la complexité du temps de cas moyen pour avoir la clé et sa valeur correspondante insérée dans une structure de données HashMap est:

O (1 + n / k)

Où n est le nombre de seaux et k est le nombre de clés. Par exemple, n peut-être 10, et k peut-être 5. Dans cette situation particulière, certains seaux sont vides (n'ont aucune valeur). Ainsi, le nombre d'opérations serait, 1 + 10/5 = 1 + 2 = 3. C'est-à-dire qu'il y aurait 3 opérations de codage pour insérer un élément de paire de clé / valeur (compte tenu de la clé). Compte tenu d'une nouvelle clé et d'une nouvelle valeur, la complexité de temps la pire des cas pour avoir la clé et sa valeur correspondante insérée dans une structure de données HashMap est:

Sur)

Où n est le nombre de seaux pour n opérations, si le hashmap prend plus d'une valeur par seau pour plus d'une clé, alors tout temps supplémentaire pour insérer une autre valeur dans le même seau est négligeable et négligé.

Effacement

Étant donné une clé déjà dans la structure des données HashMap, la suppression supprime l'élément de paire de clé / valeur. La complexité du temps de cas moyen pour la suppression est:

O (1 + n / k)

Où n est le nombre de seaux et k est le nombre de clés. Par exemple, n peut-être 10, et k peut-être 5. Dans cette situation particulière, certains seaux sont vides (n'ont aucune valeur). Ainsi, le nombre d'opérations pour le code de suppression serait, 1 + 10/5 = 1 + 2 = 3. Ici, il y aurait 3 opérations de codage pour supprimer un élément de paire de clé / valeur, étant donné la clé.

La complexité du temps le plus des cas pour la suppression, étant donné une clé, est:

Sur)

Où n est le nombre de seaux, donc, s'il y a n godets pour la structure de données HashMap, à la limite, il faudrait 10 opérations pour supprimer un élément de paire de clés / valeur dans le hashmap.

Recherche

La recherche signifie trouver l'élément de paire de clé / valeur qui a la clé donnée, qui devrait déjà être dans le hashmap. La complexité du temps de cas moyen pour cela est:

O (1 + n / k)

Avec les arguments ayant les mêmes significations que ci-dessus. La complexité du temps le plus du cas est:

Sur)

Avec l'argument ayant la même signification que ci-dessus.

C ++ 20

C ++ 20 a-t-il une classe de hashmap? - Eh bien, oui, mais pas avec le nom, hashmap. C ++ 20 a quatre conteneurs associatifs non ordonnés, qui sont différentes formes de classes de hashmap. Les conteneurs sont: non ordonné_map, non ordonné_multimap, non ordonné_set et non ordonné_multiset. Ces conteneurs associatifs se trouvent dans la bibliothèque standard C ++ 20. Le conteneur associatif à considérer dans cet article n'est pas ordonné_map. Le non ordonné_map utilise une fonction de hachage par défaut fournie par la bibliothèque standard C ++.

Pour inclure l'en-tête non ordonné_map dans un programme, utilisez la directive,

#inclure

N'utilisez pas #include, qui inclura le ordonnance_map. C ++ ne prend pas #include . L'en-tête non ordonné_map apporte la classe non ordonnée_map dans le programme C ++.

Insérer avec c++

Le segment de code suivant dans la fonction principale C ++ inséra un élément de paire de clé / valeur (nom et numéro de téléphone) dans l'objet non ordonné_map, UMP:

#inclure
non ordonné_map UMP;
arbitre.insert ("John Rambo", "555-5555");

Supprimer avec C++

La syntaxe pour supprimer un élément de paire clé / valeur d'un objet non ordonné_map, étant donné la clé, k, est:

un.Effacer (k)

Où «a» est l'objet non ordonné_map (comme UMP ci-dessus), et effacer () est la fonction membre non ordonnée_map.

Recherche

La syntaxe pour rechercher un élément de paire clé / valeur dans un objet non ordonné_map, étant donné la clé k, qui devrait déjà être dans le non ordonné_map, est:

b.trouver (k)

Où b est l'objet non ordonné_map (comme UMP ci-dessus), et find () est la fonction membre non ordonnée_map.

Conclusion

La complexité du temps signifie un temps d'exécution relatif pour un code. Bien que la complexité du temps pour créer un hashmap puisse être déterminée, lorsqu'il s'agit du hashmap, la complexité du temps est pour insérer, supprimer et rechercher des tâches. Les complexités de temps de cas moyen et pire pour un insert de hashmap bien défini sont:

O (1 + n / k)
Sur)

Les complexités de temps de cas moyen et pire pour une suppression de hashmap bien définie sont:

O (1 + n / k)
Sur)

Les complexités de temps de cas moyen et pire pour une recherche de hashmap bien définie sont:

O (1 + n / k)
Sur)