0Pricing
C Academy · Lekcja

Obsługa kolizji

Łańcuchowanie i sondowanie

Obsługa kolizji to bezpłatna lekcja C Academy na CoddyKit. To lekcja 2 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.

Problem kolizji

Kolizja występuje, gdy dwa różne klucze mają ten sam skrót i trafiają do tego samego wiadra. Ponieważ kolizje są nieuniknione, każda tablica mieszająca potrzebuje strategii przechowywania wielu kluczy w jednym miejscu.

Dwie główne grupy metod to łańcuchowanie i adresowanie otwarte.

Łańcuchowanie

W przypadku łańcuchowania każdy kubełek zawiera listę jednokierunkową wpisów. W razie kolizji wystarczy dołączyć wpis na końcu (lub początku) listy tego kubełka.

  • Kubełki przechowują wskaźniki na początki list
  • Wyszukiwanie przechodzi przez jedną krótką listę

Struktura węzła łańcuchowania

Każdy węzeł przechowuje klucz, wartość oraz wskaźnik next. Tablica jest tablicą wskaźników na węzły.

#include <stdio.h>

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *buckets[8] = {0};
    printf("slots = %zu\n", sizeof buckets / sizeof buckets[0]);
    return 0;
}

Wstawianie z użyciem łańcuchowania

Dodanie elementu na początku listy kubełka ma złożoność O(1). Tutaj ręcznie tworzymy krótki łańcuch i go wypisujemy.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int key; struct Node *next; } Node;

Node *prepend(Node *head, int key) {
    Node *n = malloc(sizeof *n);
    n->key = key; n->next = head;
    return n;
}

int main(void) {
    Node *bucket = NULL;
    bucket = prepend(bucket, 10);
    bucket = prepend(bucket, 26); /* same bucket as 10 mod 8 */
    for (Node *p = bucket; p; p = p->next)
        printf("%d ", p->key);
    printf("\n");
    return 0;
}

Adresowanie otwarte

W przypadku adresowania otwartego każdy wpis znajduje się bezpośrednio w tablicy kubełków. W razie kolizji sondujesz kolejną pustą pozycję, korzystając ze stałej sekwencji.

Nie są przydzielane dodatkowe węzły, co sprzyja wykorzystaniu pamięci podręcznej.

Sondowanie liniowe

Sondowanie liniowe sprawdza następną pozycję, potem kolejną, zawijając się na początku po dotarciu do końca: (h + i) % capacity.

Jest proste i sprzyja wykorzystaniu pamięci podręcznej, ale cierpi z powodu grupowania.

#include <stdio.h>

int main(void) {
    int slots[8] = {0,0,1,0,0,0,0,0}; /* slot 2 taken */
    unsigned h = 2, cap = 8;
    for (unsigned i = 0; i < cap; i++) {
        unsigned idx = (h + i) % cap;
        if (!slots[idx]) { printf("insert at %u\n", idx); break; }
    }
    return 0;
}

Sondowanie kwadratowe

Sondowanie kwadratowe używa (h + i*i) % capacity, aby rozproszyć sondowania i ograniczyć grupowanie pierwotne.

#include <stdio.h>

int main(void) {
    unsigned h = 3, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h + i*i) % cap);
    return 0;
}

Podwójne haszowanie

Podwójne haszowanie używa drugiej funkcji skrótu do określenia kroku: (h1 + i*h2) % capacity. Dzięki temu każdy klucz ma własną sekwencję sondowania, co zapewnia najlepsze rozłożenie spośród tych trzech metod.

#include <stdio.h>

int main(void) {
    unsigned h1 = 3, h2 = 5, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h1 + i*h2) % cap);
    return 0;
}

Usuwanie w adresowaniu otwartym

W adresowaniu otwartym nie można po prostu wyczyścić pozycji, ponieważ przerwałoby to łańcuchy sondowania innych kluczy. Zamiast tego oznacz ją jako znacznik usunięcia, aby wyszukiwanie nadal sondowało kolejne pozycje.

Łańcuchowanie a adresowanie otwarte

Kompromisy:

  • Łańcuchowanie: obsługuje wysokie współczynniki zapełnienia i upraszcza usuwanie, ale korzysta ze wskaźników i alokacji
  • Adresowanie otwarte: sprzyja wykorzystaniu pamięci podręcznej i nie wymaga alokacji dla każdego wpisu, ale znacznie zwalnia przy niemal pełnej tablicy i wymaga znaczników usunięcia

Przykład zliczania sondowań

Sondowanie liniowe może wymagać kilku kroków, gdy pozycje są zgrupowane. Tutaj zliczamy sondowania potrzebne do znalezienia wolnej pozycji.

#include <stdio.h>

int main(void) {
    int slots[8] = {1,1,1,0,0,0,0,0};
    unsigned h = 0, cap = 8, probes = 0;
    for (unsigned i = 0; i < cap; i++) {
        probes++;
        if (!slots[(h + i) % cap]) break;
    }
    printf("probes used = %u\n", probes);
    return 0;
}

Szybkie sprawdzenie

Sprawdź swoją wiedzę na temat obsługi kolizji.

Podsumowanie

Przeanalizowałeś(-aś), jak tablice haszujące rozwiązują kolizje.

  • Łańcuchowanie przechowuje listę jednokierunkową dla każdego kubełka
  • Adresowanie otwarte sonduje kolejne pozycje w poszukiwaniu wolnej
  • Warianty sondowania: liniowe, kwadratowe i podwójne haszowanie
  • Adresowanie otwarte wymaga znaczników usunięcia

Często zadawane pytania

Czy lekcja „Obsługa kolizji” jest bezpłatna?

Tak — pełny tekst „Obsługa kolizji” 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 „Obsługa kolizji”?

Łańcuchowanie i sondowanie Ć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 2 z 4.

Ile czasu zajmuje lekcja „Obsługa kolizji”?

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