czoper.devlog

.NET, CAD/CAM

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:

1. dla wierzchołków działa
2. krawędzie są skierowane (dla przeciwnie skierowanych krawędzi wartość hash’a będzie różna)
3. 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!

Be Sociable, Share!

• 
•