Short Tip #09: GetHashCode() dla wektora
Specyfika pewnej części projektu, nad którym obecnie pracuję wymagała zastosowania tablicy haszującej. Struktury danych, które są przechowywane w tablicach (jedna tablica na typ) wyglądają następująco:
Okazało się, że metoda
GetHashCode()
domyślnie wygenerowana przez IDE dla klasy Vector3
jest niewystarczająca – błędy pojawiły się już przy próbie wczytania wierzchołków, krawędzi i trójkątów prostego sześcianu.
Chwila zastanowienia doprowadziła do powstania następującej koncepcji. Idąc schematem „bottom-up”, najpierw klasa najniżej położona w pseudohierarchii – Vector3
i fragment klasy pomocniczej Util
:
/// <summary> /// basic version: http://dotnetperls.com/gethashcode-net /// </summary> public static unsafe int GetHashFromString(string s) { fixed (char* str = s) { char* chPtr = str; int num = 352654597; int num2 = num; int* numPtr = (int*)chPtr; for (int i = s.Length; i > 0; i -= 4) { num = (((num << 5) + num) + (num >> 27)) ^ numPtr[0]; if (i <= 2) break; num2 = (((num2 << 5) + num2) + (num2 >> 27)) ^ numPtr[1]; numPtr += 2; } return (num + (num2 * 1566083941)); } }
Vector3.cs
public override int GetHashCode() { return Util.GetHashFromString(GetStringForHash()); } public string GetStringForHash() { return string.Format("{0}{1}{2}", X, Y, Z); }
dalej Edge.cs (Start.Position
i End.Position
to zmienne typu Vector3
)
public override int GetHashCode() { string s1 = Start.Position.GetStringForHash(); string s2 = End.Position.GetStringForHash(); return Util.GetHashFromString(s1 + s2); }
i na koniec Face.cs (A, B, C to wierzchołki trójkąta)
public override int GetHashCode() { return Util.GetHashFromString(A.GetStringForHash()) + Util.GetHashFromString(B.GetStringForHash()) + Util.GetHashFromString(C.GetStringForHash()); }
Widać, że:
- dla wierzchołków działa
- krawędzie są skierowane (dla przeciwnie skierowanych krawędzi wartość hash’a będzie różna)
- trójkąty o trzech identycznych wierzchołkach będą miały identyczną wartość hash’a niezależnie od przypisania wierzchołków do zmiennych A, B, C.
Voila!
Jedna odpowiedź Zostaw komentarz
Trochę przekombinowane. Dużo prościej możnaby było użyć GetHashCode dla współrzędnych wektora i je łączyć bitowymi operacjami i przesunieciami. Efekt można bez problemu uzyskać taki sam, a będzie szybciej bo to tylko kilka operacji na intach, a nie przeglądanie stringa po znaku w dodatku w unsafe.