Función Hash genérica para todos los contenedores STL

Question

Estoy usando un std::unordered_map<key,value> en mi implementación. Usaré cualquiera de los contenedores STL como la clave. Me preguntaba si es posible crear una función hash genérica para cualquier contenedor que se utilice.

This pregunta en SO ofrece la función de impresión genérica para todos los contenedores STL. Si bien puede tener eso, ¿por qué no puede tener algo así como una función Hash que define todo? Y sí, una gran preocupación también es que necesita ser rápido y eficiente.

Estaba considerando hacer una función de hash simple que convierte los valores de la clave a size_t y hacer una función simple como this.

¿Se puede hacer esto?

PD: No utilice las bibliotecas boost. Gracias.

Answer 1

Podemos obtener una respuesta imitando Boost y combinando hashes.

Advertencia: hashes combinación, es decir, calculando un hash de mucho de muchos hashes de las cosas, no es una buena idea general, ya que la función hash resultante no es "bueno" en el sentido estadístico. Se debe construir un hash apropiado de muchas cosas a partir de todos los datos en bruto de todos los constituyentes, no de hashes intermedios. Pero actualmente no hay una buena forma estándar de hacer esto.

De todos modos:

En primer lugar, tenemos que la función hash_combine. Por razones ajenas a mi entender no se ha incluido en la biblioteca estándar, pero es la pieza central para todo lo demás:

template <class T> 
inline void hash_combine(std::size_t & seed, const T & v) 
{ 
    std::hash<T> hasher; 
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 
} 

Usando esto, podemos desmenuzar todo lo que ha hecho a partir de elementos hashable, de dos en dos y tuplas particulares (ejercicio para el lector).

Sin embargo, también podemos usar esto para comprimir contenedores mediante el hash de sus elementos. Esto es precisamente lo que hace el "rango hash" de Boost, pero es sencillo hacerlo tú mismo usando la función de combinación.

Una vez que haya terminado de escribir su hasher rango, simplemente especializarse std::hash y ya está bueno para ir:

namespace std 
{ 
    template <typename T, class Comp, class Alloc> 
    struct hash<std::set<T, Comp, Alloc>> 
    { 
    inline std::size_t operator()(const std::set<T, Comp, Alloc> & s) const 
    { 
     return my_range_hash(s.begin(), s.end()); 
    } 
    }; 

    /* ... ditto for other containers */ 
} 

Si desea imitar la impresora bastante, incluso se podría hacer algo más extremo y especializado std::hash para todos los contenedores, pero probablemente sería más cuidadoso con eso y crea un objeto hash explícita para contenedores:

template <typename C> struct ContainerHasher 
{ 
    typedef typename C::value_type value_type; 
    inline size_t operator()(const C & c) const 
    { 
    size_t seed = 0; 
    for (typename C::const_iterator it = c.begin(), end = c.end(); it != end; ++it) 
    { 
     hash_combine<value_type>(seed, *it); 
    } 
    return seed; 
    } 
}; 

Uso:

std::unordered_map<std::set<int>, std::string, ContainerHasher<std::set<int>>> x;