0Pricing
C Academy · Lektion

Größenanpassung und Load Factor

Performance-Tuning

Größenanpassung und Load Factor ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 4 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.

Was ist der Auslastungsfaktor

Der Auslastungsfaktor ist das Verhältnis der gespeicherten Einträge zur Anzahl der Buckets: alpha = size / capacity. Er misst, wie voll die Tabelle ist, und beeinflusst ihre Leistung unmittelbar.

Warum der Auslastungsfaktor wichtig ist

Mit steigendem Auslastungsfaktor enthalten die Buckets längere Ketten (oder die Prüfungen bilden Cluster), wodurch die Operationen langsamer werden.

  • Niedriges Alpha: schnell, aber speicherintensiv
  • Hohes Alpha: kompakt, aber langsam

Für Verkettung ist 0.75 ein häufig verwendeter Zielwert.

Den Auslastungsfaktor berechnen

Berechnen Sie ihn als Gleitkomma-Verhältnis, damit Sie ihn mit einem Schwellenwert vergleichen können.

#include <stdio.h>

int main(void) {
    unsigned size = 12, capacity = 16;
    double alpha = (double)size / capacity;
    printf("load factor = %.2f\n", alpha);
    return 0;
}

Wann die Größe angepasst werden sollte

Prüfen Sie nach jedem Einfügen, ob der Auslastungsfaktor den Schwellenwert überschreitet. Falls ja, vergrößern Sie die Tabelle (üblicherweise durch Verdoppeln der Kapazität) und führen Sie ein Rehashing durch.

#include <stdio.h>

int should_grow(unsigned size, unsigned cap) {
    return (double)size / cap > 0.75;
}

int main(void) {
    printf("%d\n", should_grow(13, 16)); /* 0.8125 -> 1 */
    printf("%d\n", should_grow(10, 16)); /* 0.625  -> 0 */
    return 0;
}

Rehashing erklärt

Sie können die Buckets nicht einfach kopieren, da der Index jedes Schlüssels von der Kapazität abhängt. Beim Rehashing wird der Bucket jedes Schlüssels anhand der neuen Kapazität neu berechnet und der Schlüssel erneut eingefügt.

Eine Funktion zur Größenanpassung

Reservieren Sie Speicher für ein neues, größeres Bucket-Array. Durchlaufen Sie jeden alten Knoten und verschieben Sie ihn anhand der neuen Kapazität in das neue Array. Tauschen Sie anschließend die Arrays aus. Hier sehen Sie die zentrale Neuberechnung des Index.

#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 *key = "session";
    unsigned old_cap = 8, new_cap = 16;
    printf("old slot = %lu\n", djb2(key) % old_cap);
    printf("new slot = %lu\n", djb2(key) % new_cap);
    return 0;
}

Knoten verschieben, ohne Speicher neu zu reservieren

Bei Verkettung können Sie vorhandene Knoten in das neue Array verschieben, anstatt neue zu reservieren. Entfernen Sie jeden Knoten aus seiner bisherigen Liste, berechnen Sie seinen Bucket neu und fügen Sie ihn am Anfang ein.

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

typedef struct Node { char *key; struct Node *next; } Node;
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) {
    Node *old[2] = {0};
    Node *a = malloc(sizeof *a); a->key = strdup("x"); a->next = NULL; old[0] = a;
    Node *new_b[4] = {0};
    /* move node a */
    unsigned i = djb2(a->key) % 4;
    a->next = new_b[i]; new_b[i] = a;
    printf("moved to slot %u\n", i);
    return 0;
}

Strategie zum Vergrößern

Das Verdoppeln der Kapazität hält die amortisierten Kosten des Einfügens bei O(1): Obwohl eine Größenanpassung O(n) benötigt, tritt sie selten genug auf, sodass die durchschnittlichen Kosten pro Einfügevorgang konstant bleiben.

Potenzen von zwei ermöglichen außerdem die Verwendung der schnellen AND-Maske.

#include <stdio.h>

int main(void) {
    unsigned cap = 8;
    for (int i = 0; i < 4; i++) {
        printf("capacity = %u\n", cap);
        cap *= 2;
    }
    return 0;
}

Verkleinern

Optional können Sie die Tabelle verkleinern, wenn der Auslastungsfaktor nach vielen Löschvorgängen zu stark sinkt (beispielsweise unter 0.1). Das Verkleinern gibt Speicher frei, verursacht aber Rehashing-Kosten. Gehen Sie daher zurückhaltend vor, um ständiges Vergrößern und Verkleinern zu vermeiden.

Offene Adressierung und Auslastungsfaktor

Tabellen mit offener Adressierung reagieren deutlich empfindlicher auf den Auslastungsfaktor. Die Leistung bricht ein, wenn sich Alpha dem Wert 1 nähert. Daher werden solche Tabellen typischerweise bei 0.5 bis 0.7 vergrößert, also früher als Tabellen mit Verkettung bei 0.75.

Demo zu amortisierten Kosten

Simulieren Sie Einfügevorgänge, die bei 0.75 die Kapazität verdoppeln, und zählen Sie den Gesamtaufwand. So sehen Sie, dass der Durchschnitt niedrig bleibt.

#include <stdio.h>

int main(void) {
    unsigned cap = 4, size = 0;
    long work = 0;
    for (int i = 0; i < 100; i++) {
        size++; work++; /* the insert */
        if ((double)size / cap > 0.75) { work += size; cap *= 2; } /* rehash */
    }
    printf("inserts=%u total_work=%ld avg=%.2f\n", size, work, (double)work/size);
    return 0;
}

Kurzer Test

Testen Sie Ihr Verständnis der Größenanpassung.

Zusammenfassung

Sie haben gelernt, die Leistung von Hashtabellen abzustimmen.

  • Auslastungsfaktor = Größe / Kapazität
  • Vergrößern Sie die Tabelle, wenn der Schwellenwert überschritten wird (bei Verkettung etwa 0.75)
  • Führen Sie ein Rehashing durch, weil die Indizes von der Kapazität abhängen
  • Verdoppeln ermöglicht amortisierte Kosten von O(1) pro Einfügevorgang

Häufig gestellte Fragen

Ist die Lektion „Größenanpassung und Load Factor“ kostenlos?

Ja — der vollständige Text von „Größenanpassung und Load Factor“ 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 „Größenanpassung und Load Factor“?

Performance-Tuning 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 4 von 4.

Wie lange dauert die Lektion „Größenanpassung und Load Factor“?

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

  1. Hash-Funktionen
  2. Kollisionsbehandlung
  3. Einfügen, Suchen, Löschen
  4. Größenanpassung und Load Factor
← Zurück zu C Academy