J'essaie de comprendre une bonne fonction de hachage pour une STD :: Paire de deux types primitifs. C'est la façon dont je l'ai implémenté maintenant: Il semble fonctionner même si j'ai deux paires telles que (1, 2) et (2, 1) (nombre renversé). Ils génèrent la même valeur de hachage, mais les valeurs sont toujours insérées avec succès dans la carte de hachage. Toute pensée?
5 Réponses :
En supposant que STDext :: hash_value fournit une bonne distribution de valeurs de hachage pour chacun des premier et seconde, ce que vous avez fait va bien si vous ne vous attendez pas à une incidence de manière disproportionnée de paires d'images miroir (par exemple (1,2 ) et (2,1)). Si votre jeu de données est tel que vous EM> s'attend à ce que vous attendez beaucoup de ceux-ci, vous pourriez envisager de modifier la fonction de hachage de les forcer à être différente. Par exemple, inversez la première valeur de hachage:
return ~stdext::hash_value<T>(rhs.first) ^ stdext::hash_value<T>(rhs.second);
Mauvaise fonction de hash. ~ a ^ a est identique (valeur binaire de tous) pour toutes les valeurs de A.
Oui, mais c'est ~ a ^ b .
Cela dit, je suis d'accord hash_commine est une meilleure approche générale.
@Mike: ainsi que la "paires d'images miroir" que vous adresse, comme Michael dit qu'il est important d'assurer h (a, a)! = H (b, b) donné différent a < / code> et b
En règle générale, les conteneurs de hachage doivent toujours gérer ce cas (collisions de hachage). Il y a quelques méthodes qu'ils peuvent utiliser comme en tant que chaînage et sondage, qui ne feront pas potentiellement mal performances.
à la place, je suggérerais d'utiliser boost :: hash_combine pour combiner les hachages de manière à échanger premier et second ne générer le même hachage.
Pour plus de détails sur boost :: hash_commine : boost.org/doc/libs/1_53_0/doc/html/hash/...
Comme d'autres personnes ont noté, les fonctions de hachage n'affectent que l'efficacité des tables de hachage et non de l'exactitude. Votre fonction n'est que mal si les paires d'images miroir sont fréquentes. Comme dans certaines applications, cela pourrait être un problème, il serait raisonnable d'échanger des demi-mots supérieurs et inférieurs d'une valeur de hachage, puis de XOR. De nombreux autres régimes sont possibles, mais celui-ci est très rapide et simple.
template<typename T, typename U>
std::size_t operator()(const std::pair<T,U> &rhs) const
{
const int h = sizeof(size_t) * 8 / 2;
size_t a = stdext::hash_value<T>(rhs.first);
return ((a << h) | (a >> h)) ^ stdext::hash_value<U>(rhs.second);
}
Voici une implémentation de Vous l'utiliseriez comme ceci: < PRE> XXX Je ne peux pas réellement garantir la logique derrière cette fonction, mais elle a l'air plus solide que la plupart des options mentionnées ici. hash_commine en fonction des documents de la version actuelle de Boost:
( http: //www.boost. org / doc / libs / 1_53_0 / doc / html / hash / référence.html # boost.hash_commine )
Juste pour le plaisir de cela, voici une autre approche qui est simple et adresse directement aux cas problématiques, notamment:
premier code> et secondes code> sont identiques, il renvoie sa valeur de hachage commune li>
- Sinon, il Xors les valeurs mais:
- empêcher H (A, B) en collision avec H (B, A), il utilise un
ul> li>
ul>
Mise en œuvre: P>
1 template<typename T, typename U>
2 std::size_t operator()(const std::pair<T,U> &rhs) const
3 {
4 std::size_t a = stdext::hash_value<T>(rhs.first);
5 return rhs.first == rhs.second ? a :
6 a ^ (rhs.first < rhs.second ? stdext::hash_value<U>(rhs.second)
7 : stdext::hash_value<U>(~rhs.second));
8 }
La génération du même hachage de deux entrées différentes est une occurrence attendue, et toute table de hachage correctement implémentée le gérera correctement. Mais cela pourrait avoir un impact sur la vitesse de la recherche.
Vous pouvez utiliser
boost :: hach_comminepour combiner les 2 hachages (ou jeter un coup d'œil à la source si vous n'êtes pas autorisé à utiliser Boost)Vous pouvez essayer d'inverser les bits du deuxième hachage.
Un autre problème avec XOR est que si les valeurs de la paire sont égales, le XOR des hachages sera toujours zéro.