Conseils généraux et instructions sur la manière de remplacer correctement object.GetHashCode ()

Question

Selon MSDN, une fonction de hachage doit avoir les propriétés suivantes:

1. Si deux objets sont considérées comme égales, la méthode GetHashCode pour chaque objet doit retourner la même valeur. Toutefois, si deux objets ne sont pas considérées comme égales, la GetHashCode méthodes pour les deux objets n'ont pas à renvoyer des valeurs différentes.

2. La méthode GetHashCode pour un objet doit constamment revenir par 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 l'objet de la méthode Equals. Notez que ceci n'est vrai que pour l'exécution d'une application, et qu'un autre code de hachage peut être retourné si l'application est exécutée à nouveau.

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

---

Je continue de trouver moi-même dans le scénario suivant: j'ai créé une classe, mis en oeuvre IEquatable<T> et remplacé object.Equals(object). MSDN stipule que:

Types de remplacer Égale devez également remplacer GetHashCode ; sinon, la table de hachage peut ne pas fonctionner correctement.

Et puis il s'arrête généralement un peu pour moi. Parce que, comment avez-vous correctement remplacer object.GetHashCode()? Jamais vraiment savoir par où commencer, et il semble y avoir beaucoup de pièges.

Ici, à StackOverflow, il existe assez peu de questions liées à la GetHashCode primordial, mais la plupart d'entre eux semble être tout à fait particulier des cas et des questions spécifiques. Donc, c'est pourquoi j'aimerais obtenir une bonne compilation ici. Une vue d'ensemble des conseils généraux et des lignes directrices. Quoi faire, quoi ne pas faire, les pièges courants, par où commencer, etc.

Je voudrais qu'il soit surtout C#, mais je pense que cela fonctionnera sorte de la même manière pour les autres .NET langues(?).

---

Je pense que peut-être la meilleure façon est de créer une seule réponse par question rapide et de réponse à court d'abord (près de one-liner si possible), alors peut-être certains plus d'informations et à la fin avec des questions, des discussions, des articles de blog, etc., si il y a de tout. Je peux alors créer un post que l'on a accepté la réponse (pour l'obtenir sur le dessus) avec une "table des matières". Essayez de le garder court et concis. Et de ne pas les lier à d'autres questions et messages de blog. Essayez de prendre de l'essence et puis plutôt le lien vers la source (surtout depuis la source pourrait disparaître. Aussi, essayez de la modifier et d'améliorer les réponses au lieu de créé beaucoup de produits très similaires.

Je ne suis pas un très bon rédacteur technique, mais je vais au moins essayer de format de réponses afin qu'ils se ressemblent, créer la table des matières, etc. Je vais également essayer de rechercher certaines des questions liées ici à de SORTE que les réponses des parties de ces et peut-être tirer l'essence même de celles que je peux gérer. Mais depuis que je ne suis pas très stable sur ce sujet, je vais essayer de rester à l'écart pour la plupart :p

Answer 1

Table des matières

• Quand dois-je remplacer object.GetHashCode?

• Pourquoi dois-je remplacer l'objet.GetHashCode()?

• Quels sont ces nombres magiques vu dans GetHashCode implémentations?

---

Les choses que je voudrais être couverts, mais n'ont pas encore été:

• Comment créer l'entier (Comment "convertir" un objet dans un int n'était pas très évident pour moi de toute façon).
• Quels champs de la base le code de hachage sur.
  • Si elle ne devrait être sur immuable champs, que s'il y a seulement mutable ceux?
• Comment générer une bonne distribution aléatoire. MSDN (Propriété #3)
  • Une partie de cela, semble choisir une bonne magie nombre premier (ont vu les 17, 23 et 397 été utilisé), mais comment la choisir, et c'est pour quoi exactement?
• Comment assurez-vous que le code de hachage reste le même à tous par le biais de la durée de vie des objets. MSDN (Propriété #2)
  • Surtout quand l'égalité est basée sur les champs mutables. MSDN (Propriété #1)
• La façon de traiter avec des champs qui sont des types complexes (pas parmi les construite en C# types).
  • Les objets complexes et les structures, les tableaux, les collections, les listes, les dictionnaires, les types génériques, etc.
  • Par exemple, même si la liste ou un dictionnaire peut être en lecture seule, cela ne signifie pas que le contenu de ce sont.
• La façon de traiter avec les classes héritées.
  • Si vous incorporer base.GetHashCode() dans votre code de hachage?
• Pourriez-vous techniquement juste être paresseux et retourner la valeur 0? Lourdement pause MSDN directive numéro 3, mais aurait au moins assurez-vous que #1 et #2 ont toujours été vrai :P
• Commune de pièges.

Answer 2

Quels sont ces nombres magiques souvent vu dans GetHashCode implémentations?

Ils sont des nombres premiers. Les nombres premiers sont utilisés pour créer des codes de hachage parce que le premier numéro de maximiser l'utilisation du code de hachage de l'espace.

Plus précisément, commencer avec le petit nombre premier 3, et ne considèrent que la faible nybbles des résultats:

• 3 * 1 = 3 = 3(mod 8) = 0011
• 3 * 2 = 6 = 6(mod 8) = 1010
• 3 * 3 = 9 = 1(mod 8) = 0001
• 3 * 4 = 12 = 4(mod 8) = 1000
• 3 * 5 = 15 = 7(mod 8) = 1111
• 3 * 6 = 18 = 2(mod 8) = 0010
• 3 * 7 = 21 = 5(mod 8) = 1001
• 3 * 8 = 24 = 0(mod 8) = 0000
• 3 * 9 = 27 = 3(mod 8) = 0011

Et nous de recommencer. Mais vous remarquerez que les multiples de notre premier produit de chaque permutation possible de bits dans notre nybble avant de commencer à répéter. On peut obtenir le même effet avec tout nombre premier et un nombre quelconque de bits, ce qui rend les nombres premiers optimale pour générer de la quasi-aléatoire des codes de hachage. La raison nous avons l'habitude de voir de plus grands nombres premiers au lieu de petits nombres premiers comme 3 dans l'exemple ci-dessus est que, pour un plus grand nombre de bits dans notre code de hachage, les résultats obtenus à l'aide d'une petite prime ne sont même pas des pseudo-aléatoire - ils sont tout simplement une suite croissante jusqu'à un dépassement de capacité est rencontré. Pour optimiser l'aléatoire, un nombre premier qui en résulte dans le débordement de la assez pour de petits coefficients doit être utilisé, sauf si vous pouvez garantir que votre coefficients ne sera pas petite.

Liens connexes:

• Pourquoi est - ‘397' utilisé pour ReSharper GetHashCode remplacer?

Answer 3

Pourquoi dois-je remplacer object.GetHashCode()?

Substitution de cette méthode est importante parce que la propriété suivante doit toujours rester vrai:

Si deux objets sont considérées comme égales, la méthode GetHashCode pour chaque objet doit retourner la même valeur.

La raison, comme l'a déclaré JaredPar dans un billet de blog sur la mise en œuvre de l'égalité, c'est que

De nombreuses classes utilisent le code de hachage de classer un objet. En particulier, les tables de hachage et les dictionnaires ont tendance à placer des objets dans des seaux en fonction de leur code de hachage. Lors de la vérification si un objet est déjà dans la table de hachage, il va d'abord chercher dans un seau. Si deux objets sont égaux, mais ont différents codes de hachage ils peuvent être mis dans des compartiments différents et que le dictionnaire ne parviendrait pas à la recherche de l'objet.

Liens connexes:

• Dois-je remplacer GetHashCode et Égaux dans de nouvelles Classes?
• Dois-je remplacer GetHashCode() sur les types de référence?
• Remplacer d'égal à Égal et GetHashCode Question
• Pourquoi est-il important de remplacer GetHashCode lorsque la méthode Equals est surchargé en C#?
• Correctement mise en Œuvre de l'Égalité dans VB

Answer 4

Vous devez remplacer chaque fois que vous avez une mesure intéressante de l'égalité pour les objets de ce type (c'est à dire que vous remplacez est Égal). Si vous saviez l'objet n'allait pas être haché pour une raison quelconque, vous pourriez le laisser, mais il est peu probable que vous pouvait le savoir à l'avance.

Le hachage doit être fondée uniquement sur les propriétés de l'objet qui sont utilisés pour définir l'égalité depuis deux objets qui sont considérés comme égaux doivent avoir le même code de hachage. En général, vous le feriez habituellement quelque chose comme:

public override int GetHashCode()
{
    int mc = //magic constant, usually some prime
    return mc * prop1.GetHashCode() * prop2.GetHashCode * ... * propN.GetHashCode();
}

J'ai l'habitude de supposer multipliant les valeurs de produire une distribution assez uniforme, en supposant que chaque propriété hashcode de la fonction fait la même chose, même si c'est peut-être faux. En utilisant cette méthode, si les objets de l'égalité-la définition des propriétés de changement, puis le code de hachage est également susceptible de changer, ce qui est acceptable compte tenu de la définition n ° 2 dans votre question. Il traite également de tous les types de manière uniforme.

Vous pouviez retourner la même valeur pour tous les cas, bien que cela fera toute les algorithmes qui utilisent le hachage (comme dictionarys) très lent, essentiellement toutes les instances seront hachées pour le même seau et de recherche deviendra alors O(n) à la place de l'O(1). Bien sûr, cela vous fait oublier tous les avantages de l'utilisation de telles structures pour la recherche.

Answer 5

A) Vous devez remplacer à la fois Égaux et GetHashCode si vous voulez employer la valeur de l'égalité au lieu de la valeur par défaut référence d'égalité. Par la suite, deux références de l'objet sont considérées comme égales si elles se réfèrent à la même instance d'objet. Avec le premier, ils sont considérées comme égales si leur valeur est la même, même si elles se réfèrent à des objets différents. Par exemple, vous avez probablement besoin d'utiliser la valeur de l'égalité pour la Date, de l'Argent, et des objets Point.

B) afin de mettre En valeur l'égalité, vous devez remplacer d'égal à Égal et GetHashCode. Les deux devraient dépendre sur les champs de l'objet qui contient la valeur. Par exemple, la Date.Année, La Date.Le mois et la Date.De la journée; ou de l'Argent.De la monnaie et de l'Argent.Montant; ou le Point.X, Point.Y et le Point.Z. Vous devriez également considérer primordial de l'opérateur ==, opérateur !=, l'opérateur < et operator >.

C) Le hashcode n'avez pas à rester constant tout au travers de la durée de vie des objets. Cependant, il doit rester immuable, alors qu'il participe à ce titre à la clé dans une table de hachage. À partir de MSDN doco pour le Dictionnaire: "tant Qu'un objet est utilisé comme une clé dans le Dictionnaire<(Of <(TKey, TValue>)>), il ne doit pas changer d'une manière qui affecte sa valeur de hachage." Si vous devez modifier la valeur d'une clé de supprimer une entrée dans le dictionnaire, changer la valeur de la clé, et à remplacer l'entrée.

D) de l'OMI, vous permettra de simplifier votre vie, si vos objets de valeur sont eux-mêmes immuables.