Zine.net online

Witaj na Zine.net online Zaloguj się | Rejestracja | Pomoc
w Szukaj

mgrzeg.net - Admin on Rails :)

GetHashCode

W poprzedniej notce pisałem o implementacji lock’a i do zilustrowania pewnych szczegółów użyłem metody GetHashCode analizowanego obiektu. Tym razem przyjrzymy się bliżej samej metodzie GetHashCode, dziedziczonej przez wszystkie klasy z bazowej klasy Object i często traktowanej po macoszemu, lub też bez właściwego zrozumienia. Niestety potrafi się to zemścić, a w jaki sposób, to spróbuję za chwilę zademonstrować, po czym postaram się podać kilka rad co z tym fantem począć.

O tym, że metoda GetHashCode jest ważna mogliśmy przekonać się już poprzednio, gdy okazało się, że CLR zapisuje wynik jej działania w bloku synchronizacji obiektu. Dorzućmy do tego fakt, że jest jedną z czterech metod dziedziczonych po object’cie (obok ToString, Equals oraz Finalize), którą klasa może przykryć własną implementacją, a już widać, że żartów nie ma.

Lekcja 1 GetHashCode a Hashtable

Utwórzmy sobie dla przykładu następującą klasę:
public class HashPerson
{
 string _firstName;
 string _lastName;
 public HashPerson(string first, string last)
 {
    _firstName = first;
    _lastName = last;
 }
 public override bool Equals(object obj)
 {
    HashPerson hd = obj as HashPerson;
    if (hd != null) return (hd._firstName == _firstName && hd._lastName == _lastName);
    else return false;
 }
 public override int GetHashCode()
 {
    return string.Concat(_firstName, _lastName).GetHashCode();
 }
}

Dorzućmy do tego przykładowy kod testujący:
public static void Main(string[] args)
{
 Hashtable ht = new Hashtable();
 HashPerson personA = new HashPerson("ala", "kot");
 HashPerson personB = new HashPerson("ala", "kot");
 HashPerson personC = new HashPerson("ola", "pies");
 Console.WriteLine("personA == personB = {0}", personA.Equals(personB));
 Console.WriteLine("personA == personC = {0}", personA.Equals(personC));
 Console.WriteLine("personA == personA = {0}", personA.Equals(personA));
 ht[personA] = personA;
 ht[personB] = personB;
 ht[personC] = personC;

 Console.WriteLine(ht.Count);
}

Uruchamiamy program i w wyniku otrzymujemy:

>HashPerson.exe
personA == personB = True
personA == personC = False
personA == personA = True
Number of elements: 2

Teraz zmodyfikujmy nieznacznie kod metody GetHashCode naszej klasy HashPerson i zamiast
public override int GetHashCode()
{
  return string.Concat(_firstName, _lastName).GetHashCode();
}

napiszmy
public override int GetHashCode()
{
    return base.GetHashCode();
}

Ponownie uruchamiamy program i tym razem w wyniku dostajemy:

>HashPerson.exe
personA == personB = True
personA == personC = False
personA == personA = True
Number of elements: 3

Dwa różne wyniki! Mimo, iż mamy Identyczny kod metody Equals w obu scenariuszach, za pierwszym razem tablica haszująca zawierała tylko 2 elementy, za drugim natomiast - 3.
Ktoś może w tym miejscu powiedzieć: "E, co mi tam - nie korzystam z Hashtable w swoim kodzie, problem mnie nie dotyczy". No cóż - możesz nawet nie wiedzieć, że korzystasz... A z LINQ korzystasz? Jeśli tak, to czytaj dalej :)

Lekcja 2 GetHashCode a LINQ

Do klasy z poprzedniej lekcji dodajmy następujący kod testujący:
public static void Main(string[] args)
{
 HashPerson[] hpArray = new HashPerson[3];
 HashPerson personA = new HashPerson("ala", "kot");
 HashPerson personB = new HashPerson("ala", "kot");
 HashPerson personC = new HashPerson("ola", "pies");
 Console.WriteLine("personA == personB = {0}", personA.Equals(personB));
 Console.WriteLine("personA == personC = {0}", personA.Equals(personC));
 Console.WriteLine("personA == personA = {0}", personA.Equals(personA));
 hpArray[0] = personA;
 hpArray[1] = personB;
 hpArray[2] = personC;
 var testList = from hashPerson in hpArray.Distinct<HashPerson>()
             select hashPerson;
 Console.WriteLine("Number of elements: {0}", testList.Count<HashPerson>());
}

po czym ponownie sprawdźmy wyniki dla dwóch różnych implementacji metody GetHashCode. I tym razem otrzymujemy w pierwszym przypadku:

>HashPersonLINQ.exe
personA == personB = True
personA == personC = False
personA == personA = True
Number of elements: 2

a w drugim, po modyfikacji GetHashCode:

>HashPersonLINQ.exe
personA == personB = True
personA == personC = False
personA == personA = True
Number of elements: 3

Proponuję dla ćwiczenia przetestować inne algorytmy LINQ: Union, Intersect, etc., a na pewno nie zawiedziecie się :).

Lekcja 3. GetHashCode a kolizje

Wiemy już zatem, że korzystanie z implementacji z klasy Object może być niebezpieczne i jednak warto samemu coś napisać. Podejmijmy zatem próbę napisania klasy zachowującej się podobnie do int, z naszą implementacją metody GetHashCode. Weźmy dwie klasy:
public class HashIntOriginal
{
 public int Number = 0;
 protected int hashModulo = Int32.MaxValue;
 public HashIntOriginal(int number, int modulo)
 {
    Number = number;
    hashModulo = modulo;
 }
 public override bool Equals(object obj)
 {
    HashIntOriginal hObj = obj as HashIntOriginal;
    if (hObj != null) return hObj.Number == Number;
    else return false;
 }
 public override int GetHashCode()
 {
    return Number;
 }
}

public class HashIntNew : HashIntOriginal
{
 public HashIntNew(int number, int modulo) : base(number, modulo) {}
 public override int GetHashCode()
 {
    return Number % (hashModulo / 100);
 }
}

Różnica między nimi sprowadza się do innej implementacji metody GetHashCode: w przypadku pierwszym, najbliższym intowi kodem haszowym jest sama liczba, natomiast w przypadku ‘eksperymentalnym’ kodem haszowym jest liczba modulo ustalona z góry liczba, podzielona przez 100. Co to za liczba i dlaczego akurat tak, wyjaśni poniższy kawałek testu:
public static void Main(string[] args)
{
 Stopwatch sw = new Stopwatch();
 int N = 100 * 1000;
 Hashtable hTableInt = new Hashtable();
 Hashtable hTableOryg = new Hashtable();
 Hashtable hTableNew = new Hashtable();
 HashIntOriginal[] hashOriginArr = new HashIntOriginal[N];
 HashIntNew[] hashNewArr = new HashIntNew[N];
 for (int i = 0; i < N; i++)
 {
    hashOriginArr[i] = new HashIntOriginal(i, N);
    hashNewArr[i] = new HashIntNew(i, N);
 }
 Console.WriteLine("Add");
 sw = Stopwatch.StartNew();
 for (int i = 0; i < N; i++)
 {
    hTableInt[i] = i;
 }
 Console.WriteLine(sw.Elapsed + "\tInt");
 sw = Stopwatch.StartNew();
 for (int i = 0; i < N; i++)
 {
    hTableOryg[hashOriginArr[i]] = i;
 }
 Console.WriteLine(sw.Elapsed + "\tHashIntOriginal");
 sw = Stopwatch.StartNew();
 for (int i = 0; i < N; i++)
 {
    hTableNew[hashNewArr[i]] = i;
 }
 Console.WriteLine(sw.Elapsed + "\tHashIntNew");
 Console.WriteLine("Lookup");
 sw = Stopwatch.StartNew();
 for (int i = 0; i < N; i++)
 {
    if (((int)hTableInt[i]) != i)
      Console.WriteLine("{0}", ((int)hTableInt[i]));
 }
 Console.WriteLine(sw.Elapsed + "\tInt");
 sw = Stopwatch.StartNew();
 for (int i = 0; i < N; i++)
 {
    if (((int)hTableOryg[hashOriginArr[i]]) != i)
      Console.WriteLine("{0}", ((int)hTableOryg[hashOriginArr[i]]));
 }
 Console.WriteLine(sw.Elapsed + "\tHashIntOriginal");
 sw = Stopwatch.StartNew();
 for (int i = 0; i < N; i++)
 {
    if (((int)hTableNew[hashNewArr[i]]) != i)
      Console.WriteLine("{0}", ((int)hTableNew[hashNewArr[i]]));
 }
 Console.WriteLine(sw.Elapsed + "\tHashIntNew");
}

Ostatnie 3 pętle umieściłem dla niedowiarków, którzy sądzą, że ze względu na to, iż dla różnych obiektów mamy takie same kody haszowe, mapowanie nie jest jednoznaczne i zmiana funkcji zwracającej kod haszowy obiektu powoduje, że klucz oparty na HashIntNew jest bezużyteczny. Dodatkowo mamy również porównanie czasów wyszukiwania.

W wyniku otrzymujemy:

>HashCollisions.exe
Add
00:00:00.0127302        Int
00:00:00.0127299        HashIntOriginal
00:00:07.8739154        HashIntNew
Lookup
00:00:00.0037004        Int
00:00:00.0028617        HashIntOriginal
00:00:05.2034449        HashIntNew

Jak widać czasy dodawania i wyszukiwania elementów tablicy haszującej dla kluczy opartych na systemowym int i HashIntOriginal są porównywalne, natomiast w przypadku kluczy opartych na HashIntNew czas dodawania jest ponad 500-krotnie dłuższy, a wyszukiwania - prawie 2000 razy dłuższy.

Internalsy

Zgodnie z założeniami, mieszanie jest techniką pozwalającą na wyszukiwanie elementów w tablicy w czasie stałym, niezależnym od ilości elementów. W uproszczeniu polega to na tym, że istnieje funkcja, która dla każdego elementu pozwala wyznaczyć indeks tabeli w której umieszczone są obiekty, a co za tym idzie fizyczne położenie wyszukiwanego elementu. Złożoność obliczeniowa sprowadza się zatem wyłącznie do funkcji mieszającej i nie zależy od ilości elementów tablicy. Dla przykładu, funkcja mieszająca dla ciągu znaków mogłaby wyglądać następująco (dzielimy na grupy po 4 litery, używamy kodu ascii każdej i wszystko xorujemy):
F("ALAMAKOTA") = 
   f1("ALAM") xor f1("AKOT") xor f1("A") = 
   0x414C414D ^ 0x414B4F54 ^ 0x00000041 = 
   0x00070E58 = 462424

Z oczywistych względów nie da się przygotować tablicy, która może zawierać wszystkie możliwe elementy, więc np. określa się rozmiar jako liczbę pierwszą, a w mieszaniu używa się operacji arytmetycznej modulo obcinającej wynik mieszania do dopuszczalnego zakresu. Dla przykładu, .NET-owy Hashtable do ustalenia rozmiaru tablicy korzysta ze statycznej tablicy wybranych liczb pierwszych kończącej się na liczbie 7199369, a dla większych wartości wylicza ją klasycznie.

Wszystko byłoby dobrze, gdyby funkcja haszująca była idealna, czyli taka, która dla dowolnych dwóch różnych elementów dawała dwie różne liczby. Tak jednak najczęściej nie jest i wówczas mamy do czynienia z problemem tzw. kolizji, których rozwiązywanie nie musi być trywialne. W komentarzach do Hashtable z rotora możemy znaleźć (sscli20/clr/src/bcl/system/collections/hashtable.cs):
/*
Our hash function is of the following form:
   
h(key, n) = h1(key) + n*h2(key)
   
where n is the number of times we've hit a collided bucket and rehashed
(on this particular lookup).  Here are our hash functions:
   
h1(key) = GetHash(key);  // default implementation calls key.GetHashCode();
h2(key) = 1 + (((h1(key) >> 5) + 1) % (hashsize - 1));
   
The h1 can return any number.  h2 must return a number between 1 and
hashsize - 1 that is relatively prime to hashsize (not a problem if
hashsize is prime).  (Knuth's Art of Computer Programming, Vol. 3, p. 528-9)
If this is true, then we are guaranteed to visit every bucket in exactly
hashsize probes, since the least common multiple of hashsize and h2(key)
will be hashsize * h2(key).  (This is the first number where adding h2 to
h1 mod hashsize will be 0 and we will search the same bucket twice).
*/

Przykład rozwiązywania konfliktów mieliśmy wyżej, gdy wpychaliśmy po 100 elementów do jednego kubełka. Zainteresowanym polecam sprawdzenie co się stanie, gdy metodę GetHashCode klasy HashIntNew zastąpimy czymś takim:
 public override int GetHashCode()
 {
    return 1;
 }

czyli przypadku, w którym wszystkie elementy będziemy próbować upchnąć do jednego kubełka.
Dodatkowo proponuję sprawdzić, co się stanie, gdy kod haszowy będzie się zmieniał w czasie, np.:
 public override int GetHashCode()
 {
    return (int) DateTime.Now.Ticks;
 }

Metoda zwracająca kod haszowy nie musi być zatem doskonała, jednak powinna cechować się jak najlepszym rozkładem w sensie prowadzenia do jak najmniejszej liczby kolizji. Nie powinna być także zbyt skomplikowana obliczeniowo i raczej sprowadzać się do prostych operacji arytmetycznych. W przypadku typów o rozmiarze mniejszym, lub równym rozmiarowi integera, wystarczy po prostu zwrócić liczbę reprezentującą obiekt, np. dla int (rotor):
// The absolute value of the int contained.
public override int GetHashCode() {
 return m_value;
}

Zatrzymajmy się przez chwilę przy implementacji metody GetHashCode dla klasy Object, a właściwie do metody wyliczania kodu haszowego dla obiektu. I tak (na podstawie rotora):
//object.cpp
DWORD Object::ComputeHashCode()
{
 DWORD hashCode;
 
 // note that this algorithm now uses at most HASHCODE_BITS so that it will
 // fit into the objheader if the hashcode has to be moved back into the objheader
 // such as for an object that is being frozen
 do
 {
   // we use the high order bits in this case because they're more random
   hashCode = GetThread()->GetNewHashCode() >> (32-HASHCODE_BITS);
 }
 while (hashCode == 0);   // need to enforce hashCode != 0
 return hashCode;
}

//syncblk.h
#ifdef _DEBUG
#define HASHCODE_BITS                   25
#else
#define HASHCODE_BITS                   26
#endif

//threads.h
inline DWORD GetNewHashCode()
{
 LEAF_CONTRACT;
 // Every thread has its own generator for hash codes so that we won't get into a situation
 // where two threads consistently give out the same hash codes.
 // Choice of multiplier guarantees period of 2**32 - see Knuth Vol 2 p16 (3.2.1.2 Theorem A).
 DWORD multiplier = m_ThreadId*4 + 5;
 m_dwHashCodeSeed = m_dwHashCodeSeed*multiplier + 1;
 return m_dwHashCodeSeed;
}

//threads.cpp
DWORD m_dwHashCodeSeed;
static  DWORD dwHashCodeSeed = 123456789;
// Initialize this variable to a very different start value for each thread
// Using linear congruential generator from Knuth Vol. 2, p. 102, line 24
dwHashCodeSeed = dwHashCodeSeed * 1566083941 + 1;
m_dwHashCodeSeed = dwHashCodeSeed;

Moglibyśmy teraz uruchomić WinDbg i sprawdzić implementację z naszej wersji .NET Framework, ale oszczędzimy tego sobie - z moich ćwiczeń wynika, że jest prawdopodobnie taka sama.
To, co jest ważne, to to, że kod haszowy zależy od aktualnego numeru wątku zarządzanego w procesie, jest względnie przypadkowy i dla dwóch różnych obiektów powinien być różny. I jeszcze to, że za wszystkim stoi wiedza z lat 60-tych i Donald Knuth, który poza ‘Sztuką Programowania" zasłynął jeszcze swoim TeX-em ;)
Zauważmy też, że ponowne uruchomienie programu, nawet na innej maszynie da nam te same wartości kodu haszowego obiektu, oczywiście przy założeniu takiego samego przebiegu programu.

Nauka płynąca z lekcji i wnioski na przyszłość

Lekcje 1 i 2 to cenne przykłady na to, że trzeba uważać na to, co robi dla nas środowisko programistyczne. Dlaczego? Ano dlatego, że:
- po zaimplementowaniu przez nas metody Equals Visual Studio wystawia warning, że brakuje naszej implementacji GetHashCode;
- łaskawie zgadzamy się, żeby Visual Studio przygotował dla nas implementację i w rezultacie dostajemy
public override int GetHashCode()
{
 return base.GetHashCode();
}

która prowadzi nas wprost na manowce.

Lekcja 3 to z kolei przykład na to, jaki wpływ ma nasza implementacja metody GetHashCode na wydajność związaną z dodawaniem i wyszukiwaniem w tablicy haszującej. Niby wszystko działa, ale jakby nieco wolniej.

W dokumentacji do metody GetHashCode na stronach MSDN można znaleźć kilka cennych wskazówek, które pozwolą nam ustrzec się przed opisanymi wyżej błędami.

  1. Jeśli wynik porównania (Equals) dwóch obiektów daje true, to wywołanie metody GetHashCode musi zwracać identyczne wartości dla obu tych obiektów. Z drugiej jednak strony, jeśli wynik porównania (Equals) dwóch obiektów daje false, to wywołanie metody GetHashCode dla obu tych obiektów nie musi zwracać różnych wartości.
  2. Metoda GetHashCode musi zwracać tę samą wartość tak długo, jak długo nie następuje zmiana obiektu wpływająca na wynik działania metody Equals. Uwaga - ponowne uruchomienie programu może prowadzić do innych wartości zwracanych przez GetHashCode
  3. W celu osiągnięcia jak najlepszej wydajności, metoda GetHashCode musi zwracać wyniki o przypadkowym rozkładzie dla wszystkich danych.

Dodatkowo należy dodać, że metoda GetHashCode powinna korzystać z wartości pól obiektu oraz nie może rzucać wyjątków. Powinna też być szybka do wyliczenia i nie może używać odwołań cyklicznych.

Szczególnie zainteresowanych zachęcam do obejrzenia implementacji metod GetHashCode dla niektórych typów wbudowanych, w tym w szczególności polecam zajrzenie do stringa.

Na sam koniec należy wyraźnie napisać, że wynik metody GetHashCode nie może być traktowany jako identyfikator obiektu i nie ma sensu przechowywać go w tabeli w bazie danych, a już na pewno nie powinno się opierać na nim klucza takiej tabeli. GetHashCode (pomimo nieco mylącej nazwy) nie ma również związku z funkcjami skrótu np. SHA1 i nie należy wyniku działania tej metody traktować jako 'skrótu obiektu'.

Ot, kilka takich refleksji po lekturze niektórych pytań na forach.

Opublikowane 30 kwietnia 2011 02:45 przez mgrzeg
Filed under: , ,

Powiadamianie o komentarzach

Jeżeli chciałbyś otrzymywać email gdy ta wypowiedź zostanie zaktualizowana, to zarejestruj się tutaj

Subskrybuj komentarze za pomocą RSS

Komentarze:

 

dotnetomaniak.pl said:

Dziękujemy za publikację - Trackback z dotnetomaniak.pl

kwietnia 30, 2011 17:43
 

MSM said:

No tak, przez miesiąc nic nie ma a tu nagle dwa wpisy w jeden dzień :)

Pozytywnie zaskoczyłeś mnie GetHashCode() dla Object-u, myślałem że po prostu pobiera sobie tablicę bajtów i jakoś je hashuje.

Ciekawe czy, jeśli CLR implementuje to w ten sam albo chociaż podobny sposób, dałoby się jakoś zmodyfikować (oczywiście jakąś niecną sztuczką jak np. wskaźnikiem bo raczej nie ma do tego ładnego API) DWORD hashCode - jeśli liczenie hasha jest długotrwałe i chcemy go gdzieś przechować to można by w ten sposób uniknąć marnowania `cennych` 4 bajtów pamięci.

maja 2, 2011 15:13
 

zidu said:

Świetny wpis ;)

października 9, 2012 10:04
 

C# Operatory arytmetyczne , por??wnania oraz metody Equals i GetHashCode « Bart??omiej Wasik said:

października 9, 2012 11:32
 

Bart??omiej Wasik said:

maja 13, 2013 21:29

Co o tym myślisz?

(wymagane) 
(opcjonalne)
(wymagane) 

  
Wprowadź kod: (wymagane)
Wyślij

Subskrypcje

W oparciu o Community Server (Personal Edition), Telligent Systems