C Academy · Lektion

Kollisionsbehandlung

Verkettung und Sondierung

Kollisionsbehandlung ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Das Kollisionsproblem

Eine Kollision tritt auf, wenn zwei verschiedene Schlüssel auf denselben Bucket gehasht werden. Da Kollisionen unvermeidbar sind, benötigt jede Hashtabelle eine Strategie, um mehrere Schlüssel in einem Slot zu speichern.

Die beiden wichtigsten Verfahren sind Verkettung und Open Addressing.

Separate Verkettung

Bei der separaten Verkettung enthält jeder Bucket eine verkettete Liste von Einträgen. Bei einer Kollision hängen Sie den Eintrag einfach an die Liste dieses Buckets an (oder fügen ihn am Anfang ein).

Buckets speichern die Listenanfänge
Bei der Suche wird eine kurze Liste durchlaufen

Struktur eines Verkettungsknotens

Jeder Knoten speichert einen Schlüssel, einen Wert und einen next-Zeiger. Die Tabelle ist ein Array von Zeigern auf Knoten.

#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;
}

Einfügen mit Verkettung

Das Einfügen am Anfang der Bucket-Liste hat die Komplexität O(1). Hier erstellen wir von Hand eine kleine Kette und geben sie aus.

#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;
}

Offene Adressierung

Bei der offenen Adressierung liegt jeder Eintrag direkt im Bucket-Array. Bei einer Kollision prüfen Sie anhand einer festen Folge weitere freie Positionen.

Es werden keine zusätzlichen Knoten angelegt, was cachefreundlich ist.

Lineares Sondieren

Beim linearen Sondieren wird zuerst die nächste Position und dann die jeweils folgende geprüft, wobei am Ende wieder von vorne begonnen wird: (h + i) % capacity.

Das Verfahren ist einfach und cachefreundlich, leidet aber unter Clusterbildung.

#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;
}

Quadratisches Sondieren

Beim quadratischen Sondieren wird (h + i*i) % capacity verwendet, um die Prüfungen weiter zu verteilen und die primäre Clusterbildung zu verringern.

#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;
}

Doppeltes Hashing

Beim doppelten Hashing wird ein zweiter Hashwert für die Schrittweite verwendet: (h1 + i*h2) % capacity. Dadurch erhält jeder Schlüssel eine eigene Prüfsequenz und von den drei Verfahren die beste Verteilung.

#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;
}

Löschen bei offener Adressierung

Bei offener Adressierung können Sie eine Position nicht einfach leeren, da dadurch Prüfketten anderer Schlüssel unterbrochen würden. Markieren Sie sie stattdessen mit einem Tombstone, damit Suchvorgänge weiterhin darüber hinaus prüfen.

Verkettung im Vergleich zur offenen Adressierung

Abwägungen:

Verkettung: verarbeitet hohe Auslastungsfaktoren, einfaches Löschen, verwendet aber Zeiger und Speicherreservierungen
Offene Adressierung: cachefreundlich, keine Speicherreservierung pro Eintrag, wird bei fast voller Tabelle jedoch deutlich langsamer und benötigt Tombstones

Demo zur Anzahl der Prüfungen

Beim linearen Sondieren können mehrere Schritte erforderlich sein, wenn sich Positionen zu Clustern zusammenballen. Hier zählen wir die Prüfungen, bis eine freie Position gefunden wird.

#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;
}

Kurzer Test

Testen Sie Ihr Wissen über den Umgang mit Kollisionen.

Zusammenfassung

Sie haben untersucht, wie Hashtabellen Kollisionen auflösen.

Verkettung speichert pro Bucket eine verkettete Liste
Offene Adressierung prüft Positionen auf einen freien Platz
Varianten des Sondierens: linear, quadratisch und doppeltes Hashing
Offene Adressierung benötigt Tombstones zum Löschen

Häufig gestellte Fragen

Ist die Lektion „Kollisionsbehandlung“ kostenlos?

Ja — der vollständige Text von „Kollisionsbehandlung“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Kollisionsbehandlung“?

Verkettung und Sondierung Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um C Academy zu starten?

Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.

Wie lange dauert die Lektion „Kollisionsbehandlung“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?

Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

← Zurück zu C Academy