Grootte aanpassen en loadfactor
Prestaties tunen
Grootte aanpassen en loadfactor is een gratis C Academy-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject C Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus C Academy bevat in totaal 4 lessen.
Wat is de bezettingsgraad
De bezettingsgraad is de verhouding tussen het aantal opgeslagen items en het aantal buckets: alpha = size / capacity. Deze waarde geeft aan hoe vol de tabel is en heeft rechtstreeks invloed op de prestaties.
Waarom de bezettingsgraad belangrijk is
Naarmate de bezettingsgraad stijgt, bevatten buckets langere ketens of raken probeerstappen meer geclusterd. Daardoor worden bewerkingen trager.
- Lage alpha: snel, maar verspilt geheugen
- Hoge alpha: compact, maar traag
Voor chaining is 0.75 een veelgebruikte doelwaarde.
De bezettingsgraad berekenen
Bereken de waarde als een verhouding met drijvende komma, zodat je die met een drempelwaarde kunt vergelijken.
#include <stdio.h>
int main(void) {
unsigned size = 12, capacity = 16;
double alpha = (double)size / capacity;
printf("load factor = %.2f\n", alpha);
return 0;
}Wanneer je de grootte aanpast
Controleer na elke invoeging of de bezettingsgraad de drempel overschrijdt. Zo ja, vergroot je de tabel, meestal door de capaciteit te verdubbelen, en voer je een rehash uit.
#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 uitgelegd
Je kunt buckets niet blind kopiëren, omdat de index van elke sleutel afhankelijk is van de capaciteit. Bij rehashing wordt voor elke sleutel de bucketindex opnieuw berekend met de nieuwe capaciteit en wordt de sleutel opnieuw ingevoegd.
Een functie voor het aanpassen van de grootte
Reserveer ruimte voor een nieuwe, grotere bucketarray. Doorloop elk oude knooppunt en verplaats het met de nieuwe capaciteit naar de nieuwe array. Wissel daarna de arrays om. Hier zie je de essentiële herberekening van de 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;
}Knooppunten verplaatsen zonder opnieuw toe te wijzen
Met chaining kun je bestaande knooppunten naar de nieuwe array verplaatsen in plaats van nieuwe knooppunten toe te wijzen. Koppel elk knooppunt los, bereken de bucket opnieuw en plaats het vooraan.
#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;
}Groeistrategie
Door de capaciteit te verdubbelen blijven de afgeschreven kosten van invoegen O(1): een aanpassing van de grootte kost weliswaar O(n), maar gebeurt zelden genoeg om de gemiddelde kosten per invoeging constant te houden.
Machten van twee maken het bovendien mogelijk om het snelle AND-masker te gebruiken.
#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;
}Verkleinen
Je kunt de tabel optioneel verkleinen wanneer de bezettingsgraad na veel verwijderingen te laag wordt, bijvoorbeeld onder 0.1. Verkleinen geeft geheugen terug, maar brengt kosten voor rehashing met zich mee. Doe dit daarom voorzichtig om voortdurend vergroten en verkleinen te voorkomen.
Open addressing en bezettingsgraad
Tabellen met open addressing zijn veel gevoeliger voor de bezettingsgraad. De prestaties storten in wanneer alpha 1 nadert. Daarom worden ze meestal al bij 0.5 tot 0.7 vergroot, dus eerder dan bij de 0.75 van chaining.
Demonstratie van afgeschreven kosten
Simuleer invoegingen waarbij de capaciteit bij 0.75 wordt verdubbeld en tel al het werk op. Zo zie je dat het gemiddelde laag blijft.
#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;
}Korte controle
Toets je begrip van het aanpassen van de tabelgrootte.
Samenvatting
Je hebt geleerd hoe je de prestaties van een hashtabel afstemt.
- Bezettingsgraad = grootte / capaciteit
- Pas de grootte aan wanneer de bezettingsgraad een drempel overschrijdt, ongeveer 0.75 bij chaining
- Voer rehashing uit omdat indices afhankelijk zijn van de capaciteit
- Verdubbelen zorgt voor afgeschreven invoegingen van O(1)
Leer C met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 39
- Lessen
- 144
Veelgestelde vragen
Is de les “Grootte aanpassen en loadfactor” gratis?
Ja — de volledige tekst van “Grootte aanpassen en loadfactor” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus C Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus C Academy bevat in totaal 4 lessen.
Wat leer ik in “Grootte aanpassen en loadfactor”?
Prestaties tunen Je oefent met C Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met C Academy te beginnen?
Ervaring vooraf is niet nodig. C Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Grootte aanpassen en loadfactor”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over C Academy?
Ja. Elke les over C Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Hashfuncties
- Botsingen afhandelen
- Invoegen, opzoeken, verwijderen
- Grootte aanpassen en loadfactor