Jaka jest rola GetHashCode w Ieequalitycomparer in.NET?

Question

Jaka jest rola GetHashCode w Ieequalitycomparer in.NET?

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

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 powiemy frameworkowi regułę używaną do porównywania obiektów. Dlaczego potrzebny jest GetHashCode?

Dzięki.

Lucian

143

.net c#gethashcode iequalitycomparer

Author: Lucian, 2010-11-04

Source

3 answers

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

9

Author: Ash,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-11-04 09:57:33

Chociaż możliwe byłoby, aby Dictionary<TKey,TValue> wywoływało swoje GetValue i podobne metody Equals na każdym pojedynczym przechowywanym kluczu, aby sprawdzić, czy pasuje do poszukiwanego, byłoby to bardzo powolne. Zamiast tego, podobnie jak wiele zbiorów opartych na hash, opiera się na GetHashCode, aby szybko wykluczyć większość niepasujących wartości z rozważenia. Jeśli wywołanie {[3] } na poszukiwanym elemencie daje 42, A zbiór ma 53 917 elementów, ale wywołanie GetHashCode na 53 914 elementów daje wartość inną niż 42, to tylko 3 przedmioty będą musiały być porównywane z poszukiwanymi. Pozostałe 53 914 można bezpiecznie zignorować.

Powodem, dla którego a GetHashCode jest zawarte w an IEqualityComparer<T> jest umożliwienie konsumentowi słownika uznania za równe przedmioty, które normalnie Nie uznają się 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 rozróżniania wielkości liter. Aby to działało efektywnie, słownik będzie potrzebował mieć jakąś formę funkcji hash, która da taką samą wartość dla " Fox " i "FOX" , ale miejmy nadzieję, że da coś innego dla " box " lub "zebra". Ponieważ metoda GetHashCode wbudowana w String nie działa w ten sposób, słownik będzie musiał pobrać taką metodę z innego miejsca, a IEqualityComparer<T> jest najbardziej logicznym miejscem, ponieważ potrzeba takiego kodu hashowego byłaby bardzo silnie powiązana z metodą Equals, która uważa "Fox" i "FOX" identyczne do siebie, ale nie do "box" czy "zebra".

5

Author: supercat,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2015-03-18 17:49:00

score 204 · Accepted Answer

Najpierw trochę tła...

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

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

Metoda GetHashCode generuje 32-bitową reprezentację całkowitą obiektu. 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 jest naprawdę fajną strukturą danych, która wymienia większy ślad pamięci w zamian za (mniej więcej) stałe koszty operacji Dodaj/usuń / Pobierz. Jest to jednak kiepski wybór do iteracji. Wewnętrznie Słownik zawiera tablicę łyżek, w której wartości mogą być przechowywane. Po dodaniu klucza i wartości do słownika, na kluczu zostanie wywołana metoda GetHashCode. Zwracany hashcode służy do określenia indeksu wiadra, w którym para klucz / wartość powinna być przechowywany.

Gdy chcesz uzyskać dostęp do wartości, przekazujesz klucz ponownie. Na kluczu jest wywołana metoda GetHashCode i znajduje się wiadro zawierające wartość.

Ieequalitycomparer jest przekazywany do konstruktora słownika, Ieequalitycomparer.Równi i Równi.Metody GetHashCode są stosowane zamiast metod na kluczowych obiektach.

Teraz, aby wyjaśnić, dlaczego obie metody są konieczne, rozważ ten 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");

Za pomocą BoxEqualityComparer.Metoda GetHashCode w twoim przykładzie oba te pola mają ten sam hashcode - 100^100^25 = 1000^1000^25 = 25 - nawet jeśli nie są one wyraźnie tym samym przedmiotem. Powodem, dla którego są to ten sam hashcode w tym przypadku, jest to, że używasz operatora ^ (bitowo exclusive-OR), więc 100^100 anuluje pozostawiając zero, podobnie jak 1000^1000. Gdy dwa różne obiekty mają ten sam klucz, nazywamy to kolizją.

Gdy dodamy dwie pary klucz / wartość z tym samym hashcode do słownika, oba są przechowywane w tym samym wiadrze. Więc kiedy chcemy pobrać wartość, metoda GetHashCode jest wywoływana na naszym kluczu, aby zlokalizować wiadro. Ponieważ w zasobniku znajduje się więcej niż jedna wartość, słownik iteruje wszystkie pary 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 true. W tym przypadku słownik ma dwa identyczne Klucze, więc rzuca wyjątek.

TLDR

Podsumowując, metoda GetHashCode jest używana do wygenerowania adresu, pod którym obiekt jest przechowywany. Więc słownik nie musi go szukać. Po prostu oblicza hashcode i przeskakuje do tego miejsca. Metoda Equals jest lepszym testem równości, ale nie może być używana do mapowania obiektu w przestrzeni adresowej.