Ogólne porady i wskazówki, jak prawidłowo nadpisać obiekt.GetHashCode()
Zgodnie z MSDN, Funkcja hash musi mieć następujące właściwości:
Jeśli dwa obiekty są równe, metoda GetHashCode dla każdego obiektu musi zwrócić tę samą wartość. Jeśli jednak dwa obiekty nie są sobie równe, metody GetHashCode dla tych dwóch obiektów nie muszą zwracać różnych wartości.
Metoda GetHashCode dla obiektu musi konsekwentnie zwracać ten sam kod skrótu, o ile nie ma modyfikacji stan obiektu określający wartość zwracaną metody Equals obiektu. Zauważ, że jest to prawdą tylko dla bieżącego wykonywania aplikacji i że inny kod skrótu może zostać zwrócony, jeśli aplikacja zostanie uruchomiona ponownie.
Aby uzyskać najlepszą wydajność, funkcja hash musi wygenerować losowy rozkład dla wszystkich danych wejściowych.
Znajduję się w następującym scenariuszu: stworzyłem klasę, zaimplementowałem IEquatable<T>
i nadpisałem object.Equals(object)
. MSDN stwierdza, że:
Typy, które nadpisują równe muszą również nadpisać GetHashCode ; w przeciwnym razie Hashtable może nie działać poprawnie.
I wtedy zwykle zatrzymuje się trochę dla mnie. Ponieważ, jak prawidłowo nadpisać object.GetHashCode()
? Nigdy naprawdę Nie wiem, od czego zacząć, i wydaje się być wiele pułapek.
Tutaj w StackOverflow jest sporo pytań związanych z nadpisywaniem kodu GetHashCode, ale większość z nich wydaje się dotyczyć dość szczególnych przypadków i konkretnych zagadnień. Dlatego chciałbym uzyskać dobrą kompilację tutaj. Przegląd z ogólnymi poradami i wytycznymi. Co robić, czego nie robić, typowe pułapki, od czego zacząć itp.
Chciałbym, aby było to szczególnie skierowane do C#, ale myślę, że będzie działać tak samo w innych językach. NET, jak również(?).
myślę, że może najlepszym sposobem jest stworzenie jednej odpowiedzi na temat z szybką i krótką odpowiedzią najpierw (blisko jednej linijki, jeśli w ogóle możliwe), potem może trochę więcej informacji i koniec z pokrewnymi pytaniami, dyskusjami, wpisami na blogu itp., jeśli są jakieś. Następnie mogę utworzyć jeden post jako zaakceptowaną odpowiedź (aby uzyskać ją na górze) z tylko "spis treści". Staraj się być krótki i zwięzły. I nie tylko Linkuj do innych pytań i postów na blogu. Spróbuj wziąć ich istotę, a następnie raczej link do źródła (zwłaszcza, że źródło może zniknąć. Proszę również spróbować edytować i poprawiać odpowiedzi zamiast tworzyć wiele bardzo podobne.
nie jestem zbyt dobrym pisarzem technicznym, ale przynajmniej postaram się sformatować odpowiedzi tak, aby wyglądały podobnie, stworzyć spis treści itp. Postaram się również wyszukać niektóre z powiązanych pytań tutaj, aby odpowiedzieć na niektóre z nich i być może wyciągnąć istotę tych, którymi mogę zarządzać. Ale ponieważ nie jestem zbyt stabilny w tym temacie, postaram się trzymać z daleka przez większą część :P
10 answers
Spis treści
Rzeczy, które chciałbym objąć, ale jeszcze nie były:
- Jak utworzyć liczbę całkowitą (jak "przekształcić" obiekt w int nie było dla mnie zbyt oczywiste).
- Jakie pola do bazuj na kodzie hashowym.
- Jeśli powinno być tylko na polach niezmiennych, co jeśli są tylko zmienne?
- Jak wygenerować dobry rozkład losowy. (MSDN Property #3)
- część tego, wydaje się wybrać dobrą magiczną liczbę pierwszą (widziano 17, 23 i 397), ale jak ją wybrać i do czego dokładnie służy?
- Jak upewnić się, że kod hash pozostaje taki sam przez cały okres istnienia obiektu. (MSDN Property #2)
- szczególnie, gdy równość opiera się na polach zmiennych. (MSDN Property #1)
- Jak radzić sobie z polami, które są złożonymi typami(nie należą do wbudowanych typów C # ).
- złożone obiekty i struktury, tablice, kolekcje, listy, słowniki, typy generyczne itp.
- na przykład, nawet jeśli lista lub słownik mogą być tylko odczytywane, nie oznacza to, że jego zawartość jest.
- Jak radzić sobie z dziedziczeniem klasy.
- czy powinieneś jakoś włączyć
base.GetHashCode()
do swojego kodu hashowego?
Możesz być leniwy i zwrócić 0? Bardzo mocno złamałby wytyczne MSDN numer # 3, ale przynajmniej upewniłby się, że #1 i #2 są zawsze prawdziwe :p
- czy powinieneś jakoś włączyć
- typowe pułapki i Gotcha.
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
2017-05-23 11:45:36
Jakie są te magiczne liczby często widywane w implementacjach GetHashCode?
Są liczbami pierwszymi. Liczby pierwsze są używane do tworzenia kodów skrótu, ponieważ liczba pierwsza maksymalizuje wykorzystanie przestrzeni kodu skrótu.
W szczególności, zacznij od małej liczby pierwszej 3 i weź pod uwagę tylko małą liczbę pierwsząnybbles z wyników:
- 3 * 1 = 3 = 3(mod 8) =
0011
- 3 * 2 = 6 = 6(mod 8) =
1010
- 3 * 3 = 9 = 1(mod 8) =
0001
- 3 * 4 = 12 = 4(mod 8) =
1000
- 3 * 5 = 15 = 7(mod 8) =
1111
- 3 * 6 = 18 = 2(mod 8) =
0010
- 3 * 7 = 21 = 5(mod 8) =
1001
- 3 * 8 = 24 = 0(mod 8) =
0000
- 3 * 9 = 27 = 3(mod 8) =
0011
I zaczynamy od nowa. Ale zauważysz, że kolejne wielokrotności naszej liczby pierwszej generowały każdą możliwą permutację bitów w naszym nybble, zanim zaczną się powtarzać. Taki sam efekt możemy uzyskać z dowolną liczbą pierwszą i dowolną liczbę bitów, co sprawia, że liczby pierwsze są optymalne do generowania prawie losowych kodów skrótu. Powodem, dla którego zwykle widzimy większe liczby pierwsze zamiast małych, takich jak 3 w powyższym przykładzie jest to, że dla większej liczby bitów w naszym kodzie skrótu, wyniki uzyskane z użycia małej liczby pierwszej nie są nawet pseudolosowe-są po prostu rosnącą sekwencją, dopóki nie napotkamy przepełnienia. Dla optymalnej losowości, liczba pierwsza, która powoduje przepełnienie dla dość małych współczynników powinna być używane, chyba że możesz zagwarantować, że Twoje współczynniki nie będą małe.
Powiązane linki:
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
2017-05-23 12:25:03
Sprawdź wytyczne i zasady GetHashCode Eric Lippert
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
2014-05-06 16:23:11
Powinieneś nadpisać je, gdy masz miarą równości dla obiektów tego typu(tzn. nadpisujesz równe). Gdybyś wiedział, że obiekt nie zostanie zaszyfrowany z jakiegokolwiek powodu, mógłbyś go zostawić, ale jest mało prawdopodobne, abyś wiedział o tym z góry.
Hash powinien być oparty tylko na właściwościach obiektu, które są używane do definiowania równości, ponieważ dwa obiekty, które są uważane za równe, powinny mieć ten sam kod skrótu. Ogólnie rzecz biorąc, zazwyczaj robisz coś like:
public override int GetHashCode()
{
int mc = //magic constant, usually some prime
return mc * prop1.GetHashCode() * prop2.GetHashCode * ... * propN.GetHashCode();
}
Zazwyczaj zakładam, że mnożenie wartości razem stworzy dość jednolity rozkład, zakładając, że funkcja hashcode każdej właściwości robi to samo, chociaż może to być błędne. Używając tej metody, jeśli zmienią się właściwości definiujące równość obiektów, wtedy prawdopodobnie zmieni się również kod skrótu, co jest akceptowalne, biorąc pod uwagę definicję # 2 w twoim pytaniu. Zajmuje się również wszystkimi typami w jednolity sposób.
Możesz zwrócić tę samą wartość dla wszystkich instancji, chociaż spowoduje to, że wszelkie algorytmy używające hashowania (takie jak dictionarys) będą bardzo wolne - zasadniczo wszystkie instancje będą hashowane do tego samego zasobnika i lookup będzie wtedy O(n) zamiast oczekiwanego o(1). To oczywiście neguje wszelkie korzyści z używania takich struktur do wyszukiwania.
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
2009-09-04 11:45:37
Dlaczego muszę nadpisać object.GetHashCode()
?
Nadpisanie tej metody jest ważne, ponieważ następująca właściwość musi zawsze pozostać prawdziwa:
W 2007 roku, w ramach projektu "the world of Warcraft 2009", w ramach projektu "the world of Warcraft 2009", w ramach projektu "the world of Warcraft 2009", w ramach projektu "the world of Warcraft 2009", w ramach projektu "the world of Warcraft 2009", w ramach projektu "the world of Warcraft 2009".]}Jeśli dwa obiekty są równe, metoda GetHashCode dla każdego obiektu musi zwrócić tę samą wartość.
Wiele klas używa kodu hashowego do klasyfikacji obiektu. W szczególności tabele hash oraz słowniki mają tendencję do umieszczania obiektów w wiadrach na podstawie ich kodu hashowego. Podczas sprawdzania, czy obiekt znajduje się już w tabeli hash, najpierw będzie szukał go w wiadrze. Jeśli dwa obiekty są równe, ale mają różne kody skrótu, mogą zostać umieszczone w różnych wiadrach i słownik nie przeszukiwałby obiektu.
Powiązane linki:
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
2017-05-23 12:19:40
A) musisz nadpisać zarówno Equals, jak i GetHashCode, jeśli chcesz użyć równości wartości zamiast domyślnej równości odniesienia. W przypadku późniejszych, dwa odniesienia do obiektów porównują się jako równe, jeśli oba odnoszą się do tej samej instancji obiektu. Z tymi pierwszymi porównują je jako równe, jeśli ich wartość jest taka sama, nawet jeśli odnoszą się do różnych obiektów. Na przykład prawdopodobnie chcesz użyć równości wartości dla obiektów daty, pieniędzy i punktów.
B) aby zaimplementować równość wartości musi nadpisać Equals i GetHashCode. Oba powinny zależeć od pól obiektu, które zawierają wartość. Na przykład data.Rok, Data.Miesiąc i data.Dzień lub pieniądze.Waluta i pieniądze.Kwota; lub PKT.X, Punkt.Y i Point.Z. należy również wziąć pod uwagę nadrzędny operator==, operator != , operator .
C) hashcode nie musi pozostać stały przez cały okres życia obiektu. Jednak musi pozostać niezmienny, podczas gdy uczestniczy jako klucz w hash. Od MSDN Doco for Dictionary: "dopóki obiekt jest używany jako klucz w słowniku)>), nie może się zmieniać w żaden sposób, który wpływa na jego wartość hash."Jeśli musisz zmienić wartość klucza usuń wpis ze słownika, zmień wartość klucza i zastąp wpis.
D) IMO, uprościsz swoje życie, jeśli obiekty wartości same są niezmienne.
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-05-04 21:06:59
Kiedy nadpisać object.GetHashCode()
?
As MSDN stwierdza:
Typy, które nadpisują równe muszą również nadpisać GetHashCode ; w przeciwnym razie Hashtable może nie działać poprawnie.
Powiązane linki:
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
2017-05-23 12:19:40
Na jakich polach bazować kod hash? Jeśli powinno być tylko na polach niezmiennych, co jeśli są tylko zmienne?
Nie musi być oparty tylko na niezmiennych polach. Oparłbym go na polach, które określają wynik metody equals.
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-01-14 13:34:04
Jak upewnić się, że kod hash pozostaje taki sam przez cały okres istnienia obiektu. (Właściwość MSDN #2) szczególnie, gdy równość jest oparta na polach mutowalnych. (MSDN Property #1)
Wygląda na to, że źle zrozumiałeś własność nr 2. Hashcode nie musi pozostawać taki sam w czasie życia obiektów. Po prostu musi pozostać taka sama, dopóki wartości, które określają wynik metody equals nie zostaną zmienione. Więc logicznie, bazujesz hashcode tylko na tych wartościach. Potem nie powinno być problemu.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-01-14 13:34:26
public override int GetHashCode()
{
return IntProp1 ^ IntProp2 ^ StrProp3.GetHashCode() ^ StrProp4.GetHashCode ^ CustomClassProp.GetHashCode;
}
Zrób to samo w metodzie customClass GetHasCode
. Działa jak urok.
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-05-01 00:34:53