Quel est le meilleur algorithme pour surcharger GetHashCode ?
J’utilise habituellement quelque chose de similaire à l’implémentation donnée dans le fabuleux Effective Java de Josh Bloch. C’est rapide et produit un hash assez bon qui a peu de chances de provoquer des collisions. Choisissez deux nombres premiers différents, par exemple 17 et 23, et faites :
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = 17;
// Suitable nullity checks etc, of course :)
hash = hash * 23 + field1.GetHashCode();
hash = hash * 23 + field2.GetHashCode();
hash = hash * 23 + field3.GetHashCode();
return hash;
}
}
Comme noté dans les commentaires, vous pourriez trouver qu’il est préférable de multiplier par un grand nombre premier à la place. Apparemment 486187739 est un bon choix… et bien que la plupart des exemples que j’ai vus avec de petits nombres tendent à utiliser des nombres premiers, il existe au moins des algorithmes similaires où des nombres non premiers sont souvent utilisés. Dans l’exemple presque-FNV plus loin, par exemple, j’ai utilisé des nombres qui apparemment fonctionnent bien – mais la valeur initiale n’est pas un nombre premier. (La constante de multiplication est un nombre premier cependant. Je ne sais pas exactement à quel point c’est important.)
C’est mieux que la pratique courante de faire un XOR des codes de hachage pour deux raisons principales. Supposons que nous ayons un type avec deux champs int :
XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y
D’ailleurs, l’algorithme précédent est celui actuellement utilisé par le compilateur C# pour les types anonymes.
Cette page donne pas mal d’options. Je pense que pour la plupart des cas, l’algorithme ci-dessus est « suffisamment bon » et qu’il est incroyablement facile à retenir et à implémenter correctement. L’alternative FNV est tout aussi simple, mais utilise des constantes différentes et XOR au lieu de ADD comme opération de combinaison. Cela ressemble quelque chose comme
(Réponse tronquée)