Jaka jest rola GetHashCode w IEqualityComparer <T> w .NET?

Próbuję zrozumieć rolę metody GetHashCode interfejsu IEqualityComparer.

Poniższy przykład pochodzi z 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();
    }
}

Czy implementacja metody Equals nie powinna wystarczyć do porównania dwóch obiektów Box? W tym miejscu podajemy szkieletowi regułę używaną do porównywania obiektów. Dlaczego potrzebny jest GetHashCode?

Dzięki.

Lucian

Najpierw trochę tła ...

Każdy obiekt w .NET ma metodę Equals i metodę GetHashCode.

Metoda Equals służy do porównywania jednego obiektu z innym obiektem - aby sprawdzić, czy dwa obiekty są równoważne.

Metoda GetHashCode generuje 32-bitową reprezentację obiektu w postaci liczby całkowitej. Ponieważ nie ma ograniczeń co do tego, ile informacji może zawierać obiekt, niektóre kody skrótu są współdzielone przez wiele obiektów - więc kod skrótu niekoniecznie jest unikalny.

Słownik to naprawdę fajna struktura danych, która umożliwia wymianę większej ilości pamięci w zamian za (mniej lub bardziej) stałe koszty operacji Dodaj / Usuń / Pobierz. Jest to jednak kiepski wybór do iteracji. Słownik wewnętrznie zawiera tablicę zasobników, w których można przechowywać wartości. Po dodaniu klucza i wartości do słownika metoda GetHashCode jest wywoływana w pliku Key. Zwrócony kod skrótu służy do określenia indeksu zasobnika, w którym powinna być przechowywana para klucz / wartość.

Gdy chcesz uzyskać dostęp do wartości, ponownie podajesz klucz. Metoda GetHashCode jest wywoływana w kluczu i znajduje się zasobnik zawierający Value.

Gdy IEqualityComparer jest przekazywany do konstruktora słownika, metody IEqualityComparer.Equals i IEqualityComparer.GetHashCode są używane zamiast metod w obiektach Key.

Teraz, aby wyjaśnić, dlaczego obie metody są konieczne, rozważ następujący przykład:

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

Używając metody BoxEqualityComparer.GetHashCode w naszym przykładzie, oba te pola mają ten sam kod skrótu - 100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 25 = 25 - nawet jeśli wyraźnie nie są tym samym obiektem. Powodem, dla którego są one tym samym hashcode w tym przypadku, jest to, że używasz operatora ^ (bitowe wykluczające-OR), więc 100 ^ 100 anuluje pozostawiając zero, podobnie jak 1000 ^ 1000. Kiedy dwa różne obiekty mają ten sam klucz, nazywamy to kolizją.

Kiedy dodajemy do słownika dwie pary klucz / wartość z tym samym hashcode, obie są przechowywane w tym samym zasobniku. Więc kiedy chcemy pobrać wartość, metoda GetHashCode jest wywoływana w naszym kluczu, aby zlokalizować zasobnik. Ponieważ w zasobniku jest więcej niż jedna wartość, słownik wykonuje iterację po wszystkich parach klucz / wartość w zasobniku, wywołując metodę Equals na kluczach, aby znaleźć właściwą.

W opublikowanym przykładzie oba pola są równoważne, więc metoda Equals zwraca wartość true. W tym przypadku słownik ma dwa identyczne klucze, więc zgłasza wyjątek.

TLDR

Podsumowując, metoda GetHashCode służy do generowania adresu, pod którym przechowywany jest obiekt. Więc słownik nie musi tego szukać. Po prostu oblicza kod skrótu i ​​przeskakuje do tej lokalizacji. Metoda Equals jest lepszym testem równości, ale nie można jej używać do mapowania obiektu na przestrzeń adresową.

GetHashCode jest używany w kolekcjach Dictionary i tworzy hash do przechowywania w nim obiektów. Oto fajny artykuł, dlaczego i jak używać IEqualtyComparer i GetHashCode http://dotnetperls.com/iequalitycomparer

Chociaż byłoby możliwe, Dictionary<TKey,TValue>aby jego GetValuei podobne metody wywoływały Equalskażdy pojedynczy przechowywany klucz, aby sprawdzić, czy pasuje do szukanego, byłoby to bardzo powolne. Zamiast tego, podobnie jak wiele kolekcji opartych na skrótach, polega na GetHashCodeszybkim wykluczeniu z rozważań większości niepasujących wartości. Jeśli wywołanie GetHashCodeposzukiwanego przedmiotu daje 42, a kolekcja zawiera 53 917 elementów, ale wywołanie GetHashCode53 914 elementów dało wartość inną niż 42, to tylko 3 elementy będą musiały zostać porównane z poszukiwanymi. Pozostałe 53,914 można bezpiecznie zignorować.

Powodem, dla którego a GetHashCodejest zawarte w an, IEqualityComparer<T>jest uwzględnienie możliwości, że konsument słownika może chcieć traktować równe przedmioty, które normalnie nie uważałyby siebie za równe. Najczęstszym przykładem może być wywołanie, które chce używać ciągów jako kluczy, ale używa porównań bez uwzględniania wielkości liter. Aby to działało efektywnie, słownik będzie musiał mieć jakąś formę funkcji skrótu, która da tę samą wartość dla „Fox” i „FOX”, ale miejmy nadzieję, że da coś innego dla „box” lub „zebra”. Ponieważ GetHashCodemetoda wbudowana Stringnie działa w ten sposób, słownik będzie musiał pobrać taką metodę z innego miejsca,IEqualityComparer<T>Equals metoda uznająca „Lis” i „LIS” za identyczne, ale nie za „pudełko” czy „zebra”.