algorithm
Funkcje skrótu

Wprowadzenie do funkcji skrótu

Funkcja skrótu h() jest dowolną funkcją, która odwzorowała dane x ∈ X o dowolnym rozmiarze na wartość y ∈ Y o stałym rozmiarze: y = h(x) . Dobre funkcje skrótu mają następujące ograniczenia:

• funkcje skrótu zachowują się jak rozkład równomierny

• funkcje skrótu są deterministyczne. h(x) zawsze powinno zwracać tę samą wartość dla danego x

• szybkie obliczanie (ma czas działania O (1))

W ogólnym przypadku rozmiar funkcji skrótu mniejszy niż rozmiar danych wejściowych: |y| < |x| . Funkcje skrótu nie są odwracalne, innymi słowy może to być kolizja: ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2) . X może być zbiorem skończonym lub nieskończonym, a Y jest zbiorem skończonym.

Funkcje mieszania są używane w wielu częściach informatyki, na przykład w inżynierii oprogramowania, kryptografii, bazach danych, sieciach, uczeniu maszynowym i tak dalej. Istnieje wiele różnych typów funkcji skrótu o różnych właściwościach specyficznych dla domeny.

Często skrót jest wartością całkowitą. Istnieją specjalne metody programowania języków do obliczania wartości skrótu. Na przykład w metodzie C# GetHashCode() dla wszystkich typów zwraca wartość Int32 (32-bitowa liczba całkowita). W Java każda klasa udostępnia metodę hashCode() , która zwraca int . Każdy typ danych ma własne lub zdefiniowane przez użytkownika implementacje.

Metody mieszania

Istnieje kilka metod określania funkcji skrótu. Bez utraty ogólności, niech x ∈ X = {z ∈ ℤ: z ≥ 0} są dodatnimi liczbami całkowitymi. Często m jest liczbą pierwszą (niezbyt blisko dokładnej potęgi 2).

Stół Hash

Funkcje skrótu używane w tabelach skrótów do obliczania indeksu w tablicy gniazd. Tabela skrótów to struktura danych do implementacji słowników (struktura klucz-wartość). Dobrze zaimplementowane tabele skrótów mają czas O (1) na kolejne operacje: wstawianie, wyszukiwanie i usuwanie danych według klucza. Więcej niż jeden klucz może mieć skrót do tego samego gniazda. Istnieją dwa sposoby rozwiązania kolizji:

1. Łańcuch: lista połączona służy do przechowywania elementów o tej samej wartości skrótu w gnieździe

2. Adresowanie otwarte: zero lub jeden element jest przechowywany w każdym gnieździe

Kolejne metody są używane do obliczania sekwencji sond wymaganych do otwartego adresowania

Gdzie i ∈ {0, 1, ..., m-1} , h'(x), h1(x), h2(x) są dodatkowymi funkcjami mieszającymi, c1, c2 są dodatnimi stałymi dodatkowymi.

Przykłady

Pozwala x ∈ U{1, 1000}, h = x mod m . Następna tabela pokazuje wartości skrótu w przypadku braku liczby pierwszej i pierwszej. Pogrubiony tekst wskazuje te same wartości skrótu.

Spinki do mankietów

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Wprowadzenie do algorytmów.

• Przegląd tabel mieszania

• Wolfram MathWorld - Funkcja skrótu

Kody skrótu dla typowych typów w C #

Kody mieszające wygenerowane przez metodę GetHashCode() dla wbudowanych i typowych typów C # z przestrzeni nazw System są pokazane poniżej.

Boolean

1 jeśli wartość jest prawdą, 0 w przeciwnym razie.

Bajt , UInt16 , Int32 , UInt32 , Single

Wartość (w razie potrzeby rzutowana na Int32).

SByte

((int)m_value ^ (int)m_value << 8);

Zwęglać

(int)m_value ^ ((int)m_value << 16);

Int16

((int)((ushort)m_value) ^ (((int)m_value) << 16));

Int64 , Double

Xor między dolnym i górnym 32 bitami liczby 64-bitowej

(unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));

UInt64 , DateTime , TimeSpan

((int)m_value) ^ (int)(m_value >> 32);

Dziesiętny

((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1];

Obiekt

RuntimeHelpers.GetHashCode(this);

Domyślną implementacją jest indeks bloku synchronizacji .

Strunowy

Obliczanie kodu skrótu zależy od typu platformy (Win32 lub Win64), funkcji korzystania z losowego mieszania ciągów, trybu debugowania / zwalniania. W przypadku platformy Win64:

int hash1 = 5381;
int hash2 = hash1;
int c;
char *s = src;
while ((c = s[0]) != 0) {
    hash1 = ((hash1 << 5) + hash1) ^ c;
    c = s[1];
    if (c == 0)
        break;
    hash2 = ((hash2 << 5) + hash2) ^ c;
    s += 2;
}
return hash1 + (hash2 * 1566083941);

Typ wartości

Pierwszym niestatycznym polem jest poszukiwanie i uzyskanie kodu hash. Jeśli typ nie ma pól niestatycznych, zwracany jest kod skrótu typu. Nie można pobrać kodu mieszającego elementu statycznego, ponieważ jeśli ten element jest tego samego typu co typ oryginalny, obliczenia kończą się w nieskończonej pętli.

Nullable <T>

return hasValue ? value.GetHashCode() : 0;

Szyk

int ret = 0;
for (int i = (Length >= 8 ? Length - 8 : 0); i < Length; i++) 
{
    ret = ((ret << 5) + ret) ^ comparer.GetHashCode(GetValue(i));
}

Bibliografia

• GitHub .Net Core CLR