Quel est le rôle de GetHashCode dans le IEqualityComparer dans .NET?

Question

Je suis en train de comprendre le rôle de la méthode GetHashCode de l'interface IEqualityComparer.

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

ne doit pas Egaux implémentation de la méthode soit suffisant pour comparer deux objets Box? C'est là que nous disons le cadre de la règle utilisée pour comparer les objets. Pourquoi le GetHashCode nécessaire?

Merci.

Lucian

Answer 1

Un peu d'arrière-plan d'abord ...

Chaque objet dans .NET a un Égal procédé et une méthode GetHashCode.

Le Égal procédé est utilisé 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 d'un objet peut contenir, certains codes de hachage sont partagés par plusieurs objets - de sorte que le code de hachage est pas nécessairement unique.

Un dictionnaire est un vraiment cool structure de données qui négocie une empreinte mémoire plus élevée en échange de (plus ou moins) coûts constants pour Ajout / Suppression / Obtenir des opérations. Il est un mauvais choix pour itérer bien. En interne, un dictionnaire contient un tableau de godets, où les valeurs peuvent être stockées. Lorsque vous ajoutez une clé et la valeur à un dictionnaire, la méthode GetHashCode est appelée sur la touche. Le hashcode retourné est utilisé pour déterminer l'indice du seau dans lequel la paire clé / valeur doit être stockée.

Si vous voulez accéder à la valeur que vous passez la touche. La méthode GetHashCode est appelée sur la touche, et le seau contenant la valeur se trouve.

Quand un IEqualityComparer est passée dans le constructeur d'un dictionnaire, les méthodes et IEqualityComparer.Equals IEqualityComparer.GetHashCode sont utilisés à la place des méthodes sur les objets clés.

Maintenant, pour expliquer pourquoi les deux méthodes sont nécessaires, considèrent 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 de BoxEqualityComparer.GetHashCode dans votre exemple, ces deux boîtes ont la même hashcode - 100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 25 = 25 - même si elles ne sont manifestement pas le même objet. La raison pour laquelle ils sont les mêmes hashcode dans ce cas parce que vous utilisez le ^ (OU exclusif au niveau du bit) opérateur pour 100 ^ 100 annule laissant le zéro, ne en 1000 ^ 1000. Lorsque deux objets différents ont la même clé, nous appelons cela une collision.

Si l'on ajoute deux paires clé / valeur avec le même hashcode à un dictionnaire, ils sont tous deux stockés dans le même seau. Alors, quand nous voulons récupérer une valeur, la méthode GetHashCode est appelée sur notre clé pour localiser le seau. Comme il n'y a plus d'une valeur dans le seau, le dictionnaire itère sur toutes les paires clé / valeur dans le seau d'appeler la méthode Equals sur les clés pour trouver le bon.

Dans l'exemple que vous avez publié, les deux boîtes sont équivalentes, de sorte que la Equals méthode retourne vrai. Dans ce cas, le dictionnaire a deux touches identiques, il renvoie 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 à rechercher. Il calcule juste la hashcode et saute à cet endroit. La méthode Equals est un meilleur test de l'égalité, mais ne peut être utilisé pour cartographier un objet dans un espace d'adressage.

L'espoir qui aide

Answer 2

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

Answer 3

Alors qu'il serait possible pour un Dictionary<TKey,TValue> d'avoir son GetValue et des méthodes similaires appel Equals sur chaque clé stockée unique pour voir si elle correspond à celui recherché, ce serait très lent. Au lieu de cela, comme beaucoup de collections à base de hachage, il repose sur GetHashCode d'exclure rapidement la plupart des valeurs qui ne correspondent pas de considération. Si vous appelez GetHashCode sur un élément étant des rendements recherchés 42, et une collection a 53917 points, mais d'appeler GetHashCode sur 53914 des articles a donné une valeur autre que 42, seuls trois éléments devront être comparés à ceux recherchés. L'autre 53914 peut être ignorée sans risque.

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 commun serait un appelant qui veut utiliser des chaînes comme clés, mais l'utilisation des comparaisons insensibles à la casse. Pour faire ce travail efficacement, le dictionnaire devra avoir une certaine forme de fonction de hachage qui donnera la même valeur pour « Fox » et « FOX », mais nous espérons obtenir quelque chose d'autre pour « boîte » ou « zèbre ». 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 la nécessité d'un tel code de hachage serait très fortement associée à une Equals méthode qui considère « Fox » et « FOX » identique à l'autre, mais pas « boîte » ou « zèbre ».