Was ist die Rolle der GetHashCode im IEqualityComparer in .NET?

Question

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

Das folgende Beispiel aus MSDN genommen:

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 nicht die Methode equals Implementierung genug sein, um zu vergleichen, zwei Box-Objekte? Das ist, wo wir den Rahmen der Regel sagen, verwendet, um die Objekte zu vergleichen. Warum ist das GetHashCode benötigt?

Danke.

Lucian

Answer 1

Ein bisschen Hintergrund zuerst ...

Jedes Objekt in .NET ist ein Gleichheits Verfahren und eine GetHashCode-Methode.

Die Equals-Methode verwendet wird, ein Objekt mit einem anderen Objekt zu vergleichen -. Zu sehen, ob die beiden Objekte äquivalent sind

Die GetHashCode Verfahren erzeugen eine 32-Bit-Ganzzahl-Darstellung des Objekts. Da gibt es kein Limit, wie viele Informationen sind ein Objekt enthält, bestimmte Hash-Codes von mehreren Objekten gemeinsam - so der Hash-Code nicht notwendigerweise eindeutig ist.

Ein Wörterbuch ist ein wirklich Datenstruktur kühlen, die einen höheren Speicherbedarf im Gegenzug tauscht (mehr oder weniger) konstant Kosten für Hinzufügen / Entfernen / Get-Operationen. Es ist eine schlechte Wahl für obwohl iterieren. Intern enthält das Wörterbuch eine Reihe von Schaufeln, wobei die Werte gespeichert werden können. Wenn Sie einen Schlüssel und Wert zu einem Wörterbuch hinzufügen, wird die GetHashCode-Methode auf dem Key genannt. Der Hash-Code zurückgegeben wird verwendet, um den Index der Schaufel, um zu bestimmen, in dem der Schlüssel / Wert-Paar gespeichert werden soll.

Wenn Sie den Wert zugreifen möchten, übergeben Sie in die Taste erneut. Die GetHashCode-Methode basiert auf dem Key genannt, und der Eimer mit dem Wert, liegt.

Wenn ein IEqualityComparer in den Konstruktor eines Wörterbuchs übergeben wird, werden die IEqualityComparer.Equals und IEqualityComparer.GetHashCode Methoden anstelle der Methoden auf den Key-Objekten verwendet.

Nun zu erklären, warum beide Methoden notwendig sind, betrachten Sie dieses Beispiel:

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

Mit der BoxEqualityComparer.GetHashCode Methode in Ihrem Beispiel, beide Boxen den gleichen Hash-Code - 100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 25 = 25 - obwohl sie eindeutig nicht das gleiche Objekt. Der Grund, dass sie die gleiche Hash-Code in diesem Fall ist, weil Sie die ^ (bitweise Exklusiv-OR) verwenden Betreiber so 100 ^ 100 auslöscht Null zu verlassen, tut als 1000 ^ 1000. Wenn zwei verschiedene Objekte den gleichen Schlüssel haben, rufen wir, dass eine Kollision.

Wenn wir zwei Schlüssel / Wert-Paare mit dem gleichen Hash-Code in ein Wörterbuch aufnehmen, sie sind beide in dem gleichen Eimer gespeichert. Wenn wir also einen Wert abrufen möchten, wird die GetHashCode-Methode auf unserem Key nennt den Eimer zu lokalisieren. Da es mehr als ein Wert im Eimer ist, in dem Wörterbuch iteriert über alle der Schlüssel / Wert-Paare auf dem heißen Stein Aufruf der Methode Equals auf den Tasten, um die richtigen zu finden.

In dem Beispiel, das Sie auf dem Laufenden, sind die beiden Boxen gleichwertig, so dass die Methode Equals gibt true zurück. In diesem Fall hat das Wörterbuch zwei identische Schlüssel, so dass es eine Ausnahme auslöst.

TLDR

So zusammenfassend wird die GetHashCode-Methode verwendet, um eine Adresse zu erzeugen, in dem das Objekt gespeichert ist. So ein Wörterbuch muss nicht danach suchen. Er berechnet nur den Hash-Code und springt an dieser Stelle. Die Methode equals ein besserer Test der Gleichheit, aber nicht verwendet werden kann, ein Objekt in einem Adressraum abzubilden.

Ich hoffe, das hilft

Answer 2

GetHashCode in Wörterbuch colections verwendet wird und es schafft Hash für Objekte darin zu speichern. Hier ist ein schöner Artikel, warum und wie man Gebrauch IEqualtyComparer und GetHashCode http: //dotnetperls.com/iequalitycomparer

Answer 3

Während es möglich wäre, ein Dictionary<TKey,TValue> seine GetValue zu haben und ähnliche Methoden aufrufen Equals auf jeder einzelnen gespeicherten Schlüssel, um zu sehen, ob es das ein Wesen gesucht einstimmt, das wäre sehr langsam sein. Stattdessen wie viele Hash-basierte Sammlungen stützt sie sich auf GetHashCode, um schnell die meisten nicht passende Werte aus der Betrachtung auszuschließen. Wenn Aufruf GetHashCode auf ein Element Erträge 42 gesucht, und eine Sammlung 53.917 Artikel, aber Aufruf GetHashCode auf 53.914 der Elemente einen anderen Wert als 42 ergab, dann nur drei Elemente müssen verglichen werden, um diejenigen gesucht. Die anderen 53.914 sicher ignoriert werden können.

Der Grund, ein GetHashCode in einem IEqualityComparer<T> enthalten ist, ist für die Möglichkeit gelassen werden, dass ein Verbraucher die Wörterbuch könnte als gleichwertige Objekte betrachten möchten, die normalerweise würde nicht einander als gleich betrachten. Das häufigste Beispiel würde ein Anrufer, die wollen Strings als Schlüssel verwenden, aber die Verwendung Groß- und Kleinschreibung Vergleiche. Um diese Arbeit effizient zu machen, wird das Wörterbuch braucht irgendeine Form von Hash-Funktion haben, die den gleichen Wert für „Fox“ und „FOX“ nachgeben, aber hoffentlich etwas anderes für „Box“ oder „Zebra“ ergeben. Da die GetHashCode Verfahren in String gebaut nicht so funktioniert, muss das Wörterbuch, ein solches Verfahren erhalten von woanders, und IEqualityComparer<T> ist die logischste Ort, da die Notwendigkeit für eine solche Hash-Code sehr stark mit einem Equals in Verbindung gebracht werden Methode, die „Fox“ und „FOX“ identisch miteinander, aber nicht beschränkt auf „Box“ oder „Zebra“.

hält