C Academy · Lesson

Resizing and Load Factor

Performance tuning.

Resizing and Load Factor is a free C Academy lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the C Academy learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

What Is Load Factor

The load factor is the ratio of stored entries to buckets: alpha = size / capacity. It measures how full the table is and directly affects performance.

Why Load Factor Matters

As the load factor rises, buckets hold longer chains (or probes cluster), so operations slow down.

Low alpha: fast but wastes memory
High alpha: compact but slow

A common target is 0.75 for chaining.

Computing Load Factor

Compute it as a floating-point ratio so you can compare against a threshold.

#include <stdio.h>

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

When to Resize

After each insert, check whether the load factor exceeds the threshold. If so, grow the table (usually double the capacity) and rehash.

#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 Explained

You cannot copy buckets blindly, because each key's index depends on the capacity. Rehashing recomputes every key's bucket against the new capacity and reinserts it.

A Resize Function

Allocate a new, larger bucket array; walk every old node and move it into the new array using the new capacity; then swap arrays. Here is the core index recompute.

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

Moving Nodes Without Reallocating

With chaining you can move existing nodes into the new array instead of allocating new ones. Detach each node, recompute its bucket, and prepend it.

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

Growth Strategy

Doubling capacity keeps amortized insert cost O(1): although a resize is O(n), it happens rarely enough that the average per-insert cost stays constant.

Powers of two also let you use the fast AND mask.

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

Shrinking

Optionally shrink when the load factor drops too low (for example below 0.1) after many deletes. Shrinking reclaims memory but adds rehash cost, so do it conservatively to avoid thrashing.

Open Addressing and Load Factor

Open-addressing tables are far more sensitive to load factor. Performance collapses as alpha approaches 1, so they typically resize at 0.5 to 0.7, lower than chaining's 0.75.

Amortized Cost Demo

Simulate inserts that double capacity at 0.75 and count total work, showing the average stays low.

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

Quick Check

Test your understanding of resizing.

Recap

You learned to tune hash-table performance.

Load factor = size / capacity
Resize when it exceeds a threshold (about 0.75 for chaining)
Rehash because indices depend on capacity
Doubling gives amortized O(1) inserts

Frequently asked questions

Is the “Resizing and Load Factor” lesson free?

Yes — the full text of “Resizing and Load Factor” is free to read here on the web, and the C Academy course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the C Academy course, upgrade to CoddyKit PRO.

What will I learn in “Resizing and Load Factor”?

Performance tuning. You practise C Academy with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start C Academy?

No prior experience is required. C Academy on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Resizing and Load Factor” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this C Academy lesson?

Yes. Every C Academy lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

← Back to C Academy