Was ist die Standard-Hash-Funktion in C ++ std :: unordered_map?

Ich bin mit

unordered_map<string, int>

und

unordered_map<int, int>

Welche hash-Funktion verwendet wird, in jedem Fall und was ist die chance einer Kollision in jedem Fall?
Ich werde einfügen eindeutige Zeichenfolge und einzigartigen int als Schlüssel in jedem Fall jeweils.

Ich bin daran interessiert zu wissen, den Algorithmus der hash-Funktion im Fall von string-und int-Schlüssel und Ihre Kollision stats.

Kommentar zu dem Problem
Ich denke, es ist bis zum standard. Nicht sicher, was für eine unorderd_map ist. Kommentarautor: Joel
unordered_map ist wie die hash-Tabelle...Hab Standard-hash-Funktionen ändern in C++98 vs C++11? Kommentarautor: Medicine
Sie hat dieses C++11, aber die Frage über TR1. Welche ist es? Kommentarautor: John Dibling
Sorry @John Dibling, ich tagged it C++11. Ich habe bearbeitet den Titel zu, da ich denke, die Frage hat mehr Bedeutung, Art und Weise; jetzt Antworten verweisen auf einen formellen standard. Fühlen Sie sich frei, um wieder zu ändern; ich sehe, Sie haben mehr Erfahrung auf dieser Website, als ich. Kommentarautor: Bathsheba
Warum dann beziehen Sie sich auf die tr1 namespace? Kommentarautor: John Dibling

InformationsquelleAutor der Frage Medicine | 2013-10-16

  1. 85

    Die Funktion Objekt std::hash<> verwendet wird.

    Standard-Spezialisierungen existieren für alle built-in Typen, und einige andere standard-Bibliothek-Typen
    wie std::string und std::thread. Siehe den link für die vollständige Liste.

    Für andere Arten verwendet werden, die in einem std::unordered_map Sie haben sich zu spezialisieren std::hash<> oder erstellen Sie Ihre eigene function-Objekt.

    Die chance für eine Kollision ist vollständig von der Implementierung abhängig, aber in Anbetracht der Tatsache, dass Ganzzahlen beschränkt sind zwischen einem definierten Bereich, während die Streicher sind theoretisch unendlich lange, ich würde sagen, es ist eine viel bessere chance für eine Kollision mit strings.

    Als für die Implementierung in GCC, die Spezialisierung für builtin-Typen nur gibt das bit-Muster. Hier ist, wie Sie definiert sind, in 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)

  ///...

    Die Spezialisierung für std::string ist definiert als:

    #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()); }
    };

    Einige weitere Suche führt uns zu:

    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 ist eine externe Funktion aus libstdc++. Ein bisschen mehr Suche führte mich zu diese Datei, in dem es heißt:

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

    Also die Standard-hashing-Algorithmus, der GCC verwendet für strings ist MurmurHashUnaligned2.

    InformationsquelleAutor der Antwort Avidan Borisov

  2. 2

    Obwohl die hashing-algorithmen, compiler-abhängig, ich werde es für GCC-C++11. @Avidan Borisov scharfsinnig entdeckt , dass die GCC-Hash-Algorithmus für strings verwendet wird "MurmurHashUnaligned2," von Austin Appleby. Ich habe einige suchen und fand eine gespiegelte Kopie von GCC auf Github. Daher:

    Die GCC-C++11 Hash-Funktionen verwendet, für unordered_map (eine hash-Tabelle-Vorlage) und unordered_set (hash-set-Vorlage) zu sein scheinen wie folgt.

    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;
}

    Für zusätzliche Hash-Funktionen, einschließlich djb2, und die 2 Versionen des K&R Hash-Funktionen (offensichtlich schrecklich, aber ziemlich gut), siehe meine andere Antwort hier: https://stackoverflow.com/a/45641002/4561887.

    InformationsquelleAutor der Antwort Gabriel Staples

Schreibe einen Kommentar