c++ - hashing - Cómo crear un buen hash_combine con salida de 64 bits(inspirado en boost:: hash_combine)

set string c++

Question

Actualmente, Boost tiene la función hash_combine que genera un entero sin signo de 32 bits (para ser precisos, size_t). Algunas referencias:

http://www.boost.org/doc/libs/1_43_0/doc/html/hash/reference.html#boost.hash_combine

http://www.boost.org/doc/libs/1_43_0/doc/html/hash/combine.html

Número mágico en impulso :: hash_combine

Me gustaría explorar cómo crear la versión de 64 bits de hash_combine.

Lo primero es obtener la proporción áurea o cualquier otro número irracional en 64 bits.

La segunda parte es usar turnos. Esta parte es bastante complicada y me gustaría preguntar si hay mejores prácticas o una guía sobre el uso de turnos para obtener valores hash. O eligiendo turnos como el código original:

seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 

es totalmente aleatorio?

¿También cómo evaluar la salida de hash_combine para asegurarse de que no cree más colisiones que la función hash original hash_value ?

Answer 1

Lee http://burtleburtle.net/bob/hash/doobs.html para obtener información básica sobre el diseño de la función hash y el resto de los artículos en http://burtleburtle.net/bob/hash/ para obtener información más detallada. CityHash se probó usando http://code.google.com/p/smhasher/ , y probablemente puedas probar tu hash_combine usando la misma suite de pruebas.

Aunque no soy un experto en hash, los diseños de funciones hash recientes me llevan a creer que el hash_combine() boost de técnica de 2 turnos ya no es avanzado y puede mejorarse.

Answer 2

Si solo quiere un hash_combine que hashes 2 valores de 64 bits en uno, y no necesita una nueva función hash para cadenas, puede simplemente extraer un pequeño código de CityHash, algo así (suponiendo que size_t es un bit de 64 bits) entero sin signo, agregue su bit favorito de preprocesador o trucos de plantilla para validar eso):

template <class T> inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    const std::size_t kMul = 0x9ddfea08eb382d69ULL;
    std::size_t a = (hasher(v) ^ seed) * kMul;
    a ^= (a >> 47);
    std::size_t b = (seed ^ a) * kMul;
    b ^= (b >> 47);
    seed = b * kMul;
}

(Creo que reproducir este fragmento aquí y en cualquier otro lugar está bien porque no constituye una "parte sustancial" del código de CityHash, pero verifique el acuerdo de licencias y fuentes de CityHash para decidir por usted mismo)