Domyślna implementacja dla obiektu.GetHashCode()

Dla klasy, wartości domyślne są zasadniczo równością odniesienia, i to jest zwykle w porządku. Jeśli piszesz strukturę, bardziej powszechne jest nadpisywanie równości (zwłaszcza w celu uniknięcia boksu), ale i tak bardzo rzadko piszesz strukturę!

Gdy nadrzędna równość, zawsze powinieneś mieć pasujące Equals() i GetHashCode() (tj. dla dwóch wartości, jeśli Equals() zwraca true, to muszą zwrócić ten sam kod hash, ale konwersja jest , a nie wymagane) - i jest również powszechne, aby ==/!=operatorów, a często także do implementacji IEquatable<T>.

Do generowania kodu skrótu powszechnie używa się sumy wyliczonej, ponieważ pozwala to uniknąć kolizji na sparowanych wartościach - na przykład dla podstawowego 2 pola hash:

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 {1,2} nie jest taki sam jak hash {2,1}
• hash {1,1} nie jest taki sam jak hash {2,2}

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

Ponieważ nie mogłem znaleźć odpowiedzi, która wyjaśnia dlaczego powinniśmy nadpisać GetHashCode i Equals dla niestandardowych struktur i dlaczego Domyślna implementacja "prawdopodobnie nie będzie odpowiednia do użycia jako klucz w tabeli hash", zostawię link do tego posta na blogu , który wyjaśnia, dlaczego w prawdziwym przykładzie problemu, który się pojawił.

Polecam przeczytać cały post, ale tutaj jest podsumowanie (podkreślenie i wyjaśnienia dodano).

Powód domyślny hash dla struktur jest powolny i niezbyt dobry:

Sposób, w jaki CLR jest zaprojektowany, każde wywołanie do członka zdefiniowanego w typach System.ValueType lub System.Enum [może] powodować } przydział boksu [...]

Implementator funkcji hash stoi przed dylematem: zrobić dobry rozkład funkcji hash lub zrobić to szybko. W niektórych przypadkach możliwe jest osiągnięcie ich obu, ale jest to trudne do zrobienia ogólnie W ValueType.GetHashCode.

The kanoniczna funkcja skrótu struktury "łączy" kody skrótu wszystkich pól. Jednak jedynym sposobem uzyskania kodu hashowego pola w metodzie ValueType jest użycie reflection. Tak więc, autorzy CLR zdecydowali się na wymianę prędkości nad dystrybucją i domyślna wersja GetHashCode po prostu zwraca kod hash pierwszego pola non-null i "munges" go z identyfikatorem typu [...] To rozsądne zachowanie, chyba że nie. Na przykład Jeśli masz pecha i pierwsze pole swojej struktury ma tę samą wartość dla większości instancji, wtedy funkcja hash będzie dostarczać ten sam wynik przez cały czas. I, jak można sobie wyobrazić, spowoduje to drastyczny wpływ na wydajność, jeśli te wystąpienia są przechowywane w zestawie skrótów lub tabeli skrótów.

[...] implementacja oparta na refleksji jest powolna. Bardzo wolno.

[...] Zarówno ValueType.Equals jak i ValueType.GetHashCode mają specjalną optymalizację. Jeśli Typ nie ma "wskaźników" i jest odpowiednio zapakowany [...] następnie stosuje się bardziej optymalne wersje: GetHashCode iteruje nad instancją i blokami XORs po 4 bajty, a Metoda Equals porównuje dwie instancje za pomocą memcmp. [...] Ale optymalizacja jest bardzo trudna. Po pierwsze, trudno jest wiedzieć, kiedy optymalizacja jest włączona [...] Po drugie, porównanie pamięci niekoniecznie da właściwe wyniki . Oto prosty przykład: [...] -0.0 i +0.0 są równe, ale mają różne reprezentacje binarne.

Problem realny 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 krotka zawierająca 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 [empty string] . Wydajność była OK, dopóki liczba elementów w zestawie znacznie wzrosła, powodując rzeczywisty problem z wydajnością, co zajęło kilka minut zainicjowanie kolekcji z dziesiątkami tysięcy elementów.

Więc, aby odpowiedzieć na pytanie "w jakich przypadkach powinienem spakować własne i w jakich przypadkach mogę bezpiecznie polegaj na domyślnej implementacji", przynajmniej w przypadku struktur , powinieneś zastąpić Equals i GetHashCode, Gdy twoja niestandardowa struktura może być używana jako klucz w tabeli hash lub Dictionary.
Polecam również wdrożenie IEquatable<T> w tym przypadku, aby uniknąć boksu.

Jak mówiły inne odpowiedzi, jeśli piszesz klasę , domyślny hash przy użyciu równości referencji jest zwykle w porządku, więc nie zawracałbym sobie głowy w tym przypadku, chyba że musisz nadpisać Equals (wtedy trzeba by odpowiednio nadpisać GetHashCode).

Dokumentacja metody GetHashCode dla obiektu mówi "Domyślna implementacja tej metody nie może być używana jako unikalny identyfikator obiektu do celów hashowania." i 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 hash.".

Podstawowe typy danych, takie jak byte, short, int, long, char i string wdrożyć dobry Metoda GetHashCode. Niektóre inne klasy i struktury, jak na przykład Point, implementują metodę GetHashCode, 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 nadpisuje domyślną implementację, czy nie. Jeśli to nie nadpisuje, powinieneś użyć własnej implementacji. Dla dowolnych klas lub struktur, które tworzysz samodzielnie, gdzie musisz użyć metody GetHashCode, powinieneś stworzyć własną implementację, która używa odpowiednich elementów do obliczania kodu hashowego.

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

Equals jest używany podczas sprawdzania Foo A, B;

If (A == B)

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

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 tabele skrótów. Hashcode generowany przez Twoją klasę powinien być zawsze taki sam dla danej klasy stan.

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 życia obiektu, ale nie zgadzam się z tym (i pewnie się mylę).

Używając domyślnej implementacji dostarczonej przez object, chyba że masz takie samo odniesienie do jednej ze swoich klas, nie będą one sobie równe. Nadpisując Equals i GetHashCode, możesz zgłaszać równość na podstawie wartości wewnętrznych, a nie odniesienia do obiektów.

Jeśli masz do czynienia z POCOs, 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;
    }
}