Welche Rolle spielt GetHashCode im IEqualityComparer <T> in .NET?

142

Ich versuche die Rolle der GetHashCode-Methode der Schnittstelle IEqualityComparer zu verstehen.

Das folgende Beispiel stammt aus 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();
    }
}

Sollte die Implementierung der Equals-Methode nicht ausreichen, um zwei Box-Objekte zu vergleichen? Hier teilen wir dem Framework die Regel mit, mit der die Objekte verglichen werden. Warum wird der GetHashCode benötigt?

Vielen Dank.

Lucian

Lucian
quelle
Lesen Sie: en.wikipedia.org/wiki/Hash_table und prüfen Sie, ob Sie den Zweck von GetHashCode besser verstehen.
Spender
1
Sehen Sie diese großartige Antwort: stackoverflow.com/a/3719802/136967
Mikhail

Antworten:

200

Ein bisschen Hintergrund zuerst ...

Jedes Objekt in .NET verfügt über eine Equals-Methode und eine GetHashCode-Methode.

Die Equals-Methode wird verwendet, um ein Objekt mit einem anderen Objekt zu vergleichen - um festzustellen, ob die beiden Objekte gleichwertig sind.

Die GetHashCode-Methode generiert eine 32-Bit-Ganzzahldarstellung des Objekts. Da die Anzahl der Informationen, die ein Objekt enthalten kann, unbegrenzt ist, werden bestimmte Hash-Codes von mehreren Objekten gemeinsam genutzt. Daher ist der Hash-Code nicht unbedingt eindeutig.

Ein Wörterbuch ist eine wirklich coole Datenstruktur, die einen höheren Speicherbedarf gegen (mehr oder weniger) konstante Kosten für Add / Remove / Get-Vorgänge eintauscht. Es ist jedoch eine schlechte Wahl, um es zu wiederholen. Intern enthält ein Wörterbuch ein Array von Buckets, in denen Werte gespeichert werden können. Wenn Sie einem Wörterbuch einen Schlüssel und einen Wert hinzufügen, wird die GetHashCode-Methode für den Schlüssel aufgerufen. Der zurückgegebene Hashcode wird verwendet, um den Index des Buckets zu bestimmen, in dem das Schlüssel / Wert-Paar gespeichert werden soll.

Wenn Sie auf den Wert zugreifen möchten, übergeben Sie den Schlüssel erneut. Die GetHashCode-Methode wird für den Schlüssel aufgerufen, und der Bucket mit dem Wert befindet sich.

Wenn ein IEqualityComparer an den Konstruktor eines Wörterbuchs übergeben wird, werden anstelle der Methoden für die Key-Objekte die Methoden IEqualityComparer.Equals und IEqualityComparer.GetHashCode verwendet.

Betrachten Sie nun dieses Beispiel, um zu erklären, warum beide Methoden erforderlich sind:

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"); 

Wenn Sie in Ihrem Beispiel die BoxEqualityComparer.GetHashCode-Methode verwenden, haben beide Boxen denselben Hashcode - 100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 25 = 25 - obwohl sie eindeutig nicht dasselbe Objekt sind. Der Grund dafür, dass es sich in diesem Fall um denselben Hashcode handelt, liegt darin, dass Sie den Operator ^ (bitweises Exklusiv-ODER) verwenden, sodass 100 ^ 100 abbrechen und Null hinterlassen, ebenso wie 1000 ^ 1000. Wenn zwei verschiedene Objekte denselben Schlüssel haben, nennen wir das eine Kollision.

Wenn wir einem Wörterbuch zwei Schlüssel / Wert-Paare mit demselben Hashcode hinzufügen, werden beide im selben Bucket gespeichert. Wenn wir also einen Wert abrufen möchten, wird die GetHashCode-Methode für unseren Schlüssel aufgerufen, um den Bucket zu lokalisieren. Da der Bucket mehr als einen Wert enthält, durchläuft das Wörterbuch alle Schlüssel / Wert-Paare im Bucket und ruft die Equals-Methode auf den Schlüsseln auf, um den richtigen zu finden.

In dem von Ihnen veröffentlichten Beispiel sind die beiden Felder äquivalent, sodass die Equals-Methode true zurückgibt. In diesem Fall verfügt das Wörterbuch über zwei identische Schlüssel, sodass eine Ausnahme ausgelöst wird.

TLDR

Zusammenfassend wird die GetHashCode-Methode verwendet, um eine Adresse zu generieren, an der das Objekt gespeichert ist. Ein Wörterbuch muss also nicht danach suchen. Es berechnet nur den Hashcode und springt zu diesem Ort. Die Equals-Methode ist ein besserer Test für die Gleichheit, kann jedoch nicht zum Zuordnen eines Objekts zu einem Adressraum verwendet werden.

Sheikhjabootie
quelle
4
Für diejenigen, die sich fragen, was der ^ -Operator ist, ist dies der bitweise Exklusiv-ODER-Operator, siehe msdn.microsoft.com/en-us/library/zkacc7k1.aspx .
R. Schreurs
2
Nur um dies explizit hervorzuheben : ( msdn.microsoft.com/en-us/library/ms132155.aspx ) Hinweise für Implementierer Implementierungen sind erforderlich, um sicherzustellen, dass der Wert zurückgegeben wird, wenn die Equals-Methode für zwei Objekte x und y true zurückgibt von der GetHashCode-Methode für x muss dem für y zurückgegebenen Wert entsprechen.
Diego Frehner
2
@DiegoFrehner - Du hast ganz recht. Eine andere Sache, die Menschen auslösen kann, ist, dass der Wert der GetHashCode-Methode nicht variieren sollte, wenn das Objekt geändert wird. Daher sollten die Felder innerhalb des Objekts, von denen GetHashCode abhängt, schreibgeschützt (unveränderlich) sein. Es gibt eine Erklärung hier: stackoverflow.com/a/4868940/469701
sheikhjabootie
1
@Acentric: Der Hash-Code eines Objekts sollte sich nur ändern, wenn er auf eine Weise mutiert ist, die sich auf die Gleichheit auswirkt. Wenn eine Klasse so mutiert werden kann, dass die Gleichheit beeinträchtigt wird, sollte Code vermeiden, dass in einem Wörterbuch eine Instanz gespeichert wird, die möglicherweise Code ausgesetzt ist, der sie mutiert, während sie sich im Wörterbuch befindet. Wenn der Code, in dem das Objekt gespeichert ist, diese Regel einhält, kann es nützlich sein, einen Hash-Code zu haben, der den veränderlichen Status widerspiegelt. Es ist schade, dass .NET Zustandsgleichheit und -äquivalenz nicht besser unterscheidet, da beide nützliche Konzepte sind.
Supercat
3
@Acentric: Auch Hash - Code für Hash-Tabelle Adressierung, die über die Verwendung grundlegende Idee hinter einem Hash - Code ist , dass das Wissen , dass zwei Objekte unterschiedliche Hash - Codes haben impliziert , dass sie ungleich und brauchen sie nicht zu vergleichen. Folglich impliziert das Wissen, dass die Hash-Codes vieler Objekte nicht mit dem Hash-Code eines bestimmten Objekts übereinstimmen, dass keiner von ihnen dem Objekt entspricht. Die Verwendung eines Hash-Codes zur Adressierung ist im Grunde eine Möglichkeit, Objekte mit unterschiedlichen Hash-Codes zu ignorieren.
Supercat
9

GetHashCode wird in Dictionary-Spalten verwendet und erstellt Hash zum Speichern von Objekten darin. Hier ist ein schöner Artikel, warum und wie IEqualtyComparer und GetHashCode verwendet werden http://dotnetperls.com/iequalitycomparer

Asche
quelle
4
Mehr: Wenn Sie Equals vergleichen müssen, wäre dies enouf, aber wenn Sie ein Element aus dem Dictionary abrufen müssen, ist es einfacher, dies durch Hash zu tun, nicht durch Verwendung von Equals .
Ash
5

Während es für a möglich wäre Dictionary<TKey,TValue>, dass seine GetValueund ähnliche Methoden Equalsjeden einzelnen gespeicherten Schlüssel aufrufen , um festzustellen, ob er mit dem gesuchten übereinstimmt, wäre dies sehr langsam. Stattdessen müssen wie bei vielen Hash-basierten Sammlungen GetHashCodedie meisten nicht übereinstimmenden Werte schnell von der Betrachtung ausgeschlossen werden. Wenn das Aufrufen GetHashCodeeines gesuchten Gegenstands 42 ergibt und eine Sammlung 53.917 Gegenstände enthält, das Aufrufen GetHashCodevon 53.914 Gegenständen jedoch einen anderen Wert als 42 ergibt, müssen nur 3 Gegenstände mit den gesuchten verglichen werden. Die anderen 53.914 können sicher ignoriert werden.

Der Grund, warum a GetHashCodein a enthalten IEqualityComparer<T>ist, besteht darin, die Möglichkeit zu berücksichtigen, dass der Verbraucher eines Wörterbuchs als gleiche Objekte betrachten möchte, die sich normalerweise nicht als gleich betrachten würden. Das häufigste Beispiel wäre ein Aufrufer, der Zeichenfolgen als Schlüssel verwenden möchte, jedoch Vergleiche ohne Berücksichtigung der Groß- und Kleinschreibung verwendet. Damit dies effizient funktioniert, muss das Wörterbuch über eine Hash-Funktion verfügen, die für "Fox" und "FOX" den gleichen Wert liefert, für "box" oder "zebra" jedoch hoffentlich etwas anderes. Da die GetHashCodeeingebaute Methode Stringnicht so funktioniert, muss das Wörterbuch eine solche Methode von einem anderen Ort beziehen.IEqualityComparer<T>Equals Methode, die "Fox" und "FOX" als identisch betrachtet, jedoch nicht als "Box" oder "Zebra".

Superkatze
quelle
Die richtige und auf den Punkt Antwort auf die Frage! GetHashCode () muss Equals () für die betreffenden Objekte ergänzen.
Sumith
@Sumith: Viele Diskussionen über Hashing sprechen über Eimer, aber ich denke, es ist nützlicher, an Ausschluss zu denken. Wenn Vergleiche teuer sind, kann Hashing Vorteile bieten, selbst wenn Sammlungen verwendet werden, die nicht in Buckets organisiert sind.
Supercat