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

142

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

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

Merci.

Lucian

Lucian
la source
Lisez: en.wikipedia.org/wiki/Hash_table puis voyez si vous comprenez mieux le but de GetHashCode.
dépenser
1
Voir cette excellente réponse: stackoverflow.com/a/3719802/136967
Mikhail

Réponses:

201

Un peu de contexte d'abord ...

Chaque objet dans .NET a 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 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 - le code de hachage n'est donc 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 Ajouter / Supprimer / Obtenir. C'est un mauvais choix pour répéter cependant. En interne, un dictionnaire contient un tableau de compartiments, où 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 souhaitez accéder à la valeur, vous transmettez à nouveau la clé. La méthode GetHashCode est appelée sur la clé et le compartiment contenant la valeur est localisé.

Lorsqu'un IEqualityComparer est passé dans le 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érons 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 le même hashcode - 100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 25 = 25 - même si elles ne sont clairement pas le même objet. La raison pour laquelle il s'agit du même code de hachage dans ce cas est que vous utilisez l'opérateur ^ (OU exclusif au niveau du bit), donc 100 ^ 100 annule en laissant 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 hashcode à 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. Puisqu'il y a plus d'une valeur dans le compartiment, le dictionnaire itère sur toutes les paires clé / valeur dans le compartiment en appelant la méthode Equals sur les clés pour trouver la bonne.

Dans l'exemple que vous avez publié, les deux zones sont équivalentes, donc la méthode Equals renvoie true. Dans ce cas, le dictionnaire a deux clés identiques, il lève donc 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é. Un dictionnaire n'a donc pas besoin de le rechercher. Il calcule simplement le hashcode et saute à cet emplacement. 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.

cheikhjabootie
la source
4
Pour ceux qui se demandent ce qu'est l'opérateur ^, il s'agit de l'opérateur OU exclusif au niveau du bit, voir msdn.microsoft.com/en-us/library/zkacc7k1.aspx .
R. Schreurs
2
Juste pour souligner cela explicitement: ( msdn.microsoft.com/en-us/library/ms132155.aspx ) Notes aux implémentations Les implémentations sont requises pour s'assurer que si la méthode Equals retourne true pour deux objets x et y, la valeur renvoyée par la méthode GetHashCode pour x doit être égal à la valeur renvoyée pour y.
Diego Frehner
2
@DiegoFrehner - Vous avez tout à fait raison. Une autre chose qui peut tromper les gens est que la valeur de la méthode GetHashCode ne doit pas varier si l'objet est modifié. Ainsi, les champs de l'objet dont dépend GetHashCode doivent être en lecture seule (immuables). Il y a une explication ici: stackoverflow.com/a/4868940/469701
sheikhjabootie
1
@Acentric: le code de hachage d'un objet ne doit pas changer sauf s'il est muté d'une manière qui affecte l'égalité. Si une classe peut être mutée de manière à affecter l'égalité, le code doit éviter de stocker dans un dictionnaire toute instance qui pourrait être exposée à du code qui la muterait lorsqu'elle est dans le dictionnaire. Si le code qui stocke l'objet respecte cette règle, avoir un code de hachage qui reflète l'état mutable peut être utile. C'est dommage que .NET ne distingue pas mieux l'égalité et l'équivalence d'état, car les deux sont des concepts utiles.
supercat
3
@Acentric: Même au-delà de l'utilisation du code de hachage pour l'adressage de table de hachage, l' idée fondamentale derrière un code de hachage est que la connaissance que deux objets ont des codes de hachage différents implique qu'ils sont inégaux et n'ont pas besoin de les comparer. En corollaire, savoir que les codes de hachage de nombreux objets ne correspondent pas au code de hachage d'un objet donné implique qu'aucun d'entre eux n'est égal à l'objet. L'utilisation d'un code de hachage pour l'adressage est fondamentalement un moyen d'ignorer les objets qui ont des codes de hachage différents.
supercat
9

GetHashCode est utilisé dans les colections de dictionnaire et crée un hachage pour y stocker des objets. Voici un bel article pourquoi et comment utiliser IEqualtyComparer et GetHashCode http://dotnetperls.com/iequalitycomparer

Cendre
la source
4
Plus: Si vous avez besoin de comparer Equals serait enouf, mais lorsque vous avez besoin d'obtenir un élément du dictionnaire, il est plus facile de le faire par hachage, pas en utilisant Equals .
Ash
5

Bien qu'il soit possible pour a Dictionary<TKey,TValue>de faire GetValueappel Equalsà ses méthodes et à des méthodes similaires sur chaque clé stockée pour voir si elle correspond à celle recherchée, ce serait très lent. Au lieu de cela, comme de nombreuses collections basées sur le hachage, il s'appuie sur GetHashCodepour exclure rapidement la plupart des valeurs non correspondantes de la considération. Si le fait de faire appel GetHashCodeà un article recherché donne 42 et qu'une collection contient 53 917 articles, mais que l'appel GetHashCodede 53 914 articles a donné une valeur différente de 42, alors seulement 3 articles devront être comparés à ceux recherchés. Les 53 914 autres peuvent être ignorés en toute sécurité.

La raison pour laquelle a GetHashCodeest inclus dans un IEqualityComparer<T>est de permettre la possibilité que le consommateur d'un dictionnaire veuille considérer comme des objets égaux qui ne se considéreraient normalement pas comme égaux. L'exemple le plus courant serait un appelant qui souhaite utiliser des chaînes comme clés mais utiliser des comparaisons insensibles à la casse. Pour que cela fonctionne efficacement, le dictionnaire devra avoir une certaine forme de fonction de hachage qui donnera la même valeur pour "Fox" et "FOX", mais avec un peu de chance, il donnera autre chose pour "box" ou "zebra". Comme la GetHashCodeméthode intégrée Stringne fonctionne pas de cette façon, le dictionnaire devra obtenir une telle méthode ailleurs,IEqualityComparer<T>Equals méthode qui considère "Fox" et "FOX" identiques l'un à l'autre, mais pas à "box" ou "zebra".

supercat
la source
La réponse correcte et précise à la question! GetHashCode () doit compléter Equals () pour les objets en question.
Sumith
@Sumith: De nombreuses discussions sur le hachage parlent de seaux, mais je pense qu'il est plus utile de penser à l'exclusion. Si les comparaisons coûtent cher, le hachage peut offrir des avantages même lors de l'utilisation de collections qui ne sont pas organisées en buckets.
supercat