Wytyczne dotyczące GetHashCode w języku C #

W książce Essential C # 3.0 i .NET 3.5 przeczytałem, że:

Zwroty GetHashCode () przez cały okres istnienia obiektu powinny być stałe (ta sama wartość), nawet jeśli dane obiektu ulegają zmianie. W wielu przypadkach należy buforować metodę powrotu, aby to wymusić.

Czy to ważna wskazówka?

Wypróbowałem kilka typów wbudowanych w .NET i nie zachowywały się w ten sposób.

W większości przypadków jest to ważna wskazówka, ale być może nie jest to ważna zasada. Nie opowiada też całej historii.

Chodzi o to, że w przypadku typów zmiennych nie można oprzeć kodu skrótu na zmiennych danych, ponieważ dwa równe obiekty muszą zwracać ten sam kod skrótu, a kod skrótu musi być ważny przez cały okres istnienia obiektu. Jeśli kod skrótu ulegnie zmianie, otrzymasz obiekt, który zostanie utracony w zahaszowanej kolekcji, ponieważ nie znajduje się już we właściwym koszu.

Na przykład obiekt A zwraca hash o wartości 1. Tak więc trafia do pojemnika 1 tablicy skrótów. Następnie zmieniasz obiekt A tak, aby zwracał hash równy 2. Kiedy tablica haszująca szuka go, szuka go w bin 2 i nie może go znaleźć - obiekt jest osierocony w bin 1. Dlatego kod skrótu musi nie zmienia się przez cały okres istnienia obiektu i jest tylko jednym z powodów, dla których pisanie implementacji GetHashCode jest uciążliwe.

Aktualizacja
Eric Lippert opublikował blog, który zawiera doskonałe informacje na temat GetHashCode.

Dodatkowa aktualizacja
Dokonałem kilku zmian powyżej:

1. Dokonałem rozróżnienia między wskazówką a regułą.
2. Udało mi się przekreślić „na całe życie obiektu”.

Wytyczna to tylko przewodnik, a nie reguła. W rzeczywistości GetHashCodenależy postępować zgodnie z tymi wytycznymi tylko wtedy, gdy rzeczy oczekują, że obiekt będzie postępował zgodnie z wytycznymi, na przykład gdy jest przechowywany w tabeli skrótów. Jeśli nigdy nie zamierzasz używać swoich obiektów w tabelach skrótów (lub czegokolwiek innego, co opiera się na regułach GetHashCode), Twoja implementacja nie musi przestrzegać wytycznych.

Kiedy widzisz „przez cały okres istnienia obiektu”, powinieneś przeczytać „przez czas, przez jaki obiekt potrzebuje współpracować z tablicami skrótów” lub podobnym. Jak większość rzeczy, GetHashCodepolega na tym, aby wiedzieć, kiedy złamać zasady.

Minęło dużo czasu, ale myślę, że nadal konieczne jest udzielenie poprawnej odpowiedzi na to pytanie, w tym wyjaśnień, dlaczego i jak. Jak dotąd najlepszą odpowiedzią jest ta, która wyczerpująco przytacza MSDN - nie próbuj tworzyć własnych reguł, ludzie z MS wiedzieli, co robią.

Ale najpierw sprawa: Wytyczne cytowane w pytaniu są błędne.

A teraz dlaczego - jest ich dwóch

Po pierwsze, dlaczego : Jeśli hashcode jest obliczany w taki sposób, że nie zmienia się w czasie życia obiektu, nawet jeśli sam obiekt się zmienia, to zrywałoby to kontrakt równości.

Pamiętaj: „Jeśli dwa obiekty są porównywane jako równe, metoda GetHashCode dla każdego obiektu musi zwracać tę samą wartość. Jeśli jednak dwa obiekty nie są porównywane jako równe, metody GetHashCode dla dwóch obiektów nie muszą zwracać różnych wartości”.

Drugie zdanie jest często błędnie interpretowane jako „Jedyną zasadą jest to, że w czasie tworzenia obiektu hashcode równych obiektów musi być równy”. Naprawdę nie wiem dlaczego, ale to jest także istota większości odpowiedzi tutaj.

Pomyśl o dwóch obiektach zawierających nazwę, których nazwa jest używana w metodzie equals: Ta sama nazwa -> ta sama rzecz. Utwórz instancję A: Imię = Joe Utwórz instancję B: Imię = Piotr

Hashcode A i Hashcode B najprawdopodobniej nie będą takie same. Co by się stało, gdyby nazwa instancji B została zmieniona na Joe?

Zgodnie z wytyczną z pytania, kod skrótu B nie ulegnie zmianie. Wynikiem tego byłoby: A.Equals (B) ==> true Ale w tym samym czasie: A.GetHashCode () == B.GetHashCode () ==> false.

Ale dokładnie to zachowanie jest wyraźnie zabronione przez kontrakt equals & hashcode.

Po drugie : chociaż jest - oczywiście - prawdą, że zmiany w kodzie skrótu mogą uszkodzić listy zaszyfrowane i inne obiekty korzystające z kodu skrótu, prawdą jest również odwrotna sytuacja. Brak zmiany kodu skrótu spowoduje w najgorszym przypadku zahaszowane listy, w których wiele różnych obiektów będzie miało ten sam kod skrótu i ​​dlatego będzie znajdować się w tym samym koszu - ma to miejsce, gdy na przykład obiekty są inicjowane ze standardową wartością.

A teraz dochodzę do pytań Cóż, na pierwszy rzut oka wydaje się, że jest sprzeczność - tak czy inaczej, kod się zepsuje. Ale żaden problem nie wynika ze zmienionego lub niezmienionego hashcode.

Źródło problemów jest dobrze opisane w MSDN:

Z pozycji hashtable MSDN:

Kluczowe obiekty muszą być niezmienne, o ile są używane jako klucze w tablicy z haszowaniem.

To znaczy:

Każdy obiekt, który tworzy wartość skrótu, powinien zmienić wartość skrótu, gdy zmienia się obiekt, ale nie może - absolutnie nie może - zezwalać na jakiekolwiek zmiany w sobie samym, gdy jest używany wewnątrz tablicy z haszowaniem (lub oczywiście dowolnego innego obiektu używającego skrótu) .

Po pierwsze, jak najłatwiej byłoby oczywiście zaprojektować niezmienne obiekty tylko do użytku w tabelach skrótów, które w razie potrzeby będą tworzone jako kopie normalnych, zmiennych obiektów. Wewnątrz niezmiennych obiektów można oczywiście buforować kod skrótu, ponieważ jest on niezmienny.

Drugi sposób Lub nadaj obiektowi flagę „jesteś teraz zaszyfrowany”, upewnij się, że wszystkie dane obiektu są prywatne, sprawdź flagę we wszystkich funkcjach, które mogą zmieniać dane obiektu i wyrzuć dane wyjątku, jeśli zmiana jest niedozwolona (np. Flaga jest ustawiona ). Teraz, kiedy umieścisz obiekt w jakimkolwiek zakodowanym obszarze, upewnij się, że ustawiłeś flagę i - także - odznacz flagę, gdy nie jest już potrzebna. Dla ułatwienia radziłbym ustawić flagę automatycznie w metodzie „GetHashCode” - w ten sposób nie można o tym zapomnieć. A jawne wywołanie metody „ResetHashFlag” upewni się, że programista będzie musiał pomyśleć, czy ma, czy nie ma prawa zmieniać danych obiektu.

Ok, co też należy powiedzieć: są przypadki, w których możliwe jest posiadanie obiektów ze zmiennymi danymi, w których hashcode jest mimo to niezmieniony, gdy dane obiektów są zmieniane, bez naruszenia kontraktu equals & hashcode.

Wymaga to jednak, aby metoda równości nie była również oparta na zmiennych danych. Tak więc, jeśli napiszę obiekt i utworzę metodę GetHashCode, która oblicza wartość tylko raz i przechowuje ją wewnątrz obiektu, aby zwrócić ją w późniejszych wywołaniach, muszę ponownie: absolutnie muszę utworzyć metodę Equals, która będzie używać przechowywane wartości do porównania, aby A.Equals (B) również nigdy nie zmieniło się z fałszu na prawdę. W przeciwnym razie umowa zostałaby zerwana. Rezultatem tego będzie zwykle to, że metoda Equals nie ma żadnego sensu - to nie jest oryginalne odniesienie równe, ale nie jest to również wartość równa. Czasami może to być zamierzone zachowanie (np. Zapisy klientów), ale zwykle tak nie jest.

Tak więc, po prostu zmień wynik GetHashCode, gdy zmienią się dane obiektu i jeśli użycie obiektu wewnątrz skrótu przy użyciu list lub obiektów jest zamierzone (lub po prostu możliwe), uczyń obiekt albo niezmiennym, albo stwórz flagę tylko do odczytu do użycia dla czas życia zaszyfrowanej listy zawierającej obiekt.

(Nawiasem mówiąc: wszystko to nie jest specyficzne dla C # ani .NET - z natury wszystkich implementacji z hashtagami lub bardziej ogólnie każdej listy indeksowanej wynika, że ​​dane identyfikacyjne obiektów nigdy nie powinny się zmieniać, gdy obiekt znajduje się na liście . Nieoczekiwane i nieprzewidywalne zachowanie nastąpi, jeśli ta reguła zostanie złamana. Gdzieś mogą istnieć implementacje list, które monitorują wszystkie elementy na liście i automatycznie reindeksują listę - ale wydajność tych z pewnością będzie w najlepszym przypadku makabryczna.)

Z MSDN

Jeśli dwa obiekty są porównywane jako równe, metoda GetHashCode dla każdego obiektu musi zwracać tę samą wartość. Jeśli jednak dwa obiekty nie są porównywane jako 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 stanu obiektu, który określa wartość zwracaną przez metodę Equals obiektu. Należy zauważyć, że dotyczy to tylko bieżącego wykonywania aplikacji i że można zwrócić inny kod skrótu, jeśli aplikacja zostanie ponownie uruchomiona.

Aby uzyskać najlepszą wydajność, funkcja skrótu musi generować losowy rozkład dla wszystkich danych wejściowych.

Oznacza to, że jeśli wartość (wartości) obiektu ulegną zmianie, kod skrótu powinien ulec zmianie. Na przykład klasa „Person” z właściwością „Name” ustawioną na „Tom” powinna mieć jeden kod skrótu i ​​inny, jeśli zmienisz nazwę na „Jerry”. W przeciwnym razie Tom == Jerry, co prawdopodobnie nie jest tym, co chciałbyś.

Edycja :

Również z MSDN:

Klasy pochodne, które przesłaniają GetHashCode, muszą również przesłonić Equals, aby zagwarantować, że dwa obiekty uważane za równe mają ten sam kod skrótu; w przeciwnym razie typ Hashtable może nie działać poprawnie.

Z pozycji hashtable MSDN :

Kluczowe obiekty muszą być niezmienne, o ile są używane jako klucze w tablicy z haszowaniem.

Sposób, w jaki to czytam, jest taki, że zmienne obiekty powinny zwracać różne kody skrótu, gdy zmieniają się ich wartości, chyba że są przeznaczone do użycia w tablicy haszującej.

W przykładzie System.Drawing.Point, obiekt jest zmienne i nie zwracają różne hashcode gdy zmienia X lub Y wartości. To sprawiłoby, że byłby słabym kandydatem do użycia w takiej postaci, w jakiej jest w tablicy haszującej.

Myślę, że dokumentacja dotycząca GetHashcode jest nieco zagmatwana.

Z jednej strony MSDN stwierdza, że ​​hashcode obiektu nigdy nie powinien się zmieniać i być stały. Z drugiej strony MSDN stwierdza również, że wartość zwracana przez GetHashcode powinna być równa 2 obiektom, jeśli te 2 obiekty są uważane za równe.

MSDN:

Funkcja skrótu musi mieć następujące właściwości:

• Jeśli dwa obiekty są porównywane jako równe, metoda GetHashCode dla każdego obiektu musi zwracać tę samą wartość. Jeśli jednak dwa obiekty nie są porównywane jako 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 stanu obiektu, który określa wartość zwracaną przez metodę Equals obiektu. Należy zauważyć, że dotyczy to tylko bieżącego wykonywania aplikacji i że można zwrócić inny kod skrótu, jeśli aplikacja zostanie ponownie uruchomiona.
• Aby uzyskać najlepszą wydajność, funkcja skrótu musi generować losowy rozkład dla wszystkich danych wejściowych.

Oznacza to, że wszystkie obiekty powinny być niezmienne lub metoda GetHashcode powinna być oparta na niezmiennych właściwościach obiektu. Załóżmy na przykład, że masz tę klasę (naiwna implementacja):

public class SomeThing
{
      public string Name {get; set;}

      public override GetHashCode()
      {
          return Name.GetHashcode();
      }

      public override Equals(object other)
      {
           SomeThing = other as Something;
           if( other == null ) return false;
           return this.Name == other.Name;
      }
}

Ta implementacja już narusza reguły, które można znaleźć w MSDN. Załóżmy, że masz 2 wystąpienia tej klasy; właściwość Name instancji instancja1 jest ustawiona na „Pol”, a właściwość Name instancji instancja2 jest ustawiona na „Piet”. Obie instancje zwracają inny kod skrótu, ale też nie są równe. Teraz załóżmy, że zmieniam nazwę instancji2 na 'Pol', a następnie zgodnie z moją metodą Equals obie instancje powinny być równe i zgodnie z jedną z reguł MSDN powinny zwrócić ten sam kod skrótu.
Jednak nie można tego zrobić, ponieważ kod skrótu instancji2 ulegnie zmianie, a MSDN stwierdza, że ​​jest to niedozwolone.

Następnie, jeśli masz encję, możesz zaimplementować kod skrótu, aby używał „podstawowego identyfikatora” tej jednostki, który może być idealnie kluczem zastępczym lub niezmienną własnością. Jeśli masz obiekt wartości, możesz zaimplementować kod Hashcode tak, aby używał „właściwości” tego obiektu wartości. Te właściwości tworzą „definicję” obiektu wartości. Taka jest oczywiście natura przedmiotu wartości; nie interesuje cię jego tożsamość, ale raczej jej wartość.
Dlatego obiekty wartości powinny być niezmienne. (Podobnie jak we frameworku .NET, string, Date itp ... są niezmiennymi obiektami).

Kolejna rzecz, która przychodzi mi na myśl:
podczas której „sesji” (nie wiem, jak mam to nazwać), „GetHashCode” powinien zwracać stałą wartość. Załóżmy, że otwierasz aplikację, ładujesz wystąpienie obiektu z bazy danych (encji) i pobierasz jego kod skrótu. Zwróci określoną liczbę. Zamknij aplikację i załaduj tę samą jednostkę. Czy wymagane jest, aby hashcode tym razem miał taką samą wartość, jak podczas ładowania jednostki po raz pierwszy? IMHO, nie.

To jest dobra rada. Oto, co Brian Pepin ma do powiedzenia w tej sprawie:

To mnie zaskoczyło więcej niż raz: upewnij się, że GetHashCode zawsze zwraca tę samą wartość przez cały okres istnienia instancji. Pamiętaj, że kody skrótów są używane do identyfikowania „zasobników” w większości implementacji z możliwością mieszania. Jeśli „zasobnik” obiektu ulegnie zmianie, tablica hashy może nie być w stanie znaleźć Twojego obiektu. Błędy te mogą być bardzo trudne do znalezienia, więc zrób to dobrze za pierwszym razem.

Nie odpowiadając bezpośrednio na twoje pytanie, ale - jeśli używasz Resharper, nie zapominaj, że ma on funkcję, która generuje dla Ciebie rozsądną implementację GetHashCode (a także metodę Equals). Możesz oczywiście określić, którzy członkowie klasy będą brani pod uwagę podczas obliczania hashcode.

Sprawdź ten post na blogu Marca Brooksa:

VTO, RTO i GetHashCode () - ojej!

A następnie zapoznaj się z postem uzupełniającym (nie mogę połączyć, ponieważ jestem nowy, ale jest łącze w artykule początkowym), który omawia dalej i obejmuje drobne niedociągnięcia w początkowej implementacji.

To było wszystko, co musiałem wiedzieć o tworzeniu implementacji GetHashCode (). Zapewnił nawet pobranie swojej metody wraz z kilkoma innymi narzędziami, w skrócie złota.

Hashcode nigdy się nie zmienia, ale ważne jest również, aby zrozumieć, skąd pochodzi Hashcode.

Jeśli twój obiekt używa semantyki wartości, tj. Tożsamość obiektu jest zdefiniowana przez jego wartości (np. String, Color, wszystkie struktury). Jeśli tożsamość twojego obiektu jest niezależna od wszystkich jego wartości, to Hashcode jest identyfikowany przez podzbiór jego wartości. Na przykład wpis StackOverflow jest przechowywany gdzieś w bazie danych. Jeśli zmienisz swoje imię i nazwisko lub adres e-mail, wpis klienta pozostanie taki sam, chociaż niektóre wartości uległy zmianie (ostatecznie zazwyczaj identyfikuje Cię długi identyfikator klienta #).

Krótko mówiąc:

Semantyka typu wartości - Hashcode jest definiowany przez wartości Semantyka typu odwołania - Hashcode jest definiowany przez jakiś identyfikator

Sugeruję, abyś przeczytał Domain Driven Design autorstwa Erica Evansa, w którym zajmuje się on podmiotami i typami wartości (co jest mniej więcej tym, co próbowałem zrobić powyżej), jeśli to nadal nie ma sensu.

Sprawdź Wytyczne i zasady dotyczące GetHashCode autorstwa Erica Lipperta