Quelle est la meilleure façon d'utiliser un HashMap en C++ ?

Question

Je sais que STL dispose d'une API HashMap, mais je n'ai trouvé aucune documentation complète avec de bons exemples à ce sujet.

Tout bon exemple sera apprécié.

Answer 1

La bibliothèque standard comprend les cartes ordonnées et non ordonnées ( std::map y std::unordered_map ). Dans une carte ordonnée ( std::map ), les éléments sont triés par clé, l'insertion et l'accès se font en O(log n) . En général, la bibliothèque standard utilise en interne arbres rouges et noirs pour les cartes ordonnées. Mais ce n'est qu'un détail de mise en œuvre. Dans une carte non ordonnée ( std::unordered_map ) et l'accès se fait en O(1). Il s'agit simplement d'un autre nom pour une table de hachage.

Un exemple avec (ordonné) std::map :

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

Sortie :

23
Key: hello Value: 23

Si vous avez besoin d'un ordre dans votre conteneur et que le temps d'exécution O(log n) ne vous pose pas de problème, utilisez simplement std::map .

Sinon, si vous avez vraiment besoin d'une table de hachage (O(1) insertion/accès), consultez std::unordered_map qui est similaire à std::map (par exemple, dans l'exemple ci-dessus, il suffit de rechercher et de remplacer map avec unordered_map ).

En unordered_map a été introduit avec le Norme C++11 révision. Ainsi, en fonction de votre compilateur, vous devez activer les fonctionnalités de C++11 (par exemple, lorsque vous utilisez GCC 4.8, vous devez ajouter -std=c++11 aux CXXFLAGS).

Même avant la sortie de C++11, GCC prenait en charge unordered_map - dans l'espace de noms std::tr1 . Ainsi, pour les anciens compilateurs GCC, vous pouvez essayer de l'utiliser comme suit :

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

Il fait également partie de boost, c'est-à-dire que vous pouvez utiliser la fonction correspondante de en-tête d'impulsion pour une meilleure portabilité.

Answer 2

A hash_map est une version plus ancienne et non normalisée de ce que l'on appelle, à des fins de normalisation, un unordered_map (à l'origine dans TR1, et inclus dans la norme depuis C++11). Comme son nom l'indique, il est différent de std::map principalement parce qu'il n'est pas ordonné - si, par exemple, vous itérez à travers une carte de begin() a end() vous obtenez les éléments dans l'ordre de la clé 1 mais si vous itérez à travers un unordered_map de begin() a end() Vous obtenez des éléments dans un ordre plus ou moins arbitraire.

Un unordered_map est normalement censé avoir une complexité constante. En d'autres termes, une insertion, une consultation, etc., prend généralement un temps fixe, quel que soit le nombre d'éléments contenus dans la table. Un std::map a une complexité logarithmique sur le nombre d'éléments stockés - ce qui signifie que le temps d'insertion ou de récupération d'un élément augmente, mais de façon relativement lente. lentement au fur et à mesure que la carte s'agrandit. Par exemple, s'il faut 1 microseconde pour consulter l'un des 1 millions d'éléments, on peut s'attendre à ce qu'il faille environ 2 microsecondes pour consulter l'un des 2 millions d'éléments, 3 microsecondes pour l'un des 4 millions d'éléments, 4 microsecondes pour l'un des 8 millions d'éléments, etc.

D'un point de vue pratique, ce n'est pas tout à fait ça. Par nature, une table de hachage simple a une taille fixe. L'adapter aux exigences de taille variable d'un conteneur à usage général n'est pas chose aisée. Par conséquent, les opérations qui augmentent (potentiellement) la taille de la table (par exemple, l'insertion) sont potentiellement relativement lentes (c'est-à-dire que la plupart d'entre elles sont assez rapides, mais périodiquement, l'une d'entre elles sera beaucoup plus lente). Les consultations, qui ne peuvent pas modifier la taille de la table, sont généralement beaucoup plus rapides. Par conséquent, la plupart des tables basées sur le hachage tendent à être optimales lorsque vous effectuez beaucoup de consultations par rapport au nombre d'insertions. Dans les situations où vous insérez beaucoup de données, puis parcourez la table une fois pour récupérer les résultats (par exemple, en comptant le nombre de mots uniques dans un fichier), il y a de fortes chances qu'une table à base de hachage soit utilisée. std::map sera tout aussi rapide, voire plus rapide encore (mais, là encore, la complexité de calcul est différente, ce qui peut également dépendre du nombre de mots uniques dans le fichier).

---

1 L'ordre est défini par le troisième paramètre du modèle lors de la création de la carte, std::less<T> par défaut.

Answer 3

Voici un exemple plus complet et plus souple qui n'omet pas les includes nécessaires pour générer des erreurs de compilation :

#include <iostream>
#include <unordered_map>

class Hashtable {
    std::unordered_map<const void *, const void *> htmap;

public:
    void put(const void *key, const void *value) {
            htmap[key] = value;
    }

    const void *get(const void *key) {
            return htmap[key];
    }

};

int main() {
    Hashtable ht;
    ht.put("Bob", "Dylan");
    int one = 1;
    ht.put("one", &one);
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one");
}

Ce n'est toujours pas très utile pour les clés, à moins qu'elles ne soient prédéfinies comme des pointeurs, parce qu'une valeur correspondante ne suffira pas ! (Toutefois, comme j'utilise normalement des chaînes pour les clés, le fait de remplacer "const void *" par "string" dans la déclaration de la clé devrait résoudre ce problème).

Answer 4

Preuve que std::unordered_map utilise une carte de hachage dans GCC stdlibc++ 6.4

Ceci a été mentionné à : https://stackoverflow.com/a/3578247/895245 mais dans la réponse suivante : Quelle structure de données se trouve à l'intérieur de std::map en C++ ? J'en ai donné d'autres preuves pour l'implémentation de GCC stdlibc++ 6.4 par :

• Débogage par étapes GDB dans la classe
• analyse des caractéristiques de performance

Voici un aperçu du graphique des caractéristiques de performance décrit dans cette réponse :

Comment utiliser une classe personnalisée et une fonction de hachage avec unordered_map

Cette réponse est parfaite : Carte non ordonnée C++ utilisant un type de classe personnalisé comme clé

Extrait : égalité :

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Fonction de hachage :

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}

Answer 5

Pour ceux d'entre nous qui essaient de comprendre comment hacher leurs propres classes tout en continuant à utiliser le modèle standard, il existe une solution simple :

1. Dans votre classe, vous devez définir une surcharge de l'opérateur d'égalité == . Si vous ne savez pas comment faire, GeeksforGeeks propose un excellent tutoriel. https://www.geeksforgeeks.org/operator-overloading-c/

2. Sous l'espace de noms standard, déclarez une structure template appelée hash avec votre nom de classe comme type (voir ci-dessous). J'ai trouvé un excellent article de blog qui montre également un exemple de calcul de hachages à l'aide de XOR et de bitshifting, mais cela sort du cadre de cette question, mais il contient également des instructions détaillées sur la manière d'utiliser les fonctions de hachage https://prateekvjoshi.com/2014/06/05/using-hash-function-in-c-for-user-defined-classes/

   namespace std {

   template<> struct hash<my_type> { size_t operator()(const my_type& k) { // Do your hash function here ... } };

   }

3. Ainsi, pour mettre en œuvre une table de hachage à l'aide de votre nouvelle fonction de hachage, il vous suffit de créer un fichier std::map o std::unordered_map comme vous le feriez normalement et utilisez my_type comme clé, la bibliothèque standard utilisera automatiquement la fonction de hachage que vous avez définie précédemment (à l'étape 2) pour hacher vos clés.

   include <unordered_map>

   int main() { std::unordered_map<my_type, other_type> my_map; }