0Pricing
C Academy · Lekcja

Funkcje haszujące

Mapowanie kluczy na koszyki

Funkcje haszujące to bezpłatna lekcja C Academy na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.

Czym jest funkcja skrótu

Funkcja skrótu przyjmuje klucz i generuje całkowity indeks tablicy wiader. Stanowi podstawę tablicy mieszającej, zamieniając dowolne klucze, takie jak napisy, na szybko dostępne pozycje w tablicy.

  • Dane wejściowe: klucz (napis, liczba całkowita itp.)
  • Dane wyjściowe: indeks wiadra w zakresie [0, capacity)

Właściwości dobrego skrótu

Dobra funkcja skrótu jest deterministyczna, szybka i rozprowadza klucze równomiernie między wiadrami.

  • Ten sam klucz zawsze daje ten sam indeks
  • Niewielkie zmiany klucza powodują duże zmiany indeksu (efekt lawinowy)
  • Mało kolizji dla typowych danych

Mapowanie do wiadra

Po obliczeniu surowej wartości skrótu należy zmapować ją na tablicę za pomocą operatora modulo: index = hash % capacity.

Należy używać typu unsigned, aby modulo nigdy nie zwracało ujemnego indeksu.

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16;
    unsigned index = (unsigned)(hash % capacity);
    printf("bucket = %u\n", index);
    return 0;
}

Prosty skrót sumujący

Najprostsza funkcja skrótu dla napisów sumuje wartości znaków. Jest łatwa, ale słabo rozprowadza dane, ponieważ anagramy powodują kolizje.

Uruchom ten przykład, aby zobaczyć, że dwa różne napisy mogą otrzymać zbliżone wartości skrótu.

#include <stdio.h>

unsigned long sum_hash(const char *s) {
    unsigned long h = 0;
    while (*s) h += (unsigned char)*s++;
    return h;
}

int main(void) {
    printf("%lu\n", sum_hash("abc"));
    printf("%lu\n", sum_hash("cba"));
    return 0;
}

Skrót DJB2

DJB2 to klasyczna, dobrze rozprowadzająca dane funkcja skrótu dla napisów, opracowana przez Daniela J. Bernsteina. Rozpoczyna działanie od wartości 5381 i używa wyrażenia hash * 33 + c.

Mnożenie i dodawanie znacznie lepiej miesza bity niż zwykłe sumowanie.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*s++))
        h = ((h << 5) + h) + c; /* h * 33 + c */
    return h;
}

int main(void) {
    printf("%lu\n", djb2("hello"));
    printf("%lu\n", djb2("world"));
    return 0;
}

Skrót FNV-1a

FNV-1a wykonuje operację XOR dla każdego bajtu, a następnie mnoży wynik przez liczbę pierwszą. Jest prosty, szybki i powszechnie używany.

Kolejność jest następująca: najpierw XOR, potem mnożenie (na tym polega wariant 1a).

#include <stdio.h>

unsigned long fnv1a(const char *s) {
    unsigned long h = 1469598103934665603UL;
    while (*s) {
        h ^= (unsigned char)*s++;
        h *= 1099511628211UL;
    }
    return h;
}

int main(void) {
    printf("%lu\n", fnv1a("key1"));
    printf("%lu\n", fnv1a("key2"));
    return 0;
}

Haszowanie liczb całkowitych

Klucze będące liczbami całkowitymi również wymagają mieszania, ponieważ samo x % capacity powoduje grupowanie, gdy klucze mają wspólne wzorce. Mieszanie multiplikatywne (Knutha) rozprasza bity.

#include <stdio.h>

unsigned hash_int(unsigned x, unsigned cap) {
    x *= 2654435761u; /* Knuth multiplicative */
    return x % cap;
}

int main(void) {
    for (unsigned i = 0; i < 5; i++)
        printf("%u -> %u\n", i, hash_int(i, 8));
    return 0;
}

Pojemności będące potęgami dwójki

Gdy pojemność jest potęgą dwójki, operator % capacity można zastąpić szybkim bitowym AND: hash & (capacity - 1).

Działa to tylko dlatego, że bity liczby o jeden mniejszej od potęgi dwójki tworzą pełną maskę.

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16; /* power of two */
    unsigned index = (unsigned)(hash & (capacity - 1));
    printf("bucket = %u\n", index);
    return 0;
}

Dlaczego modulo może być wolne

Operator % jest kompilowany do instrukcji dzielenia, która działa wolniej niż AND. Ma to znaczenie w ciasnych pętlach.

  • Tablica o pojemności będącej potęgą dwójki: użyj maski AND
  • Tablica o rozmiarze będącym liczbą pierwszą: użyj modulo (lepsze rozprowadzanie przy słabych funkcjach skrótu)

Kolizje są nieuniknione

Zgodnie z zasadą szufladkową mapowanie wielu kluczy na mniejszą liczbę wiader gwarantuje wystąpienie kolizji. Dobra funkcja skrótu minimalizuje ich liczbę, ale nie może ich wyeliminować.

W następnej lekcji omówiono sposoby rozwiązywania kolizji.

Demonstracja rozkładu

Policzmy, jak DJB2 rozprowadza kilka kluczy między 8 wiader. Dobre funkcje skrótu rozkładają je dość równomiernie.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h;
}

int main(void) {
    const char *keys[] = {"apple", "banana", "cherry", "date"};
    int counts[8] = {0};
    for (int i = 0; i < 4; i++)
        counts[djb2(keys[i]) % 8]++;
    for (int i = 0; i < 8; i++)
        printf("bucket %d: %d\n", i, counts[i]);
    return 0;
}

Szybki sprawdzian

Sprawdź swoją wiedzę na temat podstaw funkcji skrótu.

Podsumowanie

Poznał(a) Pan/Pani działanie funkcji skrótu oraz sposób mapowania kluczy na wiadra.

  • Dobre funkcje skrótu są deterministyczne, szybkie i równomierne
  • DJB2 i FNV-1a to dobre funkcje skrótu dla napisów
  • Mapowanie wykonuje się za pomocą % capacity, a dla potęg dwójki za pomocą & (capacity-1)
  • Należy używać typów bez znaku; kolizje są nieuniknione

Często zadawane pytania

Czy lekcja „Funkcje haszujące” jest bezpłatna?

Tak — pełny tekst „Funkcje haszujące” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Funkcje haszujące”?

Mapowanie kluczy na koszyki Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć C Academy?

Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.

Ile czasu zajmuje lekcja „Funkcje haszujące”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?

Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Funkcje haszujące
  2. Obsługa kolizji
  3. Wstawianie, wyszukiwanie i usuwanie
  4. Zmiana rozmiaru i współczynnik zapełnienia
← Powrót do C Academy