Directives 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 object particulier doivent être constants (même valeur), même si les données de l’object changent. Dans de nombreux cas, vous devez mettre en cache la méthode return pour appliquer cela.

Est-ce une directive valide?

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

La réponse est principalement, 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 objects é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’object. Si le code de hachage change, vous vous retrouvez avec un object qui se perd dans une collection hachée, car il ne vit plus dans le bon hachage.

Par exemple, l’object A retourne un hachage de 1. Il va donc dans la case 1 de la table de hachage. Ensuite, vous changez d’object A de telle sorte qu’il retourne un hachage de 2. Quand une table de hachage la recherche, elle regarde dans la corbeille 2 et ne la trouve pas – l’object est orphelin dans la corbeille 1. C’est pourquoi le code de hachage doit pas changer pour la durée de vie de l’object , et juste une des raisons pour lesquelles l’écriture d’implémentations GetHashCode est une douleur dans le cul.

Mettre à jour
Eric Lippert a publié un blog qui fournit d’excellentes informations sur GetHashCode .

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

  1. J’ai fait une distinction entre directive et règle.
  2. J’ai traversé “pour la durée de vie de l’object”.

Une directive n’est qu’un guide, pas une règle. En réalité, GetHashCode doit uniquement suivre ces instructions lorsque des éléments attendent que l’object suive les instructions, par exemple lorsqu’il est stocké dans une table de hachage. Si vous n’avez jamais l’intention d’utiliser vos objects dans des tables de hachage (ou tout autre élément reposant 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’object”, vous devriez lire “pendant le temps où l’object doit coopérer avec des tables de hachage” ou similaire. Comme la plupart des choses, GetHashCode consiste à savoir quand briser les règles.

Cela fait longtemps, mais je pense néanmoins qu’il est toujours 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 qui cite le MSDN de manière épuisante – n’essayez pas de définir vos propres règles, les membres de la MS savent ce qu’ils font.

Mais avant tout: la ligne direcsortingce citée dans la question est erronée.

Maintenant les pourquoi – il y en a deux

D’abord pourquoi : si le code de hachage est calculé d’une manière, il ne change pas pendant la durée de vie d’un object, même si l’object lui-même change, que cela ne briserait pas le contrat égal.

Rappelez-vous: “Si deux objects sont égaux, 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.”

La deuxième phrase est souvent interprétée comme “La seule règle est que, au moment de la création de l’object, le code de hachage des objects égaux doit être égal”. Je ne sais pas vraiment pourquoi, mais c’est aussi l’essence de la plupart des réponses ici.

Pensez à deux objects contenant un nom, où le nom est utilisé dans la méthode égale: 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 d’instance B serait changé en Joe?

Selon la ligne direcsortingce de la question, le code de hachage 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 les égaux & hashcode-contract.

Deuxième raison : Bien que ce soit – bien sûr – vrai, que les changements dans le hashcode pourraient casser les listes de hachage et autres objects en utilisant le code de hachage, l’inverse est également vrai. Si vous ne modifiez pas le hashcode, vous obtiendrez, dans le pire des cas, des listes de hachage, où de nombreux objects auront le même code de hachage et se retrouveront dans la même corbeille, par exemple lorsque les objects sont initialisés.


Maintenant, en arrivant au bout des doigts Eh bien, au premier abord, il semble y avoir une contradiction – de toute façon, le code va casser. Mais aucun problème ne provient d’un hashcode modifié ou inchangé.

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

De l’entrée de la table de hachage de MSDN:

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

Cela signifie:

Tout object qui crée une valeur de hachage doit changer la valeur de hachage, lorsque l’object change, mais il ne doit absolument pas y avoir de modifications, lorsqu’il est utilisé dans une table de hachage (ou tout autre object utilisant du hachage, bien sûr) .

Tout d’abord, la manière la plus simple serait bien sûr de concevoir des objects immuables uniquement pour les hashtables, qui seront créés en tant que copies des objects normaux, mutables si nécessaire. À l’intérieur des objects immuables, il est tout à fait acceptable de mettre le code de hachage en cache, car il est immuable.

Deuxièmement, comment donner à l’object un libellé “vous êtes haché maintenant”, vous assurer que toutes les données d’object sont privées, vérifier l’indicateur dans toutes les fonctions qui peuvent modifier les données d’objects et générer une exception si le changement n’est pas autorisé ). Maintenant, lorsque vous placez l’object dans une zone hachée, assurez-vous de définir l’indicateur et, aussi, de désélectionner le drapeau lorsqu’il n’est plus nécessaire. Pour plus de facilité, je vous conseille de définir le drapeau automatiquement dans la méthode “GetHashCode” – de cette façon, il ne peut pas être oublié. Et l’appel explicite d’une méthode “ResetHashFlag” assurera que le programmeur devra réfléchir, qu’il soit ou non autorisé à modifier les données des objects maintenant.

Ok, ce qui devrait être dit aussi: Il y a des cas où il est possible d’avoir des objects avec des données mutables, où le hashcode est néanmoins inchangé, lorsque les données des objects sont modifiées, sans violer les égaux & hashcode-contract.

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

Donc, il suffit de modifier le résultat GetHashCode, lorsque les données de l’object changent, et si l’utilisation de l’object à l’intérieur du hachage utilisant des listes ou des objects est prévue (ou simplement possible), il rendra l’object immuable ou créera un indicateur readonly durée de vie d’une liste hachée contenant l’object.

(D’ailleurs, tout ceci n’est pas spécifique à C # oder .NET – il est dans la nature de toutes les implémentations de hashtables, ou plus généralement de toute liste indexée, que les données d’identification des objects ne doivent jamais changer pendant que l’object est dans la liste Un comportement imprévisible et imprévisible se produira si cette règle est rompue: quelque part, il peut y avoir des implémentations de listes qui surveillent tous les éléments de la liste et réindexent automatiquement la liste, mais leurs performances seront certainement horribles.

À partir de MSDN

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.

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.

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

Cela signifie que si la ou les valeurs de l’object 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 surchargent GetHashCode doivent également remplacer Equals pour garantir que deux objects considérés comme égaux ont le même code de hachage; sinon, le type Hashtable peut ne pas fonctionner correctement.

De l’entrée de la table de hachage de MSDN :

Les objects 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 ceci est que les objects mutables doivent renvoyer des codes de hachage différents à mesure que leurs valeurs changent, sauf s’ils sont conçus pour être utilisés dans une table de hachage.

Dans l’exemple de System.Drawing.Point, l’object est mutable et renvoie un code de hachage différent lorsque la valeur X ou Y change. Cela ferait un mauvais candidat pour être utilisé tel quel dans une hashtable.

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

D’une part, MSDN indique que le code de hachage d’un object ne doit jamais changer et être constant. D’autre part, MSDN indique également que la valeur de retour de GetHashcode doit être égale à 2 si ces 2 objects sont considérés égaux.

MSDN:

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

  • 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.
  • 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.
  • Pour une meilleure performance, une fonction de hachage doit générer une dissortingbution aléatoire pour toutes les entrées.

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

 public class SomeThing { public ssortingng 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 viole déjà les règles disponibles 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 code de hachage différent et elles ne sont pas égales. Maintenant, supposons que je change le nom d’instance2 en ‘Pol’, alors, 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 code de hachage.
Toutefois, cela ne peut pas être fait, car le code de hachage d’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 code de hachage afin qu’il utilise l’identificateur primaire de cette entité, qui est peut-être idéalement une clé de substitution, ou une propriété immuable. Si vous avez un object value, vous pouvez implémenter le Hashcode afin qu’il utilise les propriétés de cet object de valeur. Ces propriétés constituent la définition de l’object valeur. C’est bien sûr la nature d’un object de valeur; votre identité ne vous intéresse pas, mais plutôt sa valeur.
Et, par conséquent, les objects de valeur doivent être immuables. (Tout comme ils sont dans le framework .NET, la chaîne, la date, etc. sont tous des objects immuables).

Une autre chose qui vient à l’esprit:
Au cours de quelle session (je ne sais pas vraiment comment appeler cela), “GetHashCode” devrait renvoyer une valeur constante. Supposons que vous ouvriez votre application, chargez une instance d’un object hors de la firebase database (une entité) et obtenez son code de hachage. Il retournera un certain nombre. Fermez l’application et chargez la même entité. Est-il nécessaire que le hashcode cette fois ait la même valeur que lorsque vous avez chargé l’entité la première fois? IMHO, pas.

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

Cela m’a déclenché plus d’une fois: assurez-vous que GetHashCode renvoie toujours la même valeur pendant toute la durée de vie d’une instance. Rappelez-vous que les codes de hachage sont utilisés pour identifier les “compartiments” dans la plupart des implémentations de hashtables. Si le “compartiment” d’un object change, une table de hachage ne pourra peut-être pas trouver votre object. Ceux-ci peuvent être des bogues très difficiles à trouver, alors faites-le bien la première fois.

Ne répondant pas directement à votre question, mais – si vous utilisez Resharper, n’oubliez pas qu’il comporte 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.

Découvrez cet article de Marc Brooks:

VTO, RTO et GetHashCode () – oh!

Et puis vérifiez le post de suivi (ne peut pas être lié à ma nouvelle version, mais il y a un lien dans l’article initial) qui discute plus avant et couvre quelques faiblesses mineures dans la mise en œuvre initiale.

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

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

Si votre object utilise la sémantique de valeur, c’est-à-dire que l’identité de l’object est définie par ses valeurs (comme Ssortingng, Color, toutes les structures). Si l’identité de votre object 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 dans une firebase database quelque part. Si vous modifiez votre nom ou votre adresse e-mail, votre entrée client rest la même, bien que certaines valeurs aient changé (en fin de compte, vous êtes généralement identifié par un identifiant client long).

Donc en bref:

Sémantique du type de valeur – Hashcode est défini par des valeurs Sémantique du type de référence – Hashcode est défini par un identifiant

Je vous suggère de lire Domain Driven Design d’Eric Evans, où il va dans les entités vs les 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 directives et règles pour GetHashCode par Eric Lippert