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

Estoy usando 

unordered_map<string, int>

Y 

unordered_map<int, int>

¿Qué función hash se utiliza en cada caso y cuál es la probabilidad de colisión en cada caso? Insertaré una cadena única e int única como claves en cada caso respectivamente.

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

Author: Avidan Borisov, 2013-10-16
Source

2 answers

El objeto de funciónstd::hash<> se utiliza.

Existen especializaciones estándar para todos los tipos integrados, y algunos otros tipos de bibliotecas estándar tales como std::string y std::thread. Vea el enlace para la lista completa.

Para usar otros tipos en un std::unordered_map, tendrá que especializarse std::hash<> o crear su propio objeto de función.

La posibilidad de colisión depende completamente de la implementación, pero teniendo en cuenta el hecho de que los enteros están limitados entre un rango definido, mientras que las cuerdas son teóricamente infinitamente largas, yo diría que hay una posibilidad mucho mejor de colisión con cuerdas.

En cuanto a la implementación en GCC, la especialización para builtin-types solo 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 más nos llevan a: {[16]]} 

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 esto archivo, que establece: 

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

Así que el algoritmo de hash predeterminado que usa GCC para las cadenas es MurmurHashUnaligned2.

 88
Author: Avidan Borisov,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-11-04 17:37:44

Aunque los algoritmos hash dependen 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 reflejada de GCC en Github. Por lo tanto:

Las funciones de hash de GCC C++11 utilizadas para unordered_map (una plantilla de tabla hash) yunordered_set (una plantilla de conjunto de hash) parecen ser como seguir.

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 hash adicionales, incluyendo djb2, y las 2 versiones de las funciones hash de K&R (una aparentemente terrible, una bastante buena), vea mi otra respuesta aquí: https://stackoverflow.com/a/45641002/4561887 .

 2
Author: Gabriel Staples,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-08-11 18:48:29