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



17 modern (3)

Das Funktionsobjekt std::hash<> wird verwendet.

Standardspezialisierungen gibt es für alle integrierten Typen und einige andere Standardbibliothekstypen wie beispielsweise std::string und std::thread . Siehe den Link für die vollständige Liste.

Für andere Typen, die in einer std::unordered_map , müssen Sie std::hash<> oder ein eigenes Funktionsobjekt erstellen.

Die Wahrscheinlichkeit einer Kollision ist vollständig implementierungsabhängig, aber in Anbetracht der Tatsache, dass ganze Zahlen zwischen einem definierten Bereich begrenzt sind, während Strings theoretisch unendlich lang sind, würde ich sagen, dass es eine viel bessere Chance für eine Kollision mit Strings gibt.

Wie bei der Implementierung in GCC gibt die Spezialisierung für Built-In-Typen nur das Bitmuster zurück. So sind sie 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()); }
    };

Eine 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 von libstdc++ . Ein bisschen mehr Suche führte mich zu dieser Datei , die besagt:

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

Der Standard-Hashing-Algorithmus, den GCC für Strings verwendet, ist MurmurHashUnaligned2.

ich benutze

unordered_map<string, int>

und

unordered_map<int, int>

Welche Hash-Funktion wird jeweils verwendet und was ist jeweils Kollisionswahrscheinlichkeit? Ich werde jeweils eine eindeutige Zeichenfolge und ein eindeutiges int als Schlüssel einfügen.

Ich bin daran interessiert zu wissen, den Algorithmus der Hash-Funktion im Falle von String-und int-Schlüssel und ihre Kollisionsstatistik.


Obwohl die Hashalgorithmen compilerabhängig sind, werde ich sie für GCC C ++ 11 vorstellen. @Avidan Borisov entdeckte geschickt, dass der Hash-Algorithmus des GCC, der für Strings verwendet wird, "MurmurHashUnaligned2" von Austin Appleby ist. Ich habe ein wenig gesucht und eine gespiegelte Kopie von GCC auf Github gefunden. Deshalb:

Die GCC C ++ 11 Hashfunktionen, die für unordered_map (eine Hashtabellenvorlage) und unordered_set (eine Hashsetvorlage) verwendet werden, scheinen wie folgt zu sein.

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 der K & R Hash-Funktionen (eine anscheinend schrecklich, eine ziemlich gut), siehe meine andere Antwort hier: https://.com/a/45641002/4561887 .


Sie ändert die Verknüpfung einer Funktion so, dass die Funktion von C aus aufgerufen werden kann. In der Praxis bedeutet das, dass der Funktionsname nicht verändert wird.





c++ c++11 hash stl unordered-map