Comment implémentez-vous GetHashCode pour une structure avec deux chaînes, lorsque les deux chaînes sont interchangeables

https://stackoverflow.com/questions/70303

c#
hashtable

09-06-2019
|

Question

J'ai une structure en C #:

public struct UserInfo
{
   public string str1
   {
     get;
     set;
   }

   public string str2
   {
     get;
     set;
   }   
}

La seule règle est que UserInfo (str1 = "AA", str2 = "BB"). Est égal à (UserInfo (str1 = "BB", str2 = "AA"))

Comment remplacer la fonction GetHashCode pour cette structure?

La solution

MSDN :

Une fonction de hachage doit avoir les propriétés suivantes:

Si deux objets se comparent de manière égale, la méthode GetHashCode de chaque objet doit renvoyer la même valeur. Toutefois, si deux objets ne se comparent pas de manière égale, les méthodes GetHashCode des deux objets ne doivent pas renvoyer de valeurs différentes.

La méthode GetHashCode d'un objet doit systématiquement renvoyer le même code de hachage tant qu'il n'y a pas de modification de l'état de l'objet qui détermine la valeur de retour du est égal à . méthode. Notez que cela n’est vrai que pour l’exécution en cours d’une application et qu’un code de hachage différent peut être renvoyé si l’application est réexécutée.

Pour obtenir les meilleures performances, une fonction de hachage doit générer une distribution aléatoire pour toutes les entrées.

La prise en compte correcte est la suivante:

return str1.GetHashCode() ^ str2.GetHashCode()

^ peut être remplacé par une autre opération commutative

Autres conseils

Voir réponse de Jon Skeet - Les opérations binaires telles que ^ ne sont pas bonnes, elles génèrent souvent des hashs en collision!

public override int GetHashCode()
{
    unchecked
    {
        return (str1 ?? String.Empty).GetHashCode() +
            (str2 ?? String.Empty).GetHashCode();
    }
}

Il peut être préférable d’utiliser l’opérateur "+" plutôt que "^", car bien que vous souhaitiez explicitement ("AA", "BB") et ("BB", "AA") explicitement identiques, vous pouvez veut pas ('AA', 'AA') et ('BB', 'BB') identiques (ou toutes les paires égales d'ailleurs).

La règle "aussi vite que possible" n'est pas entièrement respectée dans cette solution car, dans le cas des valeurs NULL, elle effectue un "GetHashCode ()" sur la chaîne vide au lieu de renvoyer immédiatement une constante connue, mais même sans mesurer explicitement Je suis prêt à supposer que la différence ne serait pas assez grave pour vous inquiéter à moins que vous ne vous attendiez à beaucoup de valeurs nulles.

En règle générale, un moyen simple de générer un code de hachage pour une classe consiste à XOR tous les champs de données pouvant participer à la génération du code de hachage (en prenant soin de vérifier la valeur null comme indiqué par d'autres). Ceci répond également à l'exigence (artificielle?) Selon laquelle les codes de hachage pour UserInfo ("AA", "BB") et UserInfo ("BB", "AA") sont identiques.
Si vous pouvez émettre des hypothèses sur l'utilisation de votre classe, vous pouvez peut-être améliorer votre fonction de hachage. Par exemple, s'il est commun que str1 et str2 soient identiques, XOR peut ne pas être un bon choix. Mais si str1 et str2 représentent, par exemple, le prénom et le nom, XOR est probablement un bon choix.

Bien que ceci ne soit clairement pas un exemple concret, il peut être intéressant de souligner que: - C'est probablement un mauvais exemple d'utilisation d'une structure: une structure devrait normalement avoir une sémantique de valeur, ce qui ne semble pas être le cas ici. - L'utilisation de propriétés avec des paramètres pour générer un code de hachage est également une source de problèmes.

Une méthode générale simple consiste à procéder comme suit:

return string.Format("{0}/{1}", str1, str2).GetHashCode();

À moins d’exigences de performances strictes, c’est la méthode la plus simple à laquelle je puisse penser et j’utilise fréquemment cette méthode lorsque j’ai besoin d’une clé composite. Il gère très bien les cas null et ne causera pas (m) de collisions de hachage (en général). Si vous attendez '/' dans vos chaînes, choisissez simplement un autre séparateur auquel vous ne vous attendez pas.

public override int GetHashCode()   
{       
    unchecked      
    {           
        return(str1 != null ? str1.GetHashCode() : 0) ^ (str2 != null ? str2.GetHashCode() : 0);       
    }   
}

En suivant les lignes, ReSharper suggère:

public int GetHashCode()
{
    unchecked
    {
        int hashCode;

        // String properties
        hashCode = (hashCode * 397) ^ (str1!= null ? str1.GetHashCode() : 0);
        hashCode = (hashCode * 397) ^ (str2!= null ? str1.GetHashCode() : 0);

        // int properties
        hashCode = (hashCode * 397) ^ intProperty;
        return hashCode;
    }
}

397 est un nombre premier de taille suffisante pour provoquer un débordement de la variable résultat et un peu de mélange des bits du hachage, ce qui permet une meilleure distribution des codes de hachage. Sinon, rien de spécial en 397 ne le distingue des autres nombres premiers de même ampleur.

Ah oui, comme l'a souligné Gary Shutler:

return str1.GetHashCode() + str2.GetHashCode();

Peut déborder. Vous pouvez essayer d'incarner long comme le suggère Artem, ou vous pouvez entourer l'énoncé dans le mot clé non vérifié:

return unchecked(str1.GetHashCode() + str2.GetHashCode());

Essayez celui-ci:

(((long)str1.GetHashCode()) + ((long)str2.GetHashCode())).GetHashCode()

Beaucoup de possibilités. P. ex.

retourne str1.GetHashCode () ^ str1.GetHashCode ()

Peut-être quelque chose comme str1.GetHashCode () + str2.GetHashCode ()? ou (str1.GetHashCode () + str2.GetHashCode ()) / 2? De cette façon, ce serait la même chose que str1 et str2 soient échangés ....

Triez-les, puis concatérez-les:

return ((str1.CompareTo(str2) < 1) ? str1 + str2 : str2 + str1)
    .GetHashCode();

Le résultat de GetHashCode est supposé être:

Aussi vite que possible.
Aussi unique que possible.

Gardant cela à l’esprit, je choisirais quelque chose comme ceci:

if (str1 == null)
    if (str2 == null)
        return 0;
    else
       return str2.GetHashCode();
else
    if (str2 == null)
        return str1.GetHashCode();
    else
       return ((ulong)str1.GetHashCode() | ((ulong)str2.GetHashCode() << 32)).GetHashCode();

Modifier: Vous avez oublié les valeurs nulles. Code corrigé.

Trop compliqué, et oublie les valeurs nulles, etc. Ceci est utilisé pour des choses comme le seau, vous pouvez donc vous en sortir avec quelque chose comme

if (null != str1) {
    return str1.GetHashCode();
}
if (null != str2) {
    return str2.GetHashCode();
}
//Not sure what you would put here, some constant value will do
return 0;

Cela est biaisé en supposant que str1 ne sera probablement pas commun dans une proportion exceptionnellement élevée d'instances.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow