example - unordered_map c++

¿Cuál es la función hash predeterminada utilizada en C++ std:: unordered_map?

Question

estoy usando

unordered_map<string, int>

y

unordered_map<int, int>

¿Qué función hash se usa en cada caso y cuál es la probabilidad de colisión en cada caso? Estaré insertando cadenas únicas e int únicas como claves en cada caso, respectivamente.

Estoy interesado en conocer el algoritmo de la función hash en el caso de las teclas de cadena e int y sus estadísticas de colisión.

Answer 1

Aunque los algoritmos hashing son dependientes del compilador, lo presentaré para GCC C ++ 11. @Avidan Borisov descubrió astutamente que el algoritmo de hash de GCC utilizado para cadenas es "MurmurHashUnaligned2", de Austin Appleby. Hice algunas búsquedas y encontré una copia duplicada de GCC en Github. Por lo tanto:

Las funciones de hash GCC C ++ 11 utilizadas para unordered_map (una plantilla de tabla hash) y unordered_set (una plantilla de conjunto de hash) parecen ser las siguientes.

• Gracias a Avidan Borisov por su investigación de antecedentes, que sobre la cuestión de cuáles son las funciones de hash GCC C ++ 11 utilizadas , afirmando que GCC usa una implementación de "MurmurHashUnaligned2", de Austin Appleby ( http://murmurhash.googlepages.com/ )
• En el archivo "gcc / libstdc ++ - v3 / libsupc ++ / hash_bytes.cc", aquí ( https://github.com/gcc-mirror/gcc/blob/master/libstdc++-v3/libsupc++/hash_bytes.cc ), encontré las implementaciones. Aquí está el del valor de retorno "32 bit size_t", por ejemplo (retirado el 11 de agosto de 2017)

Código:

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

Para funciones hashing adicionales, incluyendo djb2 , y las 2 versiones de las funciones hashing de K & R (una aparentemente terrible, una bastante buena), vea mi otra respuesta aquí: https://.com/a/45641002/4561887 .

Answer 2

Se usa el objeto de función std::hash<> .

Existen especializaciones estándar para todos los tipos incorporados, y algunos otros tipos de biblioteca estándar como std::string y std::thread . Ver el enlace para la lista completa.

Para que se usen otros tipos en std::unordered_map , deberá especializar std::hash<> o crear su propio objeto de función.

La posibilidad de colisión depende completamente de la implementación, pero considerando el hecho de que los enteros están limitados entre un rango definido, mientras que las cadenas son teóricamente infinitamente largas, diría que hay muchas más posibilidades de colisión con cadenas.

En cuanto a la implementación en GCC, la especialización para tipos incorporados simplemente devuelve el patrón de bits. Así es como se definen en 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 especialización para std::string se define como:

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

Algunas búsquedas adicionales nos llevan a:

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 es una función externa de libstdc++ . Un poco más de búsqueda me llevó a este archivo , que dice:

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

Por lo tanto, el algoritmo hash predeterminado que utiliza GCC para cadenas es MurmurHashUnaligned2.