Dlaczego jest ValueType.GetHashCode () zaimplementowane tak jak jest?

Rzeczywista implementacja ValueType.GetHashCode() nie do końca pasuje do komentarza. Ma dwie wersje algorytmu, szybką i powolną. Najpierw sprawdza, czy struktura zawiera jakiekolwiek elementy typu reference i czy pomiędzy polami jest jakieś wypełnienie. Padding jest pustą przestrzenią w wartości struktury, utworzoną podczas wyrównywania pól przez kompilator JIT. W strukturze, która zawiera bool i int (3 bajty) jest padding, ale nie ma padding, gdy zawiera int i int, pasują idealnie razem.

Bez referencji i bez wypełnienia, może wykonać szybką wersję, ponieważ każdy bit w wartości struktury jest bitem należącym do wartości pola. Po prostu xors 4 bajty na raz. Otrzymasz "dobry" kod hashowy, który uwzględnia wszystkich członków. Wiele prostych typów struktur w. NET Framework zachowuje się w ten sposób, jak punkt i rozmiar.

Nie zdając tego testu, robi powolną wersję, moralny odpowiednik refleksji. To właśnie dostajesz, Twój KeyValuePair zawiera referencje. A ten sprawdza tylko pole pierwszego kandydata, tak jak w komentarzu. Jest to z pewnością optymalizacja perf, unikając spalania zbyt dużo czasu.

Tak, paskudny szczegół i mało znany. Jest to zwykle odkrywane, gdy ktoś zauważa, że ich kod kolekcji ssie błoto.

Jeszcze jeden potworny szczegół: wersja fast ma błąd, który bajtuje, gdy struktura zawiera pole typu decimal. Wartości 12m i 12,0 m są logicznie równe, ale nie mają ten sam wzór bitowy. GetHashCode() powie, że nie są sobie równe. AUĆ.

Powinien być zgodny z umową GetHashCode, nawet jeśli kolejność pól się zmieni: równe wartości będą miały równe kody hash w ciągu całego życia tego procesu.

W szczególności:

• nie równe wartości nie muszą mieć nie równe kody hash
• kody Hash nie muszą być spójne w różnych procesach (możesz zmienić implementację, odbudować i wszystko powinno nadal działać - zasadniczo nie powinieneś utrzymywać kodów hash)

Teraz nie mówię, że Implementacja ValueType jest świetnym pomysłem - spowoduje to spadek wydajności na różne sposoby... ale nie wydaje mi się, żeby to było naprawdę zepsute.

Każda implementacja GetHashCode() ma swoje plusy i minusy. Są to oczywiście rzeczy, które rozważamy podczas wdrażania naszych własnych, ale w przypadku ValueType.GetHashCode() istnieje szczególna trudność w tym, że nie mają zbyt wielu informacji na temat rzeczywistych szczegółów konkretnego typu będą. Oczywiście często zdarza się to nam, gdy tworzymy klasę abstrakcyjną lub taką, która ma być bazą klas, które dodadzą o wiele więcej pod względem stanu, ale w tych przypadkach mamy oczywistą rozwiązanie polegające na użyciu domyślnej implementacji object.GetHashCode(), chyba że klasa pochodna dba o jej nadpisanie.

Z ValueType.GetHashCode() nie mają tego luksusu, ponieważ podstawową różnicą między typem wartości a typem referencyjnym jest, pomimo popularności mówienia o szczegółach implementacji stosu vs. sterty, fakt, że dla równoważności typu wartości odnosi się do wartości, podczas gdy dla równoważności typu obiektu odnosi się do tożsamości (nawet jeśli obiekt definiuje inną formę równoważności przez nadrzędne Equals() i GetHashCode() pojęcie równości odniesienia nadal istnieje i jest nadal użyteczne.

Tak więc, dla metody Equals() implementacja jest oczywista; sprawdź, czy oba obiekty są tego samego typu, a jeśli tak, sprawdź również, czy wszystkie pola są równe (w rzeczywistości istnieje optymalizacja, która w niektórych przypadkach wykonuje bitowe porównanie, ale jest to optymalizacja na tej samej podstawowej idei).

Co zrobić dla GetHashCode()? Po prostu nie ma idealnego rozwiązania. Mogą zrobić tylko kilka rodzaj mult-then-add lub shift-then-xor na każdym polu. Prawdopodobnie dałoby to całkiem dobry hashcode, ale mogłoby być drogie, gdyby było dużo pól (nieważne, że nie zaleca się posiadania typów wartości, które mają wiele pól, wykonawca musi wziąć pod uwagę, że nadal mogą, a nawet mogą być czasy, w których ma to sens, chociaż szczerze nie mogę sobie wyobrazić czasu, w którym zarówno ma to sens, jak i ma również sens, aby go hashować). Gdyby wiedzieli, że niektóre pola rzadko się różnią między instancjami mogą ignorować te pola i nadal mają całkiem dobry hashcode, a jednocześnie są dość szybkie. Na koniec mogą ignorować większość pól i mieć nadzieję, że te, których nie ignorują, przez większość czasu różnią się wartością. Wybrali najbardziej ekstremalną wersję tego ostatniego.

(kwestia tego, co się robi, gdy nie ma pól instancji, to inna sprawa i całkiem dobry wybór, takie typy wartości są równe wszystkim innym instancjom tego samego typu i mają hashcode, który pasuje do tego).

Jest to więc implementacja, która jest do bani, jeśli hashujesz wiele wartości, gdzie pierwsze pole jest takie samo( lub w inny sposób zwraca ten sam hashcode), ale inne implementacje byłyby do bani w innych przypadkach(Mono idzie na xoring wszystkich hashcodów pól razem, lepiej w Twoim przypadku, gorzej w innych).

Kwestia zmiany kolejności pól nie ma znaczenia, ponieważ hashcode jest wyraźnie określony jako ważny tylko przez cały okres istnienia procesu i nie jest nadaje się do większości przypadków, w których mogą być utrzymywane poza tym (może być przydatny w niektórych sytuacjach buforowania, gdzie nie boli, jeśli rzeczy nie zostaną znalezione poprawnie po zmianie kodu).

public class KVPCmp<TKey, TValue> : IEqualityComparer<KeyValuePair<TKey, TValue>>, IEqualityComparer
{
  bool IEqualityComparer.Equals(object x, object y)
  {
      if(x == null)
        return y == null;
      if(y == null)
        return false;
      if(!(x is KeyValuePair<TKey, TValue>) || !(y is KeyValuePair<TKey, TValue>))
        throw new ArgumentException("Comparison of KeyValuePairs only.");
      return Equals((KeyValuePair<TKey, TValue>) x, (KeyValuePair<TKey, TValue>) y);
  }
  public bool Equals(KeyValuePair<TKey, TValue> x, KeyValuePair<TKey, TValue> y)
  {
      return x.Key.Equals(y.Key) && x.Value.Equals(y.Value);
  }
  public int GetHashCode(KeyValuePair<TKey, TValue> obj)
  {
      int keyHash = obj.GetHashCode();
      return ((keyHash << 16) | (keyHash >> 16)) ^ obj.Value.GetHashCode();
  }
  public int GetHashCode(object obj)
  {
      if(obj == null)
        return 0;
      if(!(obj is KeyValuePair<TKey, TValue>))
       throw new ArgumentException();
      return GetHashCode((KeyValuePair<TKey, TValue>)obj);
  }
}

Użyj tego jako komparatora podczas tworzenia słownika, a wszystko powinno być dobrze (ty trzeba tylko generycznych metod porównawczych naprawdę, ale pozostawienie reszty nie szkodzi i może być przydatne czasami).

Dziękuję wszystkim za bardzo, bardzo pouczające odpowiedzi. Wiedziałem, że w tej decyzji musi być jakieś uzasadnienie, ale chciałbym, żeby była lepiej udokumentowana. Nie jestem w stanie użyć V4 frameworka, więc nie ma Tuple<>, i to był główny powód, dla którego zdecydowałem się użyć KeyValuePair struct. Ale myślę, że nie ma żadnych skrótów i będę musiał toczyć własne. Jeszcze raz dziękuję wszystkim.