Cómo crear un buen hash_combine con salida de 64 bits (inspirado por boost :: hash_combine)

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

Magic number in boost::hash_combine

me gustaría explorar sobre 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 la elección de 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

Lea 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ó utilizando http://code.google.com/p/smhasher/, y probablemente pueda probar su 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 pensar que el boost hash_combine() de 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 como esto (asumiendo size_t es un entero sin signo de 64 bits, añada su parte favorita del preprocesador o el engaño plantilla para validar que):

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 reproducir este fragmento aquí y en otros lugares está bien, ya que no constituye una 'parte sustancial' del código CityHash, pero consulte el acuerdo de licencia de las fuentes CityHash & para decidir por sí mismo)