Instructions GetHashCode en C #

J'ai lu dans le livre Essential C # 3.0 et .NET 3.5 que:

Les retours de GetHashCode () sur la durée de vie d'un objet particulier doivent être constants (la même valeur), même si les données de l'objet changent. Dans de nombreux cas, vous devez mettre en cache la méthode return pour appliquer cela.

Est-ce une directive valable?

J'ai essayé quelques types intégrés dans .NET et ils ne se sont pas comportés comme ça.

La réponse est la plupart du temps, c'est une directive valide, mais peut-être pas une règle valide. Cela ne raconte pas non plus toute l'histoire.

Le fait est que pour les types mutables, vous ne pouvez pas baser le code de hachage sur les données mutables car deux objets égaux doivent renvoyer le même code de hachage et le code de hachage doit être valide pour la durée de vie de l'objet. Si le code de hachage change, vous vous retrouvez avec un objet qui se perd dans une collection hachée car il ne vit plus dans la bonne corbeille de hachage.

Par exemple, l'objet A renvoie un hachage de 1. Ainsi, il va dans le bac 1 de la table de hachage. Ensuite, vous modifiez l'objet A de sorte qu'il renvoie un hachage de 2. Lorsqu'une table de hachage va le chercher, elle regarde dans le bac 2 et ne peut pas le trouver - l'objet est orphelin dans le bac 1. C'est pourquoi le code de hachage doit ne change pas pour la durée de vie de l'objet , et juste une raison pour laquelle l'écriture d'implémentations GetHashCode est une douleur dans le cul.

Mise à jour
Eric Lippert a publié un blog qui donne d'excellentes informations sur GetHashCode.

Mise à jour supplémentaire
J'ai apporté quelques modifications ci-dessus:

1. J'ai fait une distinction entre ligne directrice et règle.
2. J'ai frappé "pour la durée de vie de l'objet".

Une ligne directrice n'est qu'un guide, pas une règle. En réalité, il GetHashCodesuffit de suivre ces instructions lorsque les choses s'attendent à ce que l'objet suive les instructions, par exemple lorsqu'il est stocké dans une table de hachage. Si vous n'avez jamais l'intention d'utiliser vos objets dans des tables de hachage (ou tout autre élément qui repose sur les règles de GetHashCode), votre implémentation n'a pas besoin de suivre les instructions.

Lorsque vous voyez "pour la durée de vie de l'objet", vous devriez lire "pour le temps dont l'objet a besoin pour coopérer avec les tables de hachage" ou similaire. Comme la plupart des choses, il GetHashCodes'agit de savoir quand enfreindre les règles.

Cela fait longtemps, mais je pense néanmoins qu'il est encore nécessaire de donner une réponse correcte à cette question, y compris des explications sur le pourquoi et le comment. La meilleure réponse à ce jour est celle citant le MSDN de manière exhaustive - n'essayez pas de faire vos propres règles, les gars de MS savaient ce qu'ils faisaient.

Mais tout d'abord: la ligne directrice citée dans la question est fausse.

Maintenant les pourquoi - il y en a deux

Premièrement pourquoi : si le hashcode est calculé d'une manière, qu'il ne change pas pendant la durée de vie d'un objet, même si l'objet lui-même change, alors il romprait le contrat égal.

N'oubliez pas: «Si deux objets se comparent comme égaux, la méthode GetHashCode de chaque objet doit renvoyer la même valeur. Cependant, si deux objets ne sont pas comparables, les méthodes GetHashCode pour les deux objets ne doivent pas renvoyer des valeurs différentes.»

La deuxième phrase est souvent mal interprétée comme "La seule règle est qu'au moment de la création de l'objet, le hashcode des objets égaux doit être égal". Je ne sais pas vraiment pourquoi, mais c'est là aussi l'essence de la plupart des réponses.

Pensez à deux objets contenant un nom, où le nom est utilisé dans la méthode equals: Même nom -> même chose. Créer une instance A: Nom = Joe Créer une instance B: Nom = Peter

Hashcode A et Hashcode B ne seront probablement pas les mêmes. Que se passerait-il maintenant, lorsque le nom de l'instance B serait changé en Joe?

Selon la directive de la question, le hashcode de B ne changerait pas. Le résultat serait: A.Equals (B) ==> true Mais en même temps: A.GetHashCode () == B.GetHashCode () ==> false.

Mais exactement ce comportement est explicitement interdit par le contrat equals & hashcode.

Deuxièmement, pourquoi : bien qu'il soit - bien sûr - vrai, que des changements dans le hashcode pourraient casser les listes hachées et d'autres objets utilisant le hashcode, l'inverse est également vrai. Ne pas modifier le hashcode, dans le pire des cas, obtiendra des listes hachées, où tous les objets différents auront le même hashcode et seront donc dans le même hachage - cela se produit lorsque les objets sont initialisés avec une valeur standard, par exemple.

Voyons maintenant comment Eh bien, à première vue, il semble y avoir une contradiction - de toute façon, le code se cassera. Mais aucun des problèmes ne vient du hashcode changé ou inchangé.

La source des problèmes est bien décrite dans le MSDN:

À partir de l'entrée de hachage de MSDN:

Les objets clés doivent être immuables tant qu'ils sont utilisés comme clés dans la table de hachage.

Cela veut dire:

Tout objet qui crée une valeur de hachage doit changer la valeur de hachage, lorsque l'objet change, mais il ne doit pas - ne doit absolument pas - autoriser aucune modification de lui-même, lorsqu'il est utilisé dans une table de hachage (ou tout autre objet utilisant Hash, bien sûr) .

Tout d'abord, la manière la plus simple serait bien sûr de concevoir des objets immuables uniquement pour une utilisation dans des tables de hachage, qui seront créés comme des copies des objets normaux, les objets mutables en cas de besoin. À l'intérieur des objets immuables, il est évidemment correct de mettre en cache le hashcode, car il est immuable.

Deuxièmement, ou donnez à l'objet un drapeau "vous êtes haché maintenant", assurez-vous que toutes les données de l'objet sont privées, vérifiez le drapeau dans toutes les fonctions qui peuvent changer les données des objets et lancez une donnée d'exception si le changement n'est pas autorisé (c'est-à-dire que le drapeau est défini ). Maintenant, lorsque vous placez l'objet dans une zone hachée, assurez-vous de définir l'indicateur et, également, de désactiver l'indicateur, lorsqu'il n'est plus nécessaire. Pour faciliter l'utilisation, je vous conseille de définir automatiquement le drapeau dans la méthode "GetHashCode" - de cette façon, il ne peut pas être oublié. Et l'appel explicite d'une méthode "ResetHashFlag" garantira que le programmeur devra réfléchir, qu'il soit ou non autorisé à modifier les données des objets pour le moment.

Ok, que faut-il dire aussi: il y a des cas, où il est possible d'avoir des objets avec des données mutables, où le hashcode est néanmoins inchangé, lorsque les données des objets sont modifiées, sans violer le contrat equals & hashcode-contract.

Cela nécessite cependant que la méthode equals ne soit pas basée non plus sur les données mutables. Donc, si j'écris un objet et que je crée une méthode GetHashCode qui ne calcule une valeur qu'une seule fois et la stocke dans l'objet pour le renvoyer lors d'appels ultérieurs, alors je dois, encore une fois: absolument obligé, créer une méthode Equals, qui utilisera valeurs stockées pour la comparaison, de sorte que A.Equals (B) ne passera jamais non plus de faux à vrai. Sinon, le contrat serait rompu. Le résultat de cela sera généralement que la méthode Equals n'a aucun sens - ce n'est pas la référence d'origine est égale, mais ce n'est pas non plus une valeur égale. Parfois, cela peut être un comportement intentionnel (c.-à-d. Les enregistrements des clients), mais ce n'est généralement pas le cas.

Donc, modifiez simplement le résultat de GetHashCode, lorsque les données de l'objet changent, et si l'utilisation de l'objet à l'intérieur du hachage à l'aide de listes ou d'objets est prévue (ou simplement possible), rendez l'objet soit immuable ou créez un indicateur en lecture seule à utiliser pour le durée de vie d'une liste hachée contenant l'objet.

(À propos: tout cela n'est pas spécifique à C # ou .NET - c'est dans la nature de toutes les implémentations de table de hachage, ou plus généralement de toute liste indexée, que les données d'identification des objets ne doivent jamais changer, tant que l'objet est dans la liste . Un comportement inattendu et imprévisible se produira si cette règle est enfreinte. Quelque part, il peut y avoir des implémentations de liste, qui surveillent tous les éléments de la liste et effectuent une réindexation automatique de la liste - mais les performances de celles-ci seront sûrement horribles au mieux.)

Depuis MSDN

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

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

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

Cela signifie que si la ou les valeurs de l'objet changent, le code de hachage doit changer. Par exemple, une classe "Person" avec la propriété "Name" définie sur "Tom" doit avoir un code de hachage et un code différent si vous changez le nom en "Jerry". Sinon, Tom == Jerry, ce qui n'est probablement pas ce que vous auriez voulu.

Modifier :

Également de MSDN:

Les classes dérivées qui remplacent GetHashCode doivent également remplacer Equals pour garantir que deux objets considérés comme égaux ont le même code de hachage; sinon, le type Hashtable risque de ne pas fonctionner correctement.

À partir de l'entrée de hachage de MSDN :

Les objets clés doivent être immuables tant qu'ils sont utilisés comme clés dans la table de hachage.

La façon dont je lis cela est que les objets mutables doivent renvoyer des codes de hachage différents lorsque leurs valeurs changent, à moins qu'ils ne soient conçus pour être utilisés dans une table de hachage.

Dans l'exemple de System.Drawing.Point, l'objet est mutable, et le fait retourner un code de hachage différente lorsque la valeur change X ou Y. Cela en ferait un mauvais candidat à utiliser tel quel dans une table de hachage.

Je pense que la documentation concernant GetHashcode est un peu déroutante.

D'une part, MSDN déclare que le hashcode d'un objet ne doit jamais changer et être constant. D'autre part, MSDN indique également que la valeur de retour de GetHashcode doit être égale pour 2 objets, si ces 2 objets sont considérés comme égaux.

MSDN:

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

• Si deux objets se comparent comme égaux, la méthode GetHashCode de chaque objet doit renvoyer la même valeur. Toutefois, si deux objets ne se comparent pas comme égaux, les méthodes GetHashCode pour les deux objets ne doivent pas renvoyer des valeurs différentes.
• La méthode GetHashCode pour un objet doit systématiquement renvoyer le même code de hachage tant qu'il n'y a aucune modification de l'état de l'objet qui détermine la valeur de retour de la méthode Equals de l'objet. Notez que cela n'est vrai que pour l'exécution actuelle d'une application et qu'un code de hachage différent peut être renvoyé si l'application est réexécutée.
• Pour de meilleures performances, une fonction de hachage doit générer une distribution aléatoire pour toutes les entrées.

Ensuite, cela signifie que tous vos objets doivent être immuables ou que la méthode GetHashcode doit être basée sur les propriétés de votre objet qui sont immuables. Supposons par exemple que vous ayez cette classe (implémentation naïve):

public class SomeThing
{
      public string Name {get; set;}

      public override GetHashCode()
      {
          return Name.GetHashcode();
      }

      public override Equals(object other)
      {
           SomeThing = other as Something;
           if( other == null ) return false;
           return this.Name == other.Name;
      }
}

Cette implémentation enfreint déjà les règles qui peuvent être trouvées dans MSDN. Supposons que vous ayez 2 instances de cette classe; la propriété Name de instance1 est définie sur «Pol» et la propriété Name de instance2 est définie sur «Piet». Les deux instances renvoient un hashcode différent et elles ne sont pas non plus égales. Maintenant, supposons que je change le nom de instance2 en 'Pol', puis, selon ma méthode Equals, les deux instances doivent être égales, et selon l'une des règles de MSDN, elles doivent renvoyer le même hashcode.
Cependant, cela ne peut pas être fait, car le hashcode de instance2 changera et MSDN déclare que cela n'est pas autorisé.

Ensuite, si vous avez une entité, vous pouvez peut-être implémenter le hashcode afin qu'il utilise «l'identifiant primaire» de cette entité, qui est peut-être idéalement une clé de substitution ou une propriété immuable. Si vous avez un objet de valeur, vous pouvez implémenter le Hashcode afin qu'il utilise les «propriétés» de cet objet de valeur. Ces propriétés constituent la «définition» de l'objet de valeur. C'est bien sûr la nature d'un objet de valeur; vous n'êtes pas intéressé par son identité, mais plutôt par sa valeur.
Et, par conséquent, les objets de valeur doivent être immuables. (Tout comme ils le sont dans le framework .NET, la chaîne, la date, etc. sont tous des objets immuables).

Une autre chose qui me vient à l'esprit: au
cours de quelle 'session' (je ne sais pas vraiment comment je devrais appeler cela) 'GetHashCode' devrait renvoyer une valeur constante. Supposons que vous ouvrez votre application, chargez une instance d'un objet hors de la base de données (une entité) et obtenez son hashcode. Il renverra un certain nombre. Fermez l'application et chargez la même entité. Est-il nécessaire que le hashcode ait cette fois la même valeur que lorsque vous avez chargé l'entité la première fois? IMHO, non.

C'est un bon conseil. Voici ce que Brian Pepin a à dire à ce sujet:

Cela m'a fait trébucher plus d'une fois: assurez-vous que GetHashCode renvoie toujours la même valeur pendant toute la durée de vie d'une instance. N'oubliez pas que les codes de hachage sont utilisés pour identifier les «compartiments» dans la plupart des implémentations de table de hachage. Si le "compartiment" d'un objet change, une table de hachage peut ne pas être en mesure de trouver votre objet. Ces bogues peuvent être très difficiles à trouver, alors faites-le correctement du premier coup.

Ne répond pas directement à votre question, mais - si vous utilisez Resharper, n'oubliez pas qu'il possède une fonctionnalité qui génère une implémentation GetHashCode raisonnable (ainsi que la méthode Equals) pour vous. Vous pouvez bien sûr spécifier quels membres de la classe seront pris en compte lors du calcul du hashcode.

Consultez ce billet de blog de Marc Brooks:

VTO, RTO et GetHashCode () - oh! La la!

Et puis consultez le post de suivi (je ne peux pas lier car je suis nouveau, mais il y a un lien dans l'article initial) qui discute plus en détail et couvre quelques faiblesses mineures dans l'implémentation initiale.

C'était tout ce que j'avais besoin de savoir sur la création d'une implémentation GetHashCode (), il fournit même un téléchargement de sa méthode avec d'autres utilitaires, en bref de l'or.

Le hashcode ne change jamais, mais il est également important de comprendre d'où vient le Hashcode.

Si votre objet utilise la sémantique des valeurs, c'est-à-dire que l'identité de l'objet est définie par ses valeurs (comme String, Color, toutes les structures). Si l'identité de votre objet est indépendante de toutes ses valeurs, le Hashcode est identifié par un sous-ensemble de ses valeurs. Par exemple, votre entrée StackOverflow est stockée quelque part dans une base de données. Si vous modifiez votre nom ou votre adresse e-mail, votre entrée client reste la même, bien que certaines valeurs aient changé (en fin de compte, vous êtes généralement identifié par un long numéro de client).

Donc en bref:

Sémantique du type de valeur - Le hashcode est défini par des valeurs Sémantique du type de référence - Le hachage est défini par un identifiant

Je vous suggère de lire Domain Driven Design d'Eric Evans, où il aborde les entités par rapport aux types de valeur (ce qui est plus ou moins ce que j'ai tenté de faire ci-dessus) si cela n'a toujours pas de sens.

Consultez les lignes directrices et les règles pour GetHashCode par Eric Lippert