Implémentation par défaut pour Object.GetHashCode ()

162

Comment l'implémentation par défaut pour GetHashCode() ? Et gère-t-il suffisamment et efficacement les structures, les classes, les tableaux, etc.?

J'essaie de décider dans quels cas je dois emballer le mien et dans quels cas je peux compter en toute sécurité sur l'implémentation par défaut pour bien faire. Je ne veux pas réinventer la roue, si possible.

Fung
la source
Jetez un œil au commentaire que j'ai laissé sur l'article: stackoverflow.com/questions/763731/gethashcode-extension-method
Paul Westcott
34
A part: vous pouvez obtenir le hashcode par défaut (même s'il GetHashCode()a été remplacé) en utilisantSystem.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(obj)
Marc Gravell
@MarcGravell merci pour cette contribution, je cherchais exactement cette réponse.
Andrew Savinykh
@MarcGravell Mais comment ferais-je cela avec une autre méthode?
Tomáš Zato - Réintégrer Monica

Réponses:

86
namespace System {
    public class Object {
        [MethodImpl(MethodImplOptions.InternalCall)]
        internal static extern int InternalGetHashCode(object obj);

        public virtual int GetHashCode() {
            return InternalGetHashCode(this);
        }
    }
}

InternalGetHashCode est mappé à une fonction ObjectNative :: GetHashCode dans le CLR, qui ressemble à ceci:

FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {  
    CONTRACTL  
    {  
        THROWS;  
        DISABLED(GC_NOTRIGGER);  
        INJECT_FAULT(FCThrow(kOutOfMemoryException););  
        MODE_COOPERATIVE;  
        SO_TOLERANT;  
    }  
    CONTRACTL_END;  

    VALIDATEOBJECTREF(obj);  

    DWORD idx = 0;  

    if (obj == 0)  
        return 0;  

    OBJECTREF objRef(obj);  

    HELPER_METHOD_FRAME_BEGIN_RET_1(objRef);        // Set up a frame  

    idx = GetHashCodeEx(OBJECTREFToObject(objRef));  

    HELPER_METHOD_FRAME_END();  

    return idx;  
}  
FCIMPLEND

L'implémentation complète de GetHashCodeEx est assez volumineuse, il est donc plus facile de simplement créer un lien vers le code source C ++ .

David Brown
la source
5
Ce devis de documentation doit provenir d'une version très ancienne. Ce n'est plus écrit comme ça dans les articles MSDN actuels, probablement parce que c'est tout à fait faux.
Hans Passant
4
Ils ont changé le libellé, oui, mais il dit toujours fondamentalement la même chose: "Par conséquent, l'implémentation par défaut de cette méthode ne doit pas être utilisée comme un identifiant d'objet unique à des fins de hachage."
David Brown
7
Pourquoi la documentation prétend-elle que l'implémentation n'est pas particulièrement utile pour le hachage? Si un objet est égal à lui-même et à rien d'autre, toute méthode de code de hachage qui retournera toujours la même valeur pour une instance d'objet donnée, et retournera généralement des valeurs différentes pour différentes instances, quel est le problème?
supercat le
3
@ ta.speot.is: Si vous voulez déterminer si une instance particulière a déjà été ajoutée dans un dictionnaire, l'égalité des références est parfaite. Avec les chaînes, comme vous le notez, on est généralement plus intéressé à savoir si une chaîne contenant la même séquence de caractères a déjà été ajoutée. C'est pourquoi les stringsubstitutions GetHashCode. D'autre part, supposons que vous souhaitiez conserver un décompte du nombre de fois que les différents contrôles traitent les Paintévénements. Vous pouvez utiliser un Dictionary<Object, int[]>(chaque int[]stocké contiendrait exactement un élément).
supercat
6
@ It'sNotALie. Alors merci Archive.org pour avoir une copie ;-)
RobIII
88

Pour une classe, les valeurs par défaut sont essentiellement l'égalité de référence, et c'est généralement bien. Si vous écrivez une structure, il est plus courant de surcharger l'égalité (notamment pour éviter la boxe), mais il est très rare d'écrire une structure de toute façon!

Lorsque vous remplacez l'égalité, vous devriez toujours avoir une correspondance Equals()et GetHashCode()(c'est-à-dire pour deux valeurs, si Equals()retourne true, elles doivent retourner le même code de hachage, mais l'inverse n'est pas obligatoire) - et il est courant de fournir également des opérateurs ==/ !=, et souvent de mettre en œuvre IEquatable<T>aussi.

Pour générer le code de hachage, il est courant d'utiliser une somme pondérée, car cela évite les collisions sur des valeurs appariées - par exemple, pour un hachage de base à 2 champs:

unchecked // disable overflow, for the unlikely possibility that you
{         // are compiling with overflow-checking enabled
    int hash = 27;
    hash = (13 * hash) + field1.GetHashCode();
    hash = (13 * hash) + field2.GetHashCode();
    return hash;
}

Cela présente l'avantage que:

  • le hachage de {1,2} n'est pas le même que le hachage de {2,1}
  • le hachage de {1,1} n'est pas le même que le hachage de {2,2}

etc - ce qui peut être courant si vous utilisez simplement une somme non pondérée, ou xor ( ^), etc.

Marc Gravell
la source
Excellent point sur les avantages d'un algorithme à somme factorisée; quelque chose que je n'avais pas réalisé auparavant!
Échec du
La somme pondérée (comme indiqué ci-dessus) ne causera-t-elle pas occasionnellement des exceptions de dépassement de capacité?
sinelaw
4
@sinelaw oui, cela devrait être exécuté unchecked. Heureusement, uncheckedc'est la valeur par défaut en C #, mais il serait préférable de la rendre explicite; édité
Marc Gravell
7

La documentation de la GetHashCodeméthode pour Object indique que "l'implémentation par défaut de cette méthode ne doit pas être utilisée comme identificateur d'objet unique à des fins de hachage". et celui de ValueType indique "Si vous appelez la méthode GetHashCode du type dérivé, la valeur de retour n'est probablement pas adaptée à une utilisation comme clé dans une table de hachage.".

Les types de données de base comme byte, short, int, long, charet stringmettre en œuvre une bonne méthode GetHashCode. Certaines autres classes et structures, comme Pointpar exemple, implémentent unGetHashCode méthode qui peut ou non convenir à vos besoins spécifiques. Il vous suffit de l'essayer pour voir si c'est assez bon.

La documentation de chaque classe ou structure peut vous dire si elle remplace ou non l'implémentation par défaut. S'il ne le remplace pas, vous devez utiliser votre propre implémentation. Pour toutes les classes ou structures que vous créez vous-même où vous devez utiliser la GetHashCodeméthode, vous devez créer votre propre implémentation qui utilise les membres appropriés pour calculer le code de hachage.

Guffa
la source
2
Je ne suis pas d'accord pour dire que vous devriez systématiquement ajouter votre propre implémentation. Simplement, la grande majorité des classes (en particulier) ne seront jamais testées pour l'égalité - ou là où elles sont, l'égalité de référence intégrée est très bien. Dans l'occasion (déjà rare) d'écrire une structure, ce serait plus courant, c'est vrai.
Marc Gravell
@Marc Gravel: Ce n'est bien sûr pas ce que je voulais dire. Je vais ajuster le dernier paragraphe. :)
Guffa
Les types de données de base n'implémentent pas une bonne méthode GetHashCode, du moins dans mon cas. Par exemple, GetHashCode pour int renvoie le nombre lui-même: (123) .GetHashCode () renvoie 123.
fdermishin
5
@ user502144 Et quel est le problème avec ça? C'est un identifiant unique parfait, facile à calculer, sans faux positifs sur l'égalité ...
Richard Rast
@Richard Rast: C'est OK sauf que les clés peuvent être mal distribuées lorsqu'elles sont utilisées dans une table de hachage. Jetez un oeil à cette réponse: stackoverflow.com/a/1388329/502144
fdermishin
5

Comme je n'ai pas trouvé de réponse expliquant pourquoi nous devrions remplacer GetHashCodeet Equalspour les structures personnalisées et pourquoi l'implémentation par défaut "n'est pas susceptible d'être utilisée comme clé dans une table de hachage", je vais laisser un lien vers ce blog post , ce qui explique pourquoi avec un exemple concret d'un problème survenu.

Je recommande de lire l'intégralité du message, mais voici un résumé (soulignement et clarifications ajoutés).

Raison pour laquelle le hachage par défaut pour les structures est lent et pas très bon:

La façon dont le CLR est conçu, chaque appel à un membre défini dans System.ValueTypeou System.Enumtypes [peut] provoquer une allocation de boxe [...]

Un réalisateur d'une fonction de hachage est confronté à un dilemme: faire une bonne distribution de la fonction de hachage ou la rendre rapide. Dans certains cas, il est possible de les atteindre tous les deux, mais il est difficile de le faire de manière générique dansValueType.GetHashCode .

La fonction de hachage canonique d'une structure "combine" les codes de hachage de tous les champs. Mais le seul moyen d'obtenir un code de hachage d'un champ dans une ValueTypeméthode est d' utiliser la réflexion . Ainsi, les auteurs du CLR ont décidé d'échanger de la vitesse sur la distribution et la GetHashCodeversion par défaut renvoie simplement un code de hachage d'un premier champ non nul et le «munit» d'un identifiant de type [...] C'est un comportement raisonnable sauf si ce n'est pas le cas . Par exemple, si vous êtes assez malchanceux et que le premier champ de votre structure a la même valeur pour la plupart des instances, alors une fonction de hachage fournira le même résultat tout le temps. Et, comme vous pouvez l'imaginer, cela aura un impact considérable sur les performances si ces instances sont stockées dans un jeu de hachage ou une table de hachage.

[...] La mise en œuvre basée sur la réflexion est lente . Très lent.

[...] Les deux ValueType.Equalset ValueType.GetHashCodeont une optimisation spéciale. Si un type n'a pas de "pointeurs" et est correctement compressé [...] alors des versions plus optimales sont utilisées: GetHashCodeitère sur une instance et XORs blocs de 4 octets et la Equalsméthode compare deux instances en utilisant memcmp. [...] Mais l'optimisation est très délicate. Premièrement, il est difficile de savoir quand l'optimisation est activée [...] Deuxièmement, une comparaison de mémoire ne vous donnera pas forcément les bons résultats . Voici un exemple simple: [...] -0.0et +0.0sont égaux mais ont des représentations binaires différentes.

Problème du monde réel décrit dans l'article:

private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonly struct ErrorLocation
{
    // Empty almost all the time
    public string OptionalDescription { get; }
    public string Path { get; }
    public int Position { get; }
}

Nous avons utilisé un tuple contenant une structure personnalisée avec une implémentation d'égalité par défaut. Et malheureusement, la structure avait un premier champ facultatif qui était presque toujours égal à [chaîne vide] . Les performances étaient correctes jusqu'à ce que le nombre d'éléments de l'ensemble augmente de manière significative, provoquant un réel problème de performances, prenant quelques minutes pour initialiser une collection avec des dizaines de milliers d'éléments.

Donc, pour répondre à la question "dans quels cas je devrais emballer le mien et dans quels cas je peux compter en toute sécurité sur l'implémentation par défaut", au moins dans le cas des structures , vous devez surcharger Equalset GetHashCodechaque fois que votre structure personnalisée peut être utilisée comme un entrez une table de hachage ou Dictionary.
Je recommanderais également la mise IEquatable<T>en œuvre dans ce cas, pour éviter la boxe.

Comme le disent les autres réponses, si vous écrivez une classe , le hachage par défaut utilisant l'égalité de référence est généralement correct, donc je ne me dérangerais pas dans ce cas, à moins que vous n'ayez besoin de remplacer Equals(alors vous devrez remplacer en GetHashCodeconséquence).

geekley
la source
1

De manière générale, si vous remplacez Equals, vous souhaitez remplacer GetHashCode. La raison en est que les deux sont utilisés pour comparer l'égalité de votre classe / structure.

Equals est utilisé lors de la vérification de Foo A, B;

si (A == B)

Puisque nous savons que le pointeur n'est pas susceptible de correspondre, nous pouvons comparer les membres internes.

Equals(obj o)
{
    if (o == null) return false;
    MyType Foo = o as MyType;
    if (Foo == null) return false;
    if (Foo.Prop1 != this.Prop1) return false;

    return Foo.Prop2 == this.Prop2;
}

GetHashCode est généralement utilisé par les tables de hachage. Le hashcode généré par votre classe doit toujours être le même pour une classe donnant l'état.

Je fais généralement,

GetHashCode()
{
    int HashCode = this.GetType().ToString().GetHashCode();
    HashCode ^= this.Prop1.GetHashCode();
    etc.

    return HashCode;
}

Certains diront que le hashcode ne devrait être calculé qu'une fois par durée de vie d'objet, mais je ne suis pas d'accord avec cela (et je me trompe probablement).

En utilisant l'implémentation par défaut fournie par object, à moins que vous n'ayez la même référence à l'une de vos classes, elles ne seront pas égales l'une à l'autre. En remplaçant Equals et GetHashCode, vous pouvez signaler l'égalité basée sur des valeurs internes plutôt que sur la référence des objets.

Bennett Dill
la source
2
L'approche ^ = n'est pas une approche particulièrement bonne pour générer un hachage - elle a tendance à conduire à beaucoup de collisions courantes / prévisibles - par exemple si Prop1 = Prop2 = 3.
Marc Gravell
Si les valeurs sont identiques, je ne vois pas de problème avec la collision car les objets sont égaux. Le 13 * Hash + NewHash semble cependant intéressant.
Bennett Dill le
2
Ben: essayez-le pour Obj1 {Prop1 = 12, Prop2 = 12} et Obj2 {Prop1 = 13, Prop2 = 13}
Tomáš Kafka
0

Si vous avez uniquement affaire à des POCO, vous pouvez utiliser cet utilitaire pour vous simplifier quelque peu la vie:

var hash = HashCodeUtil.GetHashCode(
           poco.Field1,
           poco.Field2,
           ...,
           poco.FieldN);

...

public static class HashCodeUtil
{
    public static int GetHashCode(params object[] objects)
    {
        int hash = 13;

        foreach (var obj in objects)
        {
            hash = (hash * 7) + (!ReferenceEquals(null, obj) ? obj.GetHashCode() : 0);
        }

        return hash;
    }
}
Daniel Marshall
la source