Domyślna implementacja dla Object.GetHashCode ()

162

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.

Fung
źródło
Spójrz na komentarz, który zostawiłem w artykule: stackoverflow.com/questions/763731/gethashcode-extension-method
Paul Westcott.
34
Poza tym: możesz uzyskać domyślny kod skrótu (nawet jeśli GetHashCode()został zastąpiony), używającSystem.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(obj)
Marc Gravell
@MarcGravell dziękuję za wkład, szukałem dokładnie tej odpowiedzi.
Andrew Savinykh,
@MarcGravell Ale jak mam to zrobić inną metodą?
Tomáš Zato - Przywróć Monikę

Odpowiedzi:

86
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 ++ .

David Brown
źródło
5
Ten cytat z dokumentacji musiał pochodzić z bardzo wczesnej wersji. Nie jest już tak napisane w aktualnych artykułach MSDN, prawdopodobnie dlatego, że jest całkiem błędne.
Hans Passant
4
Zmienili sformułowanie, tak, ale w zasadzie nadal jest to to samo: „W związku z tym domyślna implementacja tej metody nie może być używana jako unikalny identyfikator obiektu do celów mieszania”.
David Brown
7
Dlaczego w dokumentacji podano, że implementacja nie jest szczególnie przydatna do haszowania? Jeśli obiekt jest sobie równy i nic innego, jakakolwiek metoda kodu skrótu, która zawsze zwraca tę samą wartość dla danej instancji obiektu i generalnie zwraca różne wartości dla różnych instancji, na czym polega problem?
supercat
3
@ ta.speot.is: Jeśli chcesz ustalić, czy dana instancja została już dodana do słownika, równość odwołań jest idealna. W przypadku łańcuchów, jak zauważyłeś, zwykle bardziej interesuje Cię to, czy ciąg zawierający tę samą sekwencję znaków został już dodany. Dlatego stringzastępuje GetHashCode. Z drugiej strony załóżmy, że chcesz zliczać, ile razy różne kontrolki przetwarzają Paintzdarzenia. Możesz użyć Dictionary<Object, int[]>(każdy int[]przechowywany może pomieścić dokładnie jeden przedmiot).
supercat
6
@ It'sNotALie. Następnie podziękuj Archive.org za posiadanie kopii ;-)
RobIII
88

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.

Marc Gravell
źródło
Doskonała uwaga na temat korzyści płynących z algorytmu sumy faktoryzowanej; coś, czego wcześniej nie zdawałem sobie sprawy!
Loophole,
Czy suma faktoryzowana (jak napisano powyżej) nie spowoduje sporadycznie wyjątków dotyczących przepełnienia?
sinelaw
4
@sinelaw tak, należy to wykonać unchecked. Na szczęście uncheckedjest to opcja domyślna w C #, ale lepiej byłoby to wyraźnie określić; edytowany
Marc Gravell
7

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.

Guffa
źródło
2
Nie zgadzam się, że powinieneś rutynowo dodawać własną implementację. Po prostu ogromna większość klas (w szczególności) nigdy nie zostanie przetestowana pod kątem równości - lub jeśli są, wbudowana równość referencyjna jest w porządku. W (już rzadkiej) okazji pisania struktury byłoby to bardziej powszechne, prawda.
Marc Gravell
@Marc Gravel: Oczywiście nie to miałem na myśli. Dostosuję ostatni akapit. :)
Guffa
Podstawowe typy danych nie implementują dobrej metody GetHashCode, przynajmniej w moim przypadku. Na przykład GetHashCode for int zwraca samą liczbę: (123) .GetHashCode () zwraca 123.
fdermishin
5
@ user502144 A co w tym złego? To doskonały, unikalny identyfikator, który jest łatwy do obliczenia, bez fałszywych trafień dotyczących równości ...
Richard Rast
@Richard Rast: W porządku, z wyjątkiem tego, że klucze mogą być źle dystrybuowane, gdy są używane w tablicy z haszowaniem. Spójrz na tę odpowiedź: stackoverflow.com/a/1388329/502144
fdermishin
5

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).

geekley
źródło
1

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.

Bennett Dill
źródło
2
Podejście ^ = nie jest szczególnie dobrym podejściem do generowania skrótu - zwykle prowadzi do wielu typowych / przewidywalnych kolizji - na przykład jeśli Prop1 = Prop2 = 3.
Marc Gravell
Jeśli wartości są takie same, nie widzę problemu z kolizją, ponieważ obiekty są równe. Jednak 13 * Hash + NewHash wydaje się interesujący.
Bennett Dill
2
Ben: spróbuj dla Obj1 {Prop1 = 12, Prop2 = 12} i Obj2 {Prop1 = 13, Prop2 = 13}
Tomáš Kafka
0

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;
    }
}
Daniel Marshall
źródło