2010-11-04 27 views
110

J'essaie de comprendre le rôle de la méthode GetHashCode de l'interface IEqualityComparer.Quel est le rôle de GetHashCode dans IEqualityComparer <T> dans .NET?

L'exemple suivant est tiré de MSDN:

using System; 
using System.Collections.Generic; 
class Example { 
    static void Main() { 
     try { 

      BoxEqualityComparer boxEqC = new BoxEqualityComparer(); 

      Dictionary<Box, String> boxes = new Dictionary<Box, 
               string>(boxEqC); 

      Box redBox = new Box(4, 3, 4); 
      Box blueBox = new Box(4, 3, 4); 

      boxes.Add(redBox, "red"); 
      boxes.Add(blueBox, "blue"); 

      Console.WriteLine(redBox.GetHashCode()); 
      Console.WriteLine(blueBox.GetHashCode()); 
     } 
     catch (ArgumentException argEx) { 

      Console.WriteLine(argEx.Message); 
     } 
    } 
} 

public class Box { 
    public Box(int h, int l, int w) { 
     this.Height = h; 
     this.Length = l; 
     this.Width = w; 
    } 
    public int Height { get; set; } 
    public int Length { get; set; } 
    public int Width { get; set; } 
} 

class BoxEqualityComparer : IEqualityComparer<Box> { 

    public bool Equals(Box b1, Box b2) { 
     if (b1.Height == b2.Height & b1.Length == b2.Length 
          & b1.Width == b2.Width) { 
      return true; 
     } 
     else { 
      return false; 
     } 
    } 

    public int GetHashCode(Box bx) { 
     int hCode = bx.Height^bx.Length^bx.Width; 
     return hCode.GetHashCode(); 
    } 
} 

devrait-il pas Equals implémentation de la méthode suffisante pour comparer deux objets Box? C'est là que nous disons au framework la règle utilisée pour comparer les objets. Pourquoi le GetHashCode est-il nécessaire?

Merci.

Lucian

+0

Lisez ce qui suit: http://en.wikipedia.org/wiki/Hash_table pour voir si vous comprenez mieux le but de GetHashCode. – spender

+1

Voir cette bonne réponse: http://stackoverflow.com/a/3719802/136967 – Mikhail

Répondre

168

Un peu d'histoire ... première

Chaque objet .NET est une méthode equals et une méthode GetHashCode.

La méthode Equals est utilisée pour comparer un objet avec un autre objet - pour voir si les deux objets sont équivalents.

La méthode GetHashCode génère une représentation entière de 32 bits de l'objet. Comme il n'y a pas de limite à la quantité d'informations qu'un objet peut contenir, certains codes de hachage sont partagés par plusieurs objets - donc le code de hachage n'est pas nécessairement unique. Un dictionnaire est une structure de données vraiment cool qui échange une empreinte mémoire plus élevée en échange de coûts (plus ou moins) constants pour les opérations d'ajout/suppression/réception. C'est un mauvais choix pour itérater si. En interne, un dictionnaire contient un tableau de compartiments dans lequel les valeurs peuvent être stockées. Lorsque vous ajoutez une clé et une valeur à un dictionnaire, la méthode GetHashCode est appelée sur la clé. Le hashcode renvoyé est utilisé pour déterminer l'index du compartiment dans lequel la paire clé/valeur doit être stockée. Lorsque vous voulez accéder à la valeur, vous passez à nouveau la clé. La méthode GetHashCode est appelée sur la clé et le compartiment contenant la valeur est situé.

Lorsqu'un IEqualityComparer est transmis au constructeur d'un dictionnaire, les méthodes IEqualityComparer.Equals et IEqualityComparer.GetHashCode sont utilisées à la place des méthodes sur les objets Key.

Maintenant, pour expliquer pourquoi les deux méthodes sont nécessaires, considérez cet exemple:

BoxEqualityComparer boxEqC = new BoxEqualityComparer(); 

Dictionary<Box, String> boxes = new Dictionary<Box, string>(boxEqC); 

Box redBox = new Box(100, 100, 25); 
Box blueBox = new Box(1000, 1000, 25); 

boxes.Add(redBox, "red"); 
boxes.Add(blueBox, "blue"); 

En utilisant la méthode BoxEqualityComparer.GetHashCode dans votre exemple, ces deux boîtes ont la même hashcode - 100^100^25 = 1000^1000^25 = 25 - même s'ils ne sont clairement pas le même objet. La raison pour laquelle ils sont le même hashcode dans ce cas est parce que vous utilisez l'opérateur^(OU exclusif au niveau du bit) de sorte que 100^100 annule la sortie de zéro, tout comme 1000^1000. Lorsque deux objets différents ont la même clé, nous appelons cela une collision.

Lorsque nous ajoutons deux paires clé/valeur avec le même code à un dictionnaire, elles sont toutes deux stockées dans le même compartiment. Ainsi, lorsque nous voulons récupérer une valeur, la méthode GetHashCode est appelée sur notre clé pour localiser le compartiment.Comme il existe plusieurs valeurs dans le compartiment, le dictionnaire itère sur toutes les paires clé/valeur du compartiment appelant la méthode Equals sur les clés pour trouver la paire correcte.

Dans l'exemple que vous avez publié, les deux zones sont équivalentes, de sorte que la méthode Equals renvoie true. Dans ce cas, le dictionnaire a deux clés identiques, donc il lance une exception.

TLDR

Donc, en résumé, la méthode GetHashCode est utilisée pour générer une adresse où l'objet est stocké. Donc, un dictionnaire n'a pas à le chercher. Il calcule simplement le code et saute à cet endroit. La méthode Equals est un meilleur test d'égalité, mais ne peut pas être utilisée pour mapper un objet dans un espace d'adressage.

espoir qui aide

+4

Bonne réponse, merci! – Lucian

+2

Grande explication sur les internes du dictionnaire .. – nawfal

+4

Pour ceux qui se demandent ce qu'est le^-operateur, il s'agit de l'opérateur OR exclusif au niveau du bit, voir http://msdn.microsoft.com/fr-fr/library/zkacc7k1.aspx. –

7

GetHashCode est utilisé dans colections dictionnaire et il crée hachage pour stocker des objets en elle. Voici un bel article pourquoi et comment utiliser IEqualtyComparer et GetHashCodehttp://dotnetperls.com/iequalitycomparer

+4

Plus: Si vous avez besoin de comparer ** Equals ** serait enouf, mais quand vous avez besoin d'obtenir un élément du dictionnaire, c'est plus facile de le faire par hash, pas en utilisant ** Equals **. – Ash

2

Alors qu'il serait possible pour un Dictionary<TKey,TValue> d'avoir son GetValue et des méthodes similaires appellent Equals sur chaque clé stockée unique pour voir si elle correspond à celui recherché, qui serait très lent. Au lieu de cela, comme de nombreuses collections basées sur le hachage, elle s'appuie sur GetHashCode pour exclure rapidement la plupart des valeurs non correspondantes. Si l'appel GetHashCode sur un élément recherché donne 42, et une collection a 53 917 éléments, mais en appelant GetHashCode sur 53 914 des éléments a donné une valeur autre que 42, alors seulement 3 éléments devront être comparés à ceux recherchés. L'autre 53,914 peut être ignoré en toute sécurité.

La raison pour laquelle un GetHashCode est inclus dans un IEqualityComparer<T> est de permettre la possibilité que le consommateur d'un dictionnaire pourrait vouloir considérer comme des objets égaux qui seraient normalement pas se considérer comme égaux. L'exemple le plus courant serait un appelant qui veut utiliser des chaînes comme clés mais qui utilise des comparaisons insensibles à la casse. Afin de rendre ce travail efficace, le dictionnaire devra avoir une forme de fonction de hachage qui donnera la même valeur pour "Fox" et "FOX", mais j'espère donner quelque chose d'autre pour "box" ou "zebra". Puisque la méthode GetHashCode intégrée dans String ne fonctionne pas de cette façon, le dictionnaire devra obtenir une telle méthode d'ailleurs, et IEqualityComparer<T> est l'endroit le plus logique puisque le besoin d'un tel code de hachage serait très fortement associé à un Equals méthode qui considère "Fox" et "FOX" identiques les uns aux autres, mais pas à "box" ou "zebra".