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

142

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

Lucian
źródło
Przeczytaj: en.wikipedia.org/wiki/Hash_table, a następnie sprawdź, czy lepiej rozumiesz cel GetHashCode.
wydaje
1
Zobacz tę świetną odpowiedź: stackoverflow.com/a/3719802/136967
Michaił

Odpowiedzi:

201

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ą.

sheikhjabootie
źródło
4
Dla tych, którzy zastanawiają się, czym jest ^ -operator, jest to bitowy operator wyłącznego OR, zobacz msdn.microsoft.com/en-us/library/zkacc7k1.aspx .
R. Schreurs
2
Wystarczy wyraźnie wskazać na to: ( msdn.microsoft.com/en-us/library/ms132155.aspx ) Uwagi do implementacji implementujących są wymagane, aby upewnić się, że jeśli metoda Equals zwróci true dla dwóch obiektów x i y, wówczas wartość zwrócona przez metodę GetHashCode dla x musi być równa wartości zwracanej dla y.
Diego Frehner
2
@DiegoFrehner - Masz rację. Inną rzeczą, która może zmylić ludzi, jest to, że wartość metody GetHashCode nie powinna się zmieniać, jeśli obiekt jest modyfikowany. Zatem pola w obiekcie, od których zależy GetHashCode, powinny być tylko do odczytu (niezmienne). Tutaj jest wyjaśnienie: stackoverflow.com/a/4868940/469701
sheikhjabootie
1
@Acentryczny: kod skrótu obiektu nie powinien się zmieniać, chyba że zostanie zmutowany w sposób wpływający na równość. Jeśli klasa może zostać zmutowana w taki sposób, aby wpłynąć na równość, kod powinien unikać przechowywania w słowniku jakichkolwiek instancji, które mogą być narażone na kod, który spowodowałby mutację, gdy znajduje się w słowniku. Jeśli kod, który przechowuje obiekt, podlega tej regule, przydatny może być kod skrótu, który odzwierciedla zmienny stan. Szkoda, że ​​.NET nie lepiej rozróżnia równości stanów i równoważności, ponieważ oba są użytecznymi pojęciami.
supercat
3
@Acentryczny: Nawet poza używaniem kodu skrótu do adresowania tablicy skrótów, podstawową ideą kodu skrótu jest to, że wiedza, że ​​dwa obiekty mają różne kody skrótu, oznacza, że ​​są nierówne i nie muszą ich porównywać. W konsekwencji wiedza, że ​​kody skrótów wielu obiektów nie pasują do kodu skrótu danego obiektu, oznacza, że ​​żaden z nich nie jest równy obiektowi. Używanie kodu skrótu do adresowania jest zasadniczo sposobem ignorowania obiektów, które mają różne kody skrótu.
supercat
9

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

Popiół
źródło
4
Więcej: Jeśli chcesz porównać Equals , wystarczyłoby, ale gdy potrzebujesz pobrać element ze słownika, łatwiej to zrobić za pomocą skrótu, a nie za pomocą Equals .
Ash
5

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”.

superkat
źródło
Prawidłowa i rzeczowa odpowiedź na pytanie! GetHashCode () musi uzupełniać Equals () dla danych obiektów.
Sumith
@Sumith: Wiele dyskusji na temat haszowania mówi o zasobnikach, ale myślę, że bardziej przydatne jest myślenie o wykluczeniu. Jeśli porównania są drogie, haszowanie może przynieść korzyści nawet w przypadku korzystania z kolekcji, które nie są zorganizowane w zasobniki.
supercat