C Academy · Lektion

Ændring af størrelse og load factor

Optimering af ydeevne

Lektion 4 af 413 trin

Ændring af størrelse og load factor er en gratis C Academy-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i C Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. C Academy-kurset indeholder 4 lektioner i alt.

Hvad er belastningsfaktor

Belastningsfaktoren er forholdet mellem gemte poster og spande: alpha = size / capacity. Den måler, hvor fuld tabellen er, og påvirker direkte ydeevnen.

Hvorfor belastningsfaktoren betyder noget

Når belastningsfaktoren stiger, indeholder spandene længere kæder, eller sonderingerne danner klynger, så operationerne bliver langsommere.

Lav alpha: hurtigt, men spilder hukommelse
Høj alpha: kompakt, men langsomt

Et almindeligt mål for kædning er 0.75.

Beregning af belastningsfaktor

Beregn den som et flydende kommatal, så du kan sammenligne den med en tærskel.

#include <stdio.h>

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

Hvornår skal størrelsen ændres

Kontrollér efter hver indsættelse, om belastningsfaktoren overstiger tærsklen. Hvis den gør, skal du udvide tabellen, normalt ved at fordoble kapaciteten, og hashe posterne igen.

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

Forklaring af rehashing

Du kan ikke kopiere spandene ukritisk, fordi hver nøgles indeks afhænger af kapaciteten. Rehashing beregner hver nøgles spand igen ud fra den nye kapacitet og indsætter den på ny.

En funktion til ændring af størrelsen

Allokér et nyt, større spand-array. Gennemgå hver gammel knude, og flyt den til det nye array ved hjælp af den nye kapacitet. Byt derefter arrayene. Her ser du den centrale genberegning af indekset.

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

Flytning af knuder uden ny allokering

Med kædning kan du flytte eksisterende knuder til det nye array i stedet for at allokere nye. Frakobl hver knude, beregn dens spand igen, og indsæt den først.

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

Strategi for vækst

Ved at fordoble kapaciteten bevares den amortiserede indsættelsesomkostning på O(1). Selvom en ændring af størrelsen tager O(n), sker den så sjældent, at den gennemsnitlige omkostning pr. indsættelse forbliver konstant.

Potenser af to gør det også muligt at bruge den hurtige OG-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;
}

Formindskelse

Du kan vælge at formindske tabellen, når belastningsfaktoren falder for langt, for eksempel under 0.1 efter mange sletninger. Formindskelse frigiver hukommelse, men medfører en omkostning til rehashing, så gør det forsigtigt for at undgå gentagne ændringer.

Åben adressering og belastningsfaktor

Tabeller med åben adressering er langt mere følsomme over for belastningsfaktoren. Ydeevnen kollapser, når alpha nærmer sig 1, så de ændrer typisk størrelse ved 0.5 til 0.7, hvilket er lavere end kædningens 0.75.

Demonstration af amortiseret omkostning

Simulér indsættelser, der fordobler kapaciteten ved 0.75, og tæl det samlede arbejde for at vise, at gennemsnittet forbliver lavt.

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

Hurtigt tjek

Test din forståelse af ændring af tabellens størrelse.

Besvar den i den interaktive lektion

Opsummering

Du har lært at justere hashtabellens ydeevne.

Belastningsfaktor = størrelse / kapacitet
Ændr størrelsen, når den overstiger en tærskel, omkring 0.75 for kædning
Udfør rehashing, fordi indekser afhænger af kapaciteten
Fordobling giver amortiserede indsættelser på O(1)

Gratis at komme i gang

Lær C med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 39
Lektioner: 144

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Ændring af størrelse og load factor” gratis?

Ja — hele teksten til “Ændring af størrelse og load factor” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af C Academy-kurset, skal du opgradere til CoddyKit PRO. C Academy-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Ændring af størrelse og load factor”?

Optimering af ydeevne Du øver dig i C Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på C Academy?

Der kræves ingen tidligere erfaring. C Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 4 af 4.

Hvor lang tid tager lektionen “Ændring af størrelse og load factor”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne C Academy-lektion?

Ja. Alle C Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til C Academy