Quelle est la fonction de hachage par défaut utilisée dans C++ std::unordered map?

j'utilise 

unordered_map<string, int>

et 

unordered_map<int, int>

quelle fonction de hachage est utilisée dans chaque cas et quel est le risque de collision dans chaque cas? Je vais insérer une chaîne unique et unique int comme clés dans chaque cas respectivement.

je suis intéressé de connaître l'algorithme de la fonction de hachage dans le cas des touches string et int et leurs statistiques de collision.

44
demandé sur Avidan Borisov 2013-10-16 23:09:06

2 réponses

l'objet de fonction std::hash<> est utilisé.

il existe des spécialisations Standard pour tous les types de bibliothèques intégrées et certains autres types de bibliothèques standard. std::string et std::thread. Voir le lien pour la liste complète.

pour les autres types à utiliser dans un std::unordered_map, vous devrez vous spécialiser std::hash<> ou créer votre propre objet de fonction.

le risque de collision dépend entièrement de l'implémentation, mais en considérant le fait que les entiers sont limités entre une portée définie, tandis que les cordes sont théoriquement infiniment longues, je dirais qu'il y a une bien meilleure chance de collision avec les cordes.

en ce qui concerne L'implémentation dans GCC, la spécialisation pour les types de construction renvoie simplement le patron de bits. Voici comment ils sont définis dans bits/functional_hash.h:

  /// Partial specializations for pointer types.
  template<typename _Tp>
    struct hash<_Tp*> : public __hash_base<size_t, _Tp*>
    {
      size_t
      operator()(_Tp* __p) const noexcept
      { return reinterpret_cast<size_t>(__p); }
    };

  // Explicit specializations for integer types.
#define _Cxx_hashtable_define_trivial_hash(_Tp)     \
  template<>                        \
    struct hash<_Tp> : public __hash_base<size_t, _Tp>  \
    {                                                   \
      size_t                                            \
      operator()(_Tp __val) const noexcept              \
      { return static_cast<size_t>(__val); }            \
    };

  /// Explicit specialization for bool.
  _Cxx_hashtable_define_trivial_hash(bool)

  /// Explicit specialization for char.
  _Cxx_hashtable_define_trivial_hash(char)

  /// ...

La spécialisation pour std::string est défini comme suit:

#ifndef _GLIBCXX_COMPATIBILITY_CXX0X
  /// std::hash specialization for string.
  template<>
    struct hash<string>
    : public __hash_base<size_t, string>
    {
      size_t
      operator()(const string& __s) const noexcept
      { return std::_Hash_impl::hash(__s.data(), __s.length()); }
    };

D'autres recherches nous mènent à:

struct _Hash_impl
{
  static size_t
  hash(const void* __ptr, size_t __clength,
       size_t __seed = static_cast<size_t>(0xc70f6907UL))
  { return _Hash_bytes(__ptr, __clength, __seed); }
  ...
};
...
// Hash function implementation for the nontrivial specialization.
// All of them are based on a primitive that hashes a pointer to a
// byte array. The actual hash algorithm is not guaranteed to stay
// the same from release to release -- it may be updated or tuned to
// improve hash quality or speed.
size_t
_Hash_bytes(const void* __ptr, size_t __len, size_t __seed);

_Hash_bytes est une fonction externe de libstdc++. Un peu plus de recherche m'a conduit à ce fichier, qui stipule:

// This file defines Hash_bytes, a primitive used for defining hash
// functions. Based on public domain MurmurHashUnaligned2, by Austin
// Appleby.  http://murmurhash.googlepages.com/

donc L'algorithme de hachage utilisé par défaut par GCC pour les chaînes est MurmurHashUnaligned2.

88
répondu Avidan Borisov 2013-11-04 17:37:44

bien que les algorithmes de hachage soient dépendants du compilateur, je vais le présenter pour GCC c++11. @Avidan Borisov découvert astucieusement que L'algorithme de hachage GCC utilisé pour les chaînes est "MurmurHashUnaligned2", par Austin Appleby. J'ai cherché et j'ai trouvé une copie de GCC sur Github. Donc:

les fonctions de hachage GCC c++11 utilisées pour unordered_map (un modèle de table de hachage) et unordered_set (un modèle de jeu de hachures) semble être comme suit.

Code:

// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
{
  const size_t m = 0x5bd1e995;
  size_t hash = seed ^ len;
  const char* buf = static_cast<const char*>(ptr);

  // Mix 4 bytes at a time into the hash.
  while (len >= 4)
  {
    size_t k = unaligned_load(buf);
    k *= m;
    k ^= k >> 24;
    k *= m;
    hash *= m;
    hash ^= k;
    buf += 4;
    len -= 4;
  }

  // Handle the last few bytes of the input array.
  switch (len)
  {
    case 3:
      hash ^= static_cast<unsigned char>(buf[2]) << 16;
      [[gnu::fallthrough]];
    case 2:
      hash ^= static_cast<unsigned char>(buf[1]) << 8;
      [[gnu::fallthrough]];
    case 1:
      hash ^= static_cast<unsigned char>(buf[0]);
      hash *= m;
  };

  // Do a few final mixes of the hash.
  hash ^= hash >> 13;
  hash *= m;
  hash ^= hash >> 15;
  return hash;
}

pour les fonctions de hachage supplémentaires, y compris djb2, et les 2 versions des fonctions de hachage K&R (apparemment terrible, une assez bonne), voir mon autre réponse ici: https://stackoverflow.com/a/45641002/4561887.

2
répondu Gabriel Staples 2017-08-11 18:48:29