Comment créer une bonne hash_combine avec une sortie 64 bits (inspiré de boost :: hash_combine)

Actuellement, Boost a une fonction hash_combine qui génère un entier non signé de 32 bits (pour être précis, size_t). Quelques références:

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

Nombre magique dans le boost :: hash_combine

J’aimerais explorer comment créer une version 64 bits de hash_combine.

La première chose à faire est d’obtenir un nombre d’or ou tout autre nombre irrationnel en 64 bits.

La deuxième partie consiste à utiliser des équipes. Cette partie plutôt délicate et je voudrais demander s’il existe des meilleures pratiques ou un guide sur l’utilisation des changements pour obtenir des valeurs de hachage? Ou en choisissant des changements comme le code d’origine:

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

est totalement aléatoire?

Aussi, comment évaluer la sortie de hash_combine pour s’assurer qu’elle ne crée pas plus de collisions que la fonction de hachage d’origine hash_value ?

Si vous voulez seulement un hash_combine qui hache 2 valeurs 64 bits en une seule et que vous n’ayez pas besoin d’une nouvelle fonction de hachage pour les chaînes, vous pouvez simplement extraire un tout petit peu de code de CityHash, quelque chose comme ceci (en supposant que size_t est un 64 bits). entier non signé, ajoutez votre truc préféré de préprocesseur ou de modèle pour valider cela):

 template  inline void hash_combine(std::size_t& seed, const T& v) { std::hash 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; } 

(Je pense que reproduire cet extrait ici et ailleurs est correct car il ne constitue pas une “partie substantielle” du code CityHash, mais veuillez consulter les sources et le contrat de licence de CityHash pour décider vous-même)

Lisez http://burtleburtle.net/bob/hash/doobs.html pour des informations de base sur la conception de fonctions de hachage, et le rest des articles de http://burtleburtle.net/bob/hash/ pour plus d’informations. CityHash a été testé à l’aide de http://code.google.com/p/smhasher/ . Vous pouvez probablement tester votre hash_combine à l’aide de la même série de tests.

Bien que je ne sois pas un expert en hachage, les conceptions des fonctions de hachage récentes me hash_combine() à penser que les utilisations de hash_combine() technique de renforcement à deux hash_combine() ne sont plus à la pointe de la technologie et peuvent être améliorées.