Conseils généraux et directives sur la manière de remplacer correctement object.GetHashCode ()

Selon MSDN , une fonction de hachage doit avoir les propriétés suivantes:

  1. Si deux objects sont identiques, la méthode GetHashCode pour chaque object doit renvoyer la même valeur. Toutefois, si deux objects ne sont pas comparables, les méthodes GetHashCode pour les deux objects ne doivent pas renvoyer de valeurs différentes.

  2. La méthode GetHashCode pour un object doit toujours renvoyer le même code de hachage tant qu’il n’y a aucune modification à l’état de l’object qui détermine la valeur de retour de la méthode Equals de l’object. Notez que cela est vrai uniquement pour l’exécution en cours d’une application et qu’un code de hachage différent peut être renvoyé si l’application est exécutée à nouveau.

  3. Pour une meilleure performance, une fonction de hachage doit générer une dissortingbution aléatoire pour toutes les entrées.


Je continue à me retrouver dans le scénario suivant: j’ai créé une classe, implémenté IEquatable et object.Equals(object) . MSDN déclare que:

Les types qui remplacent Equals doivent également remplacer GetHashCode; sinon, Hashtable pourrait ne pas fonctionner correctement.

Et puis ça s’arrête un peu pour moi. Car, comment pouvez-vous substituer correctement object.GetHashCode() ? Ne savez jamais vraiment par où commencer, et il semble y avoir beaucoup de pièges.

Ici, chez StackOverflow, il y a pas mal de questions liées à la substitution de GetHashCode, mais la plupart d’entre elles semblent concerner des cas particuliers et des problèmes spécifiques. Donc, je voudrais donc avoir une bonne compilation ici. Un aperçu avec des conseils généraux et des lignes direcsortingces. Que faire, que ne pas faire, les pièges courants, par où commencer, etc.

Je voudrais qu’il soit spécialement destiné à C #, mais je pense qu’il fonctionnera de la même manière pour d’autres langages .NET (?).


Je pense que le meilleur moyen est peut-être de créer une réponse par sujet avec une réponse rapide et courte (proche de la ligne unique si possible), puis peut-être quelques informations supplémentaires et terminer par des questions, discussions, articles de blog, etc. , s’il y en a. Je peux ensuite créer un article en tant que réponse acceptée (pour l’obtenir) avec juste une “table des matières”. Essayez de le garder court et concis. Et ne vous contentez pas de créer des liens vers d’autres questions et articles de blog. Essayez d’en prendre l’essentiel, puis faites plutôt un lien vers la source (d’autant plus que la source pourrait disparaître. Aussi, essayez d’éditer et d’améliorer les réponses plutôt que de créer des lots très similaires).

Je ne suis pas un très bon rédacteur technique, mais j’essaierai au moins de formater les réponses pour qu’elles se ressemblent, créent la table des matières, etc. J’essaierai également de rechercher certaines des questions connexes ici à SO ceux-ci et peut-être sortir l’essence de ceux que je peux gérer. Mais comme je ne suis pas très stable sur ce sujet, je vais essayer de restr à l’écart pour la plupart: p

Table des matières

  • Quand est-ce que je remplace l’ object.GetHashCode ?

  • Pourquoi dois-je remplacer object.GetHashCode ()?

  • Quels sont les nombres magiques vus dans les implémentations GetHashCode?


Des choses que j’aimerais voir couvertes, mais qui ne l’ont pas encore été:

  • Comment créer l’entier (Comment “convertir” un object en un int ne me semblait pas évident).
  • Sur quels champs baser le code de hachage.
    • S’il ne doit s’agir que de champs immuables, qu’en est-il s’il n’y a que des champs mutables?
  • Comment générer une bonne dissortingbution aléatoire. (Propriété MSDN # 3)
    • Une partie de ceci semble choisir un bon nombre premier magique (vu que 17, 23 et 397 ont été utilisés), mais comment le choisissez-vous et à quoi ça sert exactement?
  • Comment s’assurer que le code de hachage rest le même pendant toute la durée de vie de l’object. (Propriété MSDN n ° 2)
    • Surtout quand l’égalité est basée sur des champs mutables. (Propriété MSDN n ° 1)
  • Comment gérer les champs qui sont des types complexes (pas parmi les types C # intégrés ).
    • Objets et structures complexes, tableaux, collections, listes, dictionnaires, types génériques, etc.
    • Par exemple, même si la liste ou le dictionnaire peuvent être en lecture seule, cela ne signifie pas que le contenu en est.
  • Comment gérer les classes héritées.
    • Devez-vous en quelque sorte incorporer base.GetHashCode() dans votre code de hachage?
  • Pourriez-vous techniquement être juste paresseux et retourner 0? Briserait lourdement la ligne direcsortingce no 3 de MSDN, mais s’assurerait au moins que # 1 et # 2 étaient toujours vrais: P
  • Pièges et pièges courants.

Quels sont les nombres magiques souvent vus dans les implémentations GetHashCode?

Ils sont des nombres premiers. Les nombres premiers sont utilisés pour créer des codes de hachage car les nombres premiers maximisent l’utilisation de l’espace de code de hachage.

Spécifiquement, commencez par le petit nombre premier 3 et ne considérez que les nybbles d’ ordre inférieur des résultats:

  • 3 * 1 = 3 = 3 (mod 8) = 0011
  • 3 * 2 = 6 = 6 (mod 8) = 1010
  • 3 * 3 = 9 = 1 (mod 8) = 0001
  • 3 * 4 = 12 = 4 (mod 8) = 1000
  • 3 * 5 = 15 = 7 (mod 8) = 1111
  • 3 * 6 = 18 = 2 (mod 8) = 0010
  • 3 * 7 = 21 = 5 (mod 8) = 1001
  • 3 * 8 = 24 = 0 (mod 8) = 0000
  • 3 * 9 = 27 = 3 (mod 8) = 0011

Et on recommence. Mais vous remarquerez que les multiples successifs de notre prime ont généré toutes les permutations possibles de bits dans notre nybble avant de commencer à se répéter. Nous pouvons obtenir le même effet avec n’importe quel nombre premier et n’importe quel nombre de bits, ce qui rend les nombres premiers optimaux pour générer des codes de hachage presque aléatoires. La raison pour laquelle nous voyons habituellement des nombres premiers plus grands au lieu de petits nombres premiers tels que 3 dans l’exemple ci-dessus est que, pour un plus grand nombre de bits dans notre code de hachage, les résultats obtenus avec un petit nombre premier ne sont même pas pseudo aléatoires. séquence croissante jusqu’à ce qu’un débordement soit rencontré. Pour un caractère aléatoire optimal, il convient d’utiliser un nombre premier entraînant un débordement pour des coefficients relativement faibles, à moins que vous ne puissiez garantir que vos coefficients ne seront pas faibles.

Liens connexes:

  • Pourquoi ‘397’ est-il utilisé pour le remplacement de ReSharper GetHashCode?

Consultez les directives et règles pour GetHashCode par Eric Lippert

Vous devez le remplacer chaque fois que vous avez une mesure significative de l’égalité pour les objects de ce type (c.-à-d. Que vous avez la priorité sur Equals). Si vous saviez que l’object ne serait pas haché pour une raison quelconque, vous pourriez le laisser, mais il est peu probable que vous puissiez le savoir à l’avance.

Le hachage doit être basé uniquement sur les propriétés de l’object utilisées pour définir l’égalité, car deux objects considérés égaux doivent avoir le même code de hachage. En général, vous faites généralement quelque chose comme:

 public override int GetHashCode() { int mc = //magic constant, usually some prime return mc * prop1.GetHashCode() * prop2.GetHashCode * ... * propN.GetHashCode(); } 

Je suppose généralement que multiplier les valeurs ensemble produira une dissortingbution assez uniforme, en supposant que la fonction de hashcode de chaque propriété fait la même chose, bien que cela puisse être faux. En utilisant cette méthode, si les propriétés définissant l’égalité des objects changent, alors le code de hachage est également susceptible de changer, ce qui est acceptable pour la définition # 2 de votre question. Il traite également de tous les types de manière uniforme.

Vous pourriez renvoyer la même valeur pour toutes les instances, même si cela ralentirait les algorithmes utilisant le hachage (tels que les dictionnaires) – essentiellement toutes les instances seront hachées vers le même compartiment et la recherche deviendra alors O (n) au lieu de O (1). Cela évite bien sûr les avantages liés à l’utilisation de telles structures pour la recherche.

Pourquoi dois-je remplacer object.GetHashCode() ?

La substitution de cette méthode est importante car la propriété suivante doit toujours restr vraie:

Si deux objects sont identiques, la méthode GetHashCode pour chaque object doit renvoyer la même valeur.

La raison, comme l’a déclaré JaredPar dans un article sur la mise en œuvre de l’égalité, est que

De nombreuses classes utilisent le code de hachage pour classer un object. En particulier, les tables de hachage et les dictionnaires ont tendance à placer des objects dans des compartiments basés sur leur code de hachage. En vérifiant si un object est déjà dans la table de hachage, il le recherchera d’abord dans un compartiment. Si deux objects sont égaux mais ont des codes de hachage différents, ils peuvent être placés dans des compartiments différents et le dictionnaire ne peut pas rechercher l’object.

Liens connexes:

  • Dois-je remplacer GetHashCode et Equals dans les nouvelles classes?
  • Dois-je remplacer GetHashCode () sur les types de référence?
  • Remplacer Equals et GetHashCode Question
  • Pourquoi est-il important de remplacer GetHashCode lorsque la méthode Equals est remplacée par C #?
  • Mettre correctement en œuvre l’égalité dans VB

A) Vous devez remplacer Equals et GetHashCode si vous souhaitez utiliser l’égalité de valeur au lieu de l’égalité de référence par défaut. Avec la dernière, deux références d’object sont égales si elles se réfèrent toutes deux à la même instance d’object. Dans le premier cas, ils sont égaux si leur valeur est la même, même s’ils se réfèrent à des objects différents. Par exemple, vous souhaitez probablement utiliser l’égalité des valeurs pour les objects Date, Money et Point.

B) Pour implémenter une égalité de valeur, vous devez remplacer Equals et GetHashCode. Les deux devraient dépendre des champs de l’object qui encapsulent la valeur. Par exemple, Date.Année, Date.Mois et Date.Day; ou Money.Currency et Money.Amount; ou Point.X, Point.Y et Point.Z. Vous devez également envisager de remplacer opérateur ==, opérateur! =, Opérateur .

C) Le hashcode n’a pas à restr constant pendant toute la durée de vie de l’object. Cependant, il doit restr immuable tout en participant en tant que clé dans un hash. De MSDN doco pour Dictionary: “Tant qu’un object est utilisé comme clé dans le Dictionary <(Of <(TKey, TValue>)>), il ne doit pas changer de quelque manière que ce soit qui affecte sa valeur de hachage.” Si vous devez modifier la valeur d’une clé, supprimez-la du dictionnaire, modifiez la valeur de la clé et remplacez l’entrée.

D) IMO, vous simplifierez la vie si vos objects de valeur sont eux-mêmes immuables.

Quand dois-je remplacer object.GetHashCode() ?

Comme MSDN le dit:

Les types qui remplacent Equals doivent également remplacer GetHashCode; sinon, Hashtable pourrait ne pas fonctionner correctement.

Liens connexes:

  • Quand substituer GetHashCode ()?

Sur quels champs baser le code de hachage? S’il ne doit s’agir que de champs immuables, qu’en est-il s’il n’y a que des champs mutables?

Il n’a pas besoin d’être basé uniquement sur des champs immuables. Je me baserais sur les champs qui déterminent le résultat de la méthode des égaux.

Comment s’assurer que le code de hachage rest le même pendant toute la durée de vie de l’object. (Propriété MSDN # 2) Surtout lorsque l’égalité est basée sur des champs mutables. (Propriété MSDN n ° 1)

Vous semblez mal comprendre la propriété # 2. Le hashcode n’a pas besoin de restr le même pendant toute la durée de vie des objects. Il suffit de restr le même tant que les valeurs qui déterminent le résultat de la méthode égale ne sont pas modifiées. Donc, logiquement, vous basez le hashcode sur ces valeurs uniquement. Alors il ne devrait pas y avoir de problème.

 public override int GetHashCode() { return IntProp1 ^ IntProp2 ^ StrProp3.GetHashCode() ^ StrProp4.GetHashCode ^ CustomClassProp.GetHashCode; } 

Faites la même chose dans la méthode GetHasCode de GetHasCode . Fonctionne comme un charme.