Pourquoi est-il important de remplacer GetHashCode lorsque la méthode Equals est remplacée?

1445

Étant donné la classe suivante

public class Foo
{
    public int FooId { get; set; }
    public string FooName { get; set; }

    public override bool Equals(object obj)
    {
        Foo fooItem = obj as Foo;

        if (fooItem == null) 
        {
           return false;
        }

        return fooItem.FooId == this.FooId;
    }

    public override int GetHashCode()
    {
        // Which is preferred?

        return base.GetHashCode();

        //return this.FooId.GetHashCode();
    }
}

J'ai remplacé la Equalsméthode car Fooreprésente une ligne pour la Footable s. Quelle est la méthode préférée pour remplacer le GetHashCode?

Pourquoi est-il important de passer outre GetHashCode?

David Basarab
la source
36
Il est important d'implémenter equals et gethashcode, en raison de collisions, en particulier lors de l'utilisation de dictionnaires. si deux objets retournent le même hashcode, ils sont insérés dans le dictionnaire avec chaînage. Lors de l'accès à l'élément, la méthode de l'égalité est utilisée.
DarthVader

Réponses:

1320

Oui, il est important que votre élément soit utilisé comme clé dans un dictionnaire, ou HashSet<T>, etc. - car il est utilisé (en l'absence de coutume IEqualityComparer<T>) pour regrouper les éléments dans des compartiments. Si le code de hachage pour deux éléments ne correspond pas, ils peuvent ne jamais être considérés comme égaux ( Equals ne sera simplement jamais appelé).

La méthode GetHashCode () doit refléter la Equalslogique; les règles sont les suivantes:

  • si deux choses sont égales ( Equals(...) == true), elles doivent renvoyer la même valeur pourGetHashCode()
  • si le GetHashCode()est égal, il n'est pas nécessaire qu'ils soient identiques; c'est une collision, et Equalssera appelé pour voir s'il s'agit d'une réelle égalité ou non.

Dans ce cas, il semble que " return FooId;" soit une GetHashCode()implémentation appropriée . Si vous testez plusieurs propriétés, il est courant de les combiner en utilisant du code comme ci-dessous, pour réduire les collisions diagonales (c'est-à-dire de sorte qu'elles new Foo(3,5)aient un code de hachage différent new Foo(5,3)):

unchecked // only needed if you're compiling with arithmetic checks enabled
{ // (the default compiler behaviour is *disabled*, so most folks won't need this)
    int hash = 13;
    hash = (hash * 7) + field1.GetHashCode();
    hash = (hash * 7) + field2.GetHashCode();
    ...
    return hash;
}

Oh - pour plus de commodité, vous pouvez également envisager de fournir ==et des !=opérateurs lors de la substitution de Equalset GetHashCode.


Une démonstration de ce qui se passe lorsque vous vous trompez est ici .

Marc Gravell
la source
49
Puis-je demander ahy multipliez-vous avec de tels facteurs?
Leandro López
22
En fait, je pourrais probablement en perdre un; le but est d'essayer de minimiser le nombre de collisions - pour qu'un objet {1,0,0} ait un hachage différent de {0,1,0} et {0,0,1} (si vous voyez ce que je veux dire ),
Marc Gravell
13
J'ai modifié les chiffres pour le rendre plus clair (et ajouté une graine). Certains codes utilisent des nombres différents - par exemple, le compilateur C # (pour les types anonymes) utilise une valeur de départ de 0x51ed270b et un facteur de -1521134295.
Marc Gravell
76
@Leandro López: Habituellement, les facteurs sont choisis pour être des nombres premiers car cela réduit le nombre de collisions.
Andrei Rînea
29
"Oh - pour plus de commodité, vous pouvez également envisager de fournir des opérateurs == et! = Lorsque vous remplacez Equals et GethashCode.": Microsoft décourage l'implémentation de l'opérateur == pour les objets qui ne sont pas immuables - msdn.microsoft.com/en-us/library/ ms173147.aspx - "Ce n'est pas une bonne idée de remplacer l'opérateur == dans les types non immuables."
antiduh
137

Il est en fait très difficile à implémenter GetHashCode()correctement car, en plus des règles que Marc a déjà mentionnées, le code de hachage ne devrait pas changer pendant la durée de vie d'un objet. Par conséquent, les champs utilisés pour calculer le code de hachage doivent être immuables.

J'ai finalement trouvé une solution à ce problème lorsque je travaillais avec NHibernate. Mon approche consiste à calculer le code de hachage à partir de l'ID de l'objet. L'ID ne peut être défini que par le constructeur, donc si vous voulez changer l'ID, ce qui est très peu probable, vous devez créer un nouvel objet qui a un nouvel ID et donc un nouveau code de hachage. Cette approche fonctionne mieux avec les GUID car vous pouvez fournir un constructeur sans paramètre qui génère aléatoirement un ID.

Albic
la source
20
@vanja. Je crois que cela a à voir avec: si vous ajoutez l'objet à un dictionnaire puis changez l'identifiant de l'objet, lors de la récupération plus tard, vous utiliserez un hachage différent pour le récupérer afin de ne jamais l'obtenir du dictionnaire.
ANeves
74
La documentation de Microsoft sur la fonction GetHashCode () n'indique ni n'implique que le hachage d'objet doit rester cohérent pendant sa durée de vie. En fait, il explique spécifiquement un cas admissible dans lequel il pourrait ne pas l' être : "La méthode GetHashCode pour un objet doit toujours 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 de la méthode Equals de l'objet . "
PeterAllenWebb
37
"le code de hachage ne doit pas changer pendant la durée de vie d'un objet" - ce n'est pas vrai.
apocalypse
7
Une meilleure façon de dire que c'est "le code de hachage (ni l'évaluation des égaux) devrait changer pendant la période pendant laquelle l'objet est utilisé comme clé pour une collection" Donc, si vous ajoutez l'objet à un dictionnaire en tant que clé, vous devez vous assurer que GetHashCode et Equals ne modifieront pas leur sortie pour une entrée donnée tant que vous n'aurez pas supprimé l'objet du dictionnaire.
Scott Chamberlain
11
@ScottChamberlain Je pense que vous avez oublié PAS dans votre commentaire, cela devrait être: "le code de hachage (ni l'évaluation des égaux) ne doit PAS changer pendant la période pendant laquelle l'objet est utilisé comme clé pour une collection". Droite?
Stan Prokop
57

En remplaçant Equals, vous déclarez essentiellement que vous êtes celui qui sait mieux comparer deux instances d'un type donné, vous êtes donc probablement le meilleur candidat pour fournir le meilleur code de hachage.

Voici un exemple de la façon dont ReSharper écrit une fonction GetHashCode () pour vous:

public override int GetHashCode()
{
    unchecked
    {
        var result = 0;
        result = (result * 397) ^ m_someVar1;
        result = (result * 397) ^ m_someVar2;
        result = (result * 397) ^ m_someVar3;
        result = (result * 397) ^ m_someVar4;
        return result;
    }
}

Comme vous pouvez le voir, il essaie simplement de deviner un bon code de hachage basé sur tous les champs de la classe, mais puisque vous connaissez le domaine ou les plages de valeurs de votre objet, vous pouvez toujours en fournir un meilleur.

Prendre au piège
la source
7
Cela ne retournera-t-il pas toujours zéro? Devrait probablement initialiser le résultat à 1! Nécessite également quelques points-virgules supplémentaires.
Sam Mackrill
16
Vous savez ce que fait l'opérateur XOR (^)?
Stephen Drew
1
Comme je l'ai dit, c'est ce que R # écrit pour vous (du moins c'est ce qu'il a fait en 2008) lorsqu'on lui a demandé de le faire. De toute évidence, cet extrait est destiné à être modifié par le programmeur d'une manière ou d'une autre. Quant aux points-virgules manquants ... oui, on dirait que je les ai laissés quand j'ai copié-collé le code d'une sélection de région dans Visual Studio. Je pensais aussi que les gens trouveraient les deux.
Piège
3
@SamMackrill J'ai ajouté les points-virgules manquants.
Matthew Murdoch
5
@SamMackrill Non, il ne retournera pas toujours 0. 0 ^ a = adonc 0 ^ m_someVar1 = m_someVar1. Il pourrait tout aussi bien définir la valeur initiale de resultà m_someVar1.
Millie Smith
41

N'oubliez pas de vérifier le paramètre obj nulllors de la substitution Equals(). Et comparez également le type.

public override bool Equals(object obj)
{
    Foo fooItem = obj as Foo;

    if (fooItem == null)
    {
       return false;
    }

    return fooItem.FooId == this.FooId;
}

La raison en est: Equalsdoit renvoyer false lors de la comparaison avec null. Voir également http://msdn.microsoft.com/en-us/library/bsc2ak47.aspx

huha
la source
6
Cette vérification de type échouera dans le cas où une sous-classe se réfère à la méthode Superclass Equals dans le cadre de sa propre comparaison (c'est-à-dire base.Equals (obj)) - devrait être utilisée à la place
sweetfa
@sweetfa: Cela dépend de la façon dont la méthode Equals de la sous-classe est implémentée. Il pourrait également appeler base.Equals ((BaseType) obj)) qui fonctionnerait bien.
huha
2
Non, ce ne sera pas le cas: msdn.microsoft.com/en-us/library/system.object.gettype.aspx . Et d'ailleurs, l'implémentation d'une méthode ne devrait pas échouer ou réussir selon la façon dont elle est appelée. Si le type d'exécution d'un objet est une sous-classe d'une classe de base, Equals () de la classe de base doit renvoyer true s'il objest en effet égal thisquelle que soit la façon dont Equals () de la classe de base a été appelée.
Jupiter
2
Le déplacement fooItemvers le haut puis la vérification de la valeur Null fonctionnera mieux dans le cas de NULL ou d'un type incorrect.
IllidanS4 veut que Monica revienne le
1
@ 40Alpha Eh bien, oui, alors ce obj as Fooserait invalide.
IllidanS4 veut que Monica revienne le
35

Que diriez-vous:

public override int GetHashCode()
{
    return string.Format("{0}_{1}_{2}", prop1, prop2, prop3).GetHashCode();
}

En supposant que les performances ne sont pas un problème :)

Ludmil Tinkov
la source
1
erm - mais vous retournez une chaîne pour une méthode basée sur int; _0
jim tollan
32
Non, il appelle GetHashCode () à partir de l'objet String, qui retourne un int.
Richard Clayton
3
Je ne m'attends pas à ce que ce soit aussi rapide que je le souhaiterais, non seulement pour la boxe impliquée pour les types de valeur, mais aussi pour les performances de string.Format. Un autre geek que j'ai vu est new { prop1, prop2, prop3 }.GetHashCode(). Je ne peux pas dire si l'on serait plus lent entre ces deux. N'abusez pas des outils.
nawfal
16
Cela reviendra vrai pour { prop1="_X", prop2="Y", prop3="Z" }et { prop1="", prop2="X_Y", prop3="Z_" }. Vous ne voulez probablement pas ça.
voetsjoeba
2
Oui, vous pouvez toujours remplacer le symbole de soulignement par quelque chose de moins commun (par exemple •, ▲, ►, ◄, ☺, ☻) et espérons que vos utilisateurs n'utiliseront pas ces symboles ... :)
Ludmil Tinkov
13

Nous avons deux problèmes à résoudre.

  1. Vous ne pouvez pas indiquer GetHashCode()si un champ de l'objet peut être modifié. Souvent, un objet ne sera JAMAIS utilisé dans une collection qui en dépend GetHashCode(). Ainsi, le coût de mise en œuvre GetHashCode()n'en vaut souvent pas la peine, ou ce n'est pas possible.

  2. Si quelqu'un place votre objet dans une collection qui appelle GetHashCode()et que vous avez remplacé Equals()sans également vous GetHashCode()comporter correctement, cette personne peut passer des jours à dépister le problème.

Par conséquent, je le fais par défaut.

public class Foo
{
    public int FooId { get; set; }
    public string FooName { get; set; }

    public override bool Equals(object obj)
    {
        Foo fooItem = obj as Foo;

        if (fooItem == null)
        {
           return false;
        }

        return fooItem.FooId == this.FooId;
    }

    public override int GetHashCode()
    {
        // Some comment to explain if there is a real problem with providing GetHashCode() 
        // or if I just don't see a need for it for the given class
        throw new Exception("Sorry I don't know what GetHashCode should do for this class");
    }
}
Ian Ringrose
la source
5
Lancer une exception à partir de GetHashCode est une violation du contrat d'objet. Il n'y a aucune difficulté à définir une GetHashCodefonction telle que deux objets égaux renvoient le même code de hachage; return 24601;et return 8675309;seraient tous deux des implémentations valides de GetHashCode. Les performances de Dictionaryne seront décentes que lorsque le nombre d'éléments est petit et deviendront très mauvaises si le nombre d'éléments devient important, mais cela fonctionnera correctement dans tous les cas.
supercat
2
@supercat, Il n'est pas possible d'implémenter GetHashCode de manière sensée si les champs d'identification dans l'objet peuvent changer, car le code de hachage ne doit jamais changer. Faire ce que vous dites pourrait conduire quelqu'un à passer plusieurs jours à dépister le problème de performances, puis plusieurs semaines sur un grand système de refonte pour supprimer l'utilisation des dictionnaires.
Ian Ringrose
2
J'avais l'habitude de faire quelque chose comme ça pour toutes les classes que j'ai définies qui avaient besoin d'Equals (), et où j'étais absolument sûr de ne jamais utiliser cet objet comme clé dans une collection. Puis un jour, un programme dans lequel j'avais utilisé un objet comme celui-ci en entrée d'un contrôle DevExpress XtraGrid s'est écrasé. Il s'avère que XtraGrid, derrière mon dos, créait un HashTable ou quelque chose basé sur mes objets. Je suis entré dans une dispute mineure avec les gens du support DevExpress à ce sujet. J'ai dit qu'il n'était pas intelligent qu'ils basent la fonctionnalité et la fiabilité de leurs composants sur une implémentation client inconnue d'une méthode obscure.
RenniePet
Les gens de DevExpress étaient plutôt sournois, disant essentiellement que je dois être un idiot pour lancer une exception dans une méthode GetHashCode (). Je pense toujours qu'ils devraient trouver une méthode alternative pour faire ce qu'ils font - je me souviens de Marc Gravell sur un autre fil décrivant comment il construit un dictionnaire d'objets arbitraires sans dépendre de GetHashCode () - ne se souvient pas comment il l'a fait bien que.
RenniePet
4
@RenniePet, il vaut mieux avoir un béguin dû au lancement d'une exception, puis avoir un bogue très difficile à trouver en raison d'une implémentation non valide.
Ian Ringrose
12

C'est parce que le framework requiert que deux objets identiques doivent avoir le même hashcode. Si vous remplacez la méthode equals pour effectuer une comparaison spéciale de deux objets et que les deux objets sont considérés comme identiques par la méthode, le code de hachage des deux objets doit également être le même. (Les dictionnaires et les tables de hachage reposent sur ce principe).

kemiller2002
la source
11

Juste pour ajouter les réponses ci-dessus:

Si vous ne remplacez pas Equals, le comportement par défaut est que les références des objets sont comparées. La même chose s'applique au hashcode - l'implémentation par défaut est généralement basée sur une adresse mémoire de la référence. Étant donné que vous avez remplacé Equals, cela signifie que le comportement correct consiste à comparer tout ce que vous avez implémenté sur Equals et non les références, vous devez donc faire de même pour le code de hachage.

Les clients de votre classe s'attendront à ce que le hashcode ait une logique similaire à la méthode equals, par exemple les méthodes linq qui utilisent un IEqualityComparer comparent d'abord les hashcodes et seulement s'ils sont égaux ils compareront la méthode Equals () qui pourrait être plus chère pour s'exécuter, si nous n'avons pas implémenté le code de hachage, un objet égal aura probablement des codes de hachage différents (car ils ont une adresse mémoire différente) et sera déterminé à tort comme non égal (Equals () ne sera même pas atteint).

En outre, à l'exception du problème selon lequel vous ne pourrez peut-être pas trouver votre objet si vous l'utilisez dans un dictionnaire (car il a été inséré par un code de hachage et lorsque vous le recherchez, le code de hachage par défaut sera probablement différent et à nouveau égal à () ne sera même pas appelé, comme l'explique Marc Gravell dans sa réponse, vous introduisez également une violation du dictionnaire ou du concept de hashset qui ne devrait pas autoriser des clés identiques - vous avez déjà déclaré que ces objets sont essentiellement les mêmes lorsque vous écrasez Equals donc vous ne Je ne veux pas les deux comme des clés différentes sur une structure de données qui supposent avoir une clé unique. Mais parce qu'ils ont un code de hachage différent, la "même" clé sera insérée comme différente.

BornToCode
la source
8

Le code de hachage est utilisé pour les collections basées sur le hachage comme Dictionary, Hashtable, HashSet etc. Le but de ce code est de pré-trier très rapidement un objet spécifique en le plaçant dans un groupe spécifique (bucket). Ce pré-tri aide énormément à trouver cet objet lorsque vous devez le récupérer à partir de la collection de hachage car le code doit rechercher votre objet dans un seul compartiment au lieu de tous les objets qu'il contient. La meilleure distribution des codes de hachage (meilleure unicité) la récupération plus rapide. Dans une situation idéale où chaque objet a un code de hachage unique, le trouver est une opération O (1). Dans la plupart des cas, il s'approche de O (1).

Maciej
la source
7

Ce n'est pas nécessairement important; cela dépend de la taille de vos collections et de vos exigences de performances et si votre classe sera utilisée dans une bibliothèque où vous ne connaissez peut-être pas les exigences de performances. Je sais souvent que mes tailles de collection ne sont pas très grandes et mon temps est plus précieux que quelques microsecondes de performances gagnées en créant un code de hachage parfait; donc (pour se débarrasser de l'avertissement ennuyeux du compilateur) j'utilise simplement:

   public override int GetHashCode()
   {
      return base.GetHashCode();
   }

(Bien sûr, je pourrais également utiliser un #pragma pour désactiver l'avertissement, mais je préfère cette méthode.)

Lorsque vous êtes dans la position que vous avez besoin de la performance que tous les problèmes mentionnés par d' autres appliquent ici, bien sûr. Plus important - sinon, vous obtiendrez des résultats erronés lors de la récupération d'éléments à partir d'un ensemble de hachage ou d'un dictionnaire: le code de hachage ne doit pas varier avec la durée de vie d'un objet (plus précisément, à chaque fois que le code de hachage est nécessaire, par exemple en étant une clé dans un dictionnaire): par exemple, ce qui suit est faux car Value est public et peut donc être modifié en externe pour la classe pendant la durée de vie de l'instance, vous ne devez donc pas l'utiliser comme base pour le code de hachage:


   class A
   {
      public int Value;

      public override int GetHashCode()
      {
         return Value.GetHashCode(); //WRONG! Value is not constant during the instance's life time
      }
   }    

D'un autre côté, si la valeur ne peut pas être modifiée, il est correct d'utiliser:


   class A
   {
      public readonly int Value;

      public override int GetHashCode()
      {
         return Value.GetHashCode(); //OK  Value is read-only and can't be changed during the instance's life time
      }
   }
ILoveFortran
la source
3
Voté. C'est tout à fait faux. Même Microsoft déclare dans MSDN ( msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx ) que la valeur de GetHashCode DOIT changer lorsque l'état de l'objet change d'une manière qui peut affecter la valeur de retour d'un appel à Equals (), et même dans ses exemples, il montre également les implémentations GetHashCode qui dépendent entièrement de valeurs publiquement modifiables.
Sebastian PR Gingter
Sebastian, je ne suis pas d'accord: si vous ajoutez un objet à une collection qui utilise des codes de hachage, il sera placé dans un bac dépendant du code de hachage. Si vous modifiez maintenant le code de hachage, vous ne retrouverez plus l'objet dans la collection car le mauvais bac sera recherché. C'est, en fait, quelque chose qui s'est produit dans notre code et c'est pourquoi j'ai trouvé nécessaire de le souligner.
ILoveFortran
2
Sebastian, En outre, je ne peux pas voir une déclaration dans le lien ( msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx ) que GetHashCode () doit changer. Au contraire, elle ne doit PAS changer tant que Equals renvoie la même valeur pour le même argument: "La méthode GetHashCode pour un objet doit toujours 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 de la méthode Equals de l'objet. "Cette déclaration n'implique pas le contraire, qu'elle doit changer si la valeur de retour pour Equals change.
ILoveFortran
2
@Joao, vous confondez le côté client / consommateur du contrat avec le producteur / réalisateur. Je parle de la responsabilité de l'implémenteur, qui remplace GetHashCode (). Vous parlez du consommateur, celui qui utilise la valeur.
ILoveFortran
1
Incompréhension totale ... :) La vérité est que le code de hachage doit changer lorsque l'état de l'objet change à moins que l'état ne soit pas pertinent pour l'identité de l'objet. En outre, vous ne devez jamais utiliser un objet MUTABLE comme clé dans vos collections. Utilisez des objets en lecture seule à cet effet. GetHashCode, Equals ... et quelques autres méthodes dont je ne me souviens pas en ce moment ne devraient JAMAIS jeter.
darlove
0

Vous devez toujours garantir que si deux objets sont égaux, tels que définis par Equals (), ils doivent renvoyer le même code de hachage. Comme certains autres commentaires le disent, en théorie, cela n'est pas obligatoire si l'objet ne sera jamais utilisé dans un conteneur basé sur le hachage comme HashSet ou Dictionary. Je vous conseillerais de toujours suivre cette règle. La raison en est tout simplement parce qu'il est beaucoup trop facile pour quelqu'un de changer une collection d'un type à un autre avec la bonne intention d'améliorer réellement les performances ou simplement de transmettre la sémantique du code d'une meilleure manière.

Par exemple, supposons que nous conservions certains objets dans une liste. Quelque temps plus tard, quelqu'un se rend réellement compte qu'un HashSet est une bien meilleure alternative en raison des meilleures caractéristiques de recherche par exemple. C'est à ce moment que nous pouvons avoir des ennuis. La liste utiliserait en interne le comparateur d'égalité par défaut pour le type qui signifie égal dans votre cas tandis que HashSet utilise GetHashCode (). Si les deux se comportent différemment, votre programme aussi. Et gardez à l'esprit que ces problèmes ne sont pas les plus faciles à résoudre.

J'ai résumé ce comportement avec d'autres pièges GetHashCode () dans un article de blog où vous pouvez trouver d'autres exemples et explications.

Vasil Kosturski
la source
0

La .NET 4.7méthode préférée de remplacement GetHashCode()est indiquée ci-dessous. Si vous ciblez des versions plus anciennes de .NET, incluez le package de nuget System.ValueTuple .

// C# 7.0+
public override int GetHashCode() => (FooId, FooName).GetHashCode();

En termes de performances, cette méthode surclassera la plupart des implémentations de code de hachage composite . Le ValueTuple est structdonc il n'y aura pas de déchets, et l'algorithme sous-jacent est aussi rapide que possible.

l33t
la source
-1

Je crois comprendre que le GetHashCode () d'origine renvoie l'adresse mémoire de l'objet, il est donc essentiel de la remplacer si vous souhaitez comparer deux objets différents.

EDITED: C'était incorrect, la méthode GetHashCode () d'origine ne peut pas garantir l'égalité de 2 valeurs. Bien que les objets égaux renvoient le même code de hachage.

user2855602
la source
-6

Ci-dessous, l'utilisation de la réflexion me semble une meilleure option compte tenu des propriétés publiques, car avec cela, vous n'avez pas à vous soucier de l'ajout / de la suppression de propriétés (bien que ce ne soit pas un scénario si courant). J'ai également constaté que cela fonctionnait mieux (temps comparé avec le chronomètre Diagonistics).

    public int getHashCode()
    {
        PropertyInfo[] theProperties = this.GetType().GetProperties();
        int hash = 31;
        foreach (PropertyInfo info in theProperties)
        {
            if (info != null)
            {
                var value = info.GetValue(this,null);
                if(value != null)
                unchecked
                {
                    hash = 29 * hash ^ value.GetHashCode();
                }
            }
        }
        return hash;  
    }
Guanxi
la source
12
L'implémentation de GetHashCode () devrait être très légère. Je ne suis pas sûr que la réflexion soit perceptible avec StopWatch sur des milliers d'appels, mais c'est sûrement sur des millions (pensez à faire sortir un dictionnaire d'une liste).
bohdan_trotsenko