Domyślna implementacja dla Object.GetHashCode ()

Jak działa domyślna implementacja GetHashCode()? I czy wystarczająco dobrze radzi sobie ze strukturami, klasami, tablicami itp.?

Próbuję zdecydować, w jakich przypadkach powinienem spakować własne iw jakich przypadkach mogę bezpiecznie polegać na domyślnej implementacji, aby dobrze się spisać. Nie chcę wymyślać koła na nowo, jeśli to w ogóle możliwe.

namespace System {
    public class Object {
        [MethodImpl(MethodImplOptions.InternalCall)]
        internal static extern int InternalGetHashCode(object obj);

        public virtual int GetHashCode() {
            return InternalGetHashCode(this);
        }
    }
}

InternalGetHashCode jest mapowane na funkcję ObjectNative :: GetHashCode w środowisku CLR, która wygląda następująco:

FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {  
    CONTRACTL  
    {  
        THROWS;  
        DISABLED(GC_NOTRIGGER);  
        INJECT_FAULT(FCThrow(kOutOfMemoryException););  
        MODE_COOPERATIVE;  
        SO_TOLERANT;  
    }  
    CONTRACTL_END;  

    VALIDATEOBJECTREF(obj);  

    DWORD idx = 0;  

    if (obj == 0)  
        return 0;  

    OBJECTREF objRef(obj);  

    HELPER_METHOD_FRAME_BEGIN_RET_1(objRef);        // Set up a frame  

    idx = GetHashCodeEx(OBJECTREFToObject(objRef));  

    HELPER_METHOD_FRAME_END();  

    return idx;  
}  
FCIMPLEND

Pełna implementacja GetHashCodeEx jest dość duża, więc łatwiej jest po prostu utworzyć link do kodu źródłowego C ++ .

W przypadku klasy wartości domyślne to zasadniczo równość odwołań i zwykle jest to w porządku. Pisząc strukturę, częściej zastępuje się równość (nie tylko w celu uniknięcia boksu), ale i tak bardzo rzadko piszesz strukturę!

Przesłaniając równość, zawsze powinieneś mieć dopasowanie Equals()i GetHashCode()(tj. Dla dwóch wartości, jeśli Equals()zwraca prawdę, muszą zwrócić ten sam kod skrótu, ale odwrotność nie jest wymagana) - i często podaje się również operatory ==/ !=, a często wdrożyć IEquatable<T>też.

Do generowania kodu skrótu często używa się sumy faktoryzowanej, ponieważ pozwala to uniknąć kolizji sparowanych wartości - na przykład dla podstawowego skrótu 2 pól:

unchecked // disable overflow, for the unlikely possibility that you
{         // are compiling with overflow-checking enabled
    int hash = 27;
    hash = (13 * hash) + field1.GetHashCode();
    hash = (13 * hash) + field2.GetHashCode();
    return hash;
}

Ma to tę zaletę, że:

• hash z {1,2} to nie to samo co hash z {2,1}
• hash {1,1} to nie to samo co hash {2,2}

etc - co może być powszechne, jeśli używa się tylko nieważonej sumy lub xor ( ^) itp.

Dokumentacja GetHashCodemetody dla Object mówi, że „domyślna implementacja tej metody nie może być używana jako unikalny identyfikator obiektu do celów mieszania”. a ten dla ValueType mówi „Jeśli wywołasz metodę GetHashCode typu pochodnego, wartość zwracana prawdopodobnie nie będzie odpowiednia do użycia jako klucz w tabeli skrótów”. .

Podstawowe typy danych, takich jak byte, short, int, long, chari stringwdrożyć metodę dobry GetHashCode. Niektóre inne klasy i struktury, jak Pointna przykład, implementują GetHashCodemetodę, która może, ale nie musi być odpowiednia dla twoich konkretnych potrzeb. Po prostu musisz go wypróbować, aby zobaczyć, czy jest wystarczająco dobry.

Dokumentacja dla każdej klasy lub struktury może powiedzieć, czy zastępuje domyślną implementację, czy nie. Jeśli to nie zastępuje, powinieneś użyć własnej implementacji. Dla wszystkich klas lub struktur, które tworzysz samodzielnie, w których musisz użyć GetHashCodemetody, powinieneś utworzyć własną implementację, która używa odpowiednich członków do obliczenia kodu skrótu.

Ponieważ nie mogłem znaleźć odpowiedzi, która wyjaśnia, dlaczego powinniśmy nadpisywać GetHashCodei Equalsdla struktur niestandardowych oraz dlaczego domyślna implementacja „prawdopodobnie nie będzie odpowiednia do użycia jako klucz w tablicy skrótów”, zostawię link do tego bloga post , który wyjaśnia, dlaczego na przykładzie rzeczywistego problemu, który się wydarzył.

Polecam przeczytanie całego posta, ale tutaj jest podsumowanie (podkreślenie i dodane wyjaśnienia).

Powód, dla którego domyślny skrót dla struktur jest powolny i niezbyt dobry:

Sposób zaprojektowania CLR, każde wywołanie członka zdefiniowanego w System.ValueTypelub System.Enumtypach [może] spowodować alokację boksów [...]

Osoba realizująca funkcję skrótu stoi przed dylematem: dokonać dobrej dystrybucji funkcji skrótu lub przyspieszyć. W niektórych przypadkach możliwe jest osiągnięcie obu, ale jest to trudne do zrobienia ogólnie w ValueType.GetHashCode.

Kanoniczna funkcja skrótu struktury „łączy” kody skrótów wszystkich pól. Ale jedynym sposobem uzyskania skrótu pola w ValueTypemetodzie jest użycie odbicia . Tak więc autorzy CLR zdecydowali się zamienić prędkość na dystrybucję i GetHashCodewersja domyślna po prostu zwraca kod skrótu pierwszego pola innego niż null i "łączy" go z identyfikatorem typu [...] Jest to rozsądne zachowanie, chyba że tak nie jest . Na przykład, jeśli masz pecha i pierwsze pole twojej struktury ma tę samą wartość dla większości instancji, funkcja skrótu będzie zawsze zapewniać ten sam wynik . I, jak możesz sobie wyobrazić, spowoduje to drastyczny wpływ na wydajność, jeśli te wystąpienia będą przechowywane w zestawie skrótów lub tabeli skrótów.

[...] Wdrażanie oparte na refleksji przebiega powoli . Bardzo wolno.

[…] Obie ValueType.Equalsi ValueType.GetHashCodemają specjalną optymalizację. Jeśli typ nie ma „wskaźników” i jest odpowiednio spakowany [...], wówczas używane są bardziej optymalne wersje: GetHashCodeiteruje po instancji i blokach XOR o wielkości 4 bajtów, a Equalsmetoda porównuje dwie instancje przy użyciu memcmp. […] Ale optymalizacja jest bardzo trudna. Po pierwsze, trudno jest stwierdzić, kiedy optymalizacja jest włączona [...] Po drugie, porównanie pamięci niekoniecznie da prawidłowe wyniki . Oto prosty przykład: [...] -0.0i +0.0są równe, ale mają różne reprezentacje binarne.

Rzeczywisty problem opisany w poście:

private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonly struct ErrorLocation
{
    // Empty almost all the time
    public string OptionalDescription { get; }
    public string Path { get; }
    public int Position { get; }
}

Użyliśmy krotki, która zawierała niestandardową strukturę z domyślną implementacją równości. I niestety, struktura miała opcjonalne pierwsze pole, które prawie zawsze było równe [pusty łańcuch] . Wydajność była OK, dopóki liczba elementów w zestawie nie wzrosła znacząco, powodując rzeczywisty problem z wydajnością, a zainicjowanie kolekcji z dziesiątkami tysięcy elementów zajmowało minuty.

Tak więc, aby odpowiedzieć na pytanie „w jakich przypadkach powinienem spakować swoją własną iw jakich przypadkach mogę bezpiecznie polegać na domyślnej implementacji”, przynajmniej w przypadku struktur , należy nadpisać Equalsi GetHashCodezawsze, gdy niestandardowa struktura może być używana jako klucz w tablicy skrótów lub Dictionary.
Poleciłbym również wdrożenie IEquatable<T>w tym przypadku, aby uniknąć boksu.

Jak powiedziały inne odpowiedzi, jeśli piszesz klasę , domyślny skrót używający równości odwołań jest zwykle w porządku, więc nie zawracałbym sobie w tym przypadku, chyba że musisz nadpisać Equals(wtedy musiałbyś odpowiednio nadpisać GetHashCode).

Ogólnie rzecz biorąc, jeśli zastępujesz Equals, chcesz zastąpić GetHashCode. Powodem tego jest to, że oba są używane do porównywania równości twojej klasy / struktury.

Równe jest używane podczas sprawdzania Foo A, B;

jeśli (A == B)

Ponieważ wiemy, że wskaźnik prawdopodobnie nie będzie pasował, możemy porównać elementy wewnętrzne.

Equals(obj o)
{
    if (o == null) return false;
    MyType Foo = o as MyType;
    if (Foo == null) return false;
    if (Foo.Prop1 != this.Prop1) return false;

    return Foo.Prop2 == this.Prop2;
}

GetHashCode jest zwykle używany przez tablice skrótów. Kod skrótu wygenerowany przez twoją klasę powinien zawsze być taki sam dla klas podanych w stanie.

Zazwyczaj tak

GetHashCode()
{
    int HashCode = this.GetType().ToString().GetHashCode();
    HashCode ^= this.Prop1.GetHashCode();
    etc.

    return HashCode;
}

Niektórzy powiedzą, że hashcode powinien być obliczany tylko raz na okres istnienia obiektu, ale ja się z tym nie zgadzam (i prawdopodobnie się mylę).

Używając domyślnej implementacji dostarczonej przez obiekt, o ile nie masz tego samego odwołania do jednej z twoich klas, nie będą one sobie równe. Zastępując Equals i GetHashCode, możesz zgłosić równość na podstawie wartości wewnętrznych, a nie odwołań do obiektów.

Jeśli masz do czynienia tylko z POCO, możesz użyć tego narzędzia, aby nieco uprościć swoje życie:

var hash = HashCodeUtil.GetHashCode(
           poco.Field1,
           poco.Field2,
           ...,
           poco.FieldN);

...

public static class HashCodeUtil
{
    public static int GetHashCode(params object[] objects)
    {
        int hash = 13;

        foreach (var obj in objects)
        {
            hash = (hash * 7) + (!ReferenceEquals(null, obj) ? obj.GetHashCode() : 0);
        }

        return hash;
    }
}