L'implémentation par défaut pour Object.GetHashCode ()

https://stackoverflow.com/questions/720177

23-08-2019
|

Question

Comment l'implémentation par défaut pour les travaux de GetHashCode()? Et il gère les structures ne, des classes, des tableaux, etc. efficace et assez bien?

Je suis en train de décider dans quels cas je devrais faire mes propres et dans ce cas, je peux compter sur toute sécurité l'implémentation par défaut de bien faire. Je ne veux pas réinventer la roue, si possible.

La solution

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

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

InternalGetHashCode est mis en correspondance avec un ObjectNative :: GetHashCode fonction 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

La mise en œuvre complète de GetHashCodeEx est assez grand, il est donc plus facile de relier juste le code source en C ++ .

Autres conseils

Pour une classe, les valeurs par défaut sont essentiellement référence à l'égalité, et qui est généralement très bien. Si vous écrivez une struct, il est plus fréquent de passer outre l'égalité (pas moins pour éviter la boxe), mais il est très rare que vous écrivez un struct quand même!

Lors de la substitution de l'égalité, vous devez toujours avoir un Equals() assorti et GetHashCode() (ie pour deux valeurs, si Equals() retourne true ils devez retourner le même code de hachage, mais l'inverse est non obligatoire) - et il est courant de fournir également == / !=operators, et souvent à mettre en œuvre IEquatable<T> trop

Pour générer le code de hachage, il est courant d'utiliser une somme pondérée, car cela permet d'éviter les collisions sur les valeurs paires - par exemple, pour une table de hachage de champ de base 2:

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;
}

Ceci a l'avantage que:

le hachage de {1,2} est pas le même que le hachage de {2,1}
le hachage de {1,1} est pas la même que la valeur de hachage du {2,2}

etc -. Qui peut être commun si juste en utilisant une somme non pondérée ou XOR (^), etc

La documentation de la méthode GetHashCode objet dit « l'implémentation par défaut de cette méthode ne doit pas être utilisé comme un identificateur d'objet unique à des fins de hachage. » et celui de .

Les types de données de base comme byte, short, int, long, char et string mettre en œuvre une bonne méthode GetHashCode. D'autres classes et structures, comme Point par exemple, mettre en œuvre une méthode de GetHashCode qui peuvent ou peuvent ne pas convenir à vos besoins spécifiques. Il vous suffit de l'essayer pour voir s'il est assez bon.

La documentation pour chaque classe ou une structure peut vous dire si elle remplace l'implémentation par défaut ou non. Si elle ne l'emporte pas, vous devez utiliser votre propre implémentation. Pour toutes les classes ou struct que vous créez où vous avez besoin d'utiliser la méthode de GetHashCode, vous devez faire votre propre mise en œuvre qui utilise les membres appropriés pour calculer le code de hachage.

Depuis que je ne pouvais pas trouver une réponse qui explique pourquoi nous devons passer outre GetHashCode et Equals pour struct personnalisés et pourquoi la mise en œuvre par défaut « ne risque pas d'être adapté pour être utilisé comme une clé dans une table de hachage », je vais laisser un lien vers ce billet de blog , ce qui explique pourquoi, avec un exemple réel cas de problème qui est arrivé.

Je recommande la lecture du message entier, mais voici un résumé (accent et apporté de précision).

La raison du hachage par défaut pour struct est lent et pas très bon:

La façon dont le CLR est conçu, chaque appel à un membre défini dans les types de System.ValueType ou System.Enum [peut] faire un allocation de boxe [...]

Un implémenteur d'une fonction de hachage fait face à un dilemme: faire une bonne répartition de la fonction de hachage ou pour le rendre rapide. Dans certains cas, il est possible de les réaliser à la fois, mais il est difficile à faire génériquement ValueType.GetHashCode.

La fonction de hachage canonique d'un struct « combine » codes de hachage de tous les champs. Mais la seule façon d'obtenir un code de hachage d'un champ dans une méthode de ValueType est réflexion utilisation . Ainsi, les auteurs CLR ont décidé d'échanger la vitesse sur la distribution et la version par défaut GetHashCode retourne juste un code de hachage d'un premier champ non nul et « munges » avec un identifiant de type [...] Ceci est un comportement raisonnable à moins que ce n'est pas. Par exemple, si vous êtes assez malchanceux et le premier champ de votre struct a la même valeur pour la plupart des cas, alors une fonction de hachage fournira le même résultat tout le temps. Et, comme vous pouvez l'imaginer, cela entraînera un impact drastique de la performance si ces instances sont stockées dans un ensemble de hachage ou une table de hachage.

[...] mise en œuvre par réflexion est lent . Très lent.

[...] Les deux ValueType.Equals et ValueType.GetHashCode ont une optimisation spéciale. Si un type ne pas « pointeurs » et est correctement emballé [...] alors des versions plus optimales sont utilisées: itère GetHashCode sur un des blocs d'instance et d'XORs de 4 octets et la méthode de Equals compare deux instances à l'aide memcmp. [...] Mais l'optimisation est très délicat. Tout d'abord, il est difficile de savoir quand l'optimisation est activée [...] Deuxièmement, une comparaison de la mémoire ne sera pas nécessairement vous donner les bons résultats . Voici un exemple simple:. [...] -0.0 et +0.0 sont égaux mais ont des représentations binaires

AUTHENTIQUE monde décrit dans le message:

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 qui contenait une struct personnalisée avec la mise en œuvre de l'égalité par défaut. Malheureusement, la struct avait un premier champ optionnel qui était égal à presque toujours [chaîne vide] . La performance était OK jusqu'à ce que le nombre d'éléments dans l'ensemble a augmenté de manière significative un problème entraînant des performances réelles, en minutes pour initialiser une collection avec des dizaines de milliers d'articles.

Alors, pour répondre à la question « dans quels cas je devrais faire mes propres et dans ce cas, je peux en toute sécurité compter sur l'implémentation par défaut », au moins dans le cas de struct , vous devez remplacer Equals et GetHashCode chaque fois que votre struct personnalisé peut être utilisé comme une clé dans une table de hachage ou Dictionary.
Je recommande également la mise en œuvre IEquatable<T> dans ce cas, pour éviter la boxe.

Comme les autres réponses ont dit, si vous écrivez un class , le hachage par défaut en utilisant l'égalité de référence est généralement très bien, donc je ne dérangerait pas dans ce cas, à moins que vous devez passer outre Equals (alors que vous auriez à passer outre GetHashCode en conséquence).

D'une manière générale, si vous êtes Equals majeur, vous voulez remplacer GetHashCode. La raison en est que les deux sont utilisés pour comparer l'égalité de votre classe / struct.

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

if (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. La hashcode générée par votre classe doit toujours être la même pour un cours donnent 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 doit être calculée une fois par vie de l'objet, mais je ne suis pas d'accord avec cela (et je suis probablement mal).

En utilisant l'implémentation par défaut fourni par objet, sauf si vous avez la même référence à l'un de vos classes, ils ne seront pas égaux entre eux. En redéfinissant Equals et GetHashCode, vous pouvez signaler l'égalité fondée sur des valeurs internes plutôt que la référence des objets.

Si vous êtes juste face à Poços vous pouvez utiliser cet utilitaire pour vous simplifier la vie un peu:

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;
    }
}

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow