Routing Back to C [Part 3]: A Hash Table That Can Grow

Part 1 built the mental model: stack, heap, pointers, manual memory. Part 2 built the smallest heap structure, a linked list. Now we stack the two ideas into something you actually reach for at work: a hash table.

The dict, the map, the object, the HashMap, the HashTable: almost every language ships this as its bread-and-butter container, and the insides are almost always the same shape. We’ll build it with separate chaining: an array of buckets, where each bucket is a small linked list of entries whose keys all hashed to that slot.

By the end we’ll put it all together in ht.c, insert enough keys to trigger a resize, and run the whole thing under valgrind to prove there are no leaks. Theory first, the practical build sits at the end.

The Shape

buckets ─→ ┌───┐
           │ 0 │─→ NULL
           ├───┤
           │ 1 │─→ ┌─────────┐
           │   │   │ "apple" │─→ NULL
           ├───┤   └─────────┘
           │ 2 │─→ NULL
           ├───┤
           │ 3 │─→ ┌──────────┐     ┌─────────┐
           │   │   │ "banana" │─→   │ "berry" │─→ NULL
           ├───┤   └──────────┘     └─────────┘
           │ 4 │─→ ┌────────┐
           │   │   │ "lime" │─→ NULL
           └───┘   └────────┘

Three things to notice:

1. The array is contiguous. buckets[0] through buckets[n-1] sit next to each other in memory. One malloc, fixed size.
2. Each chain is heap-scattered. The entries in bucket 3 are two separate heap allocations. The bucket just holds a pointer to the first one; the first one points to the second.
3. Empty buckets are NULL. A bucket with no entries costs 8 bytes of pointer in the array and zero bytes of heap. That’s why calloc is the right tool to allocate the array: it zeroes everything for free.

The Entry and the Table

Two structs. One for each entry in a chain, one for the table wrapper.

typedef struct entry {
    char         *key;
    int           value;
    struct entry *next;
} entry;

typedef struct {
    entry  **buckets;
    size_t   capacity;   // how many bucket slots
    size_t   size;       // how many entries stored
} hash_table;

entry is a linked-list node with a name change and an extra field. key is a heap-owned string (more on that below). value is the payload, an int here to keep things simple, but you can swap it for anything. next chains siblings in the same bucket.

hash_table is the handle the caller holds. buckets is the array of pointers to the first entry in each chain. capacity is the array length. size is the running count of entries, which is what we’ll use to decide when to resize.

Layout and Padding

On 64-bit, entry looks like this in memory:

       0                 8        12       16               24
       ├─────────────────┼────────┼────────┼────────────────┤
bytes: │      key        │ value  │  pad   │      next      │
       │   (8 B ptr)     │ (4 B)  │ (4 B)  │    (8 B ptr)   │
       └─────────────────┴────────┴────────┴────────────────┘
       ▲
   start of entry           total: 24 bytes

Same story as Part 2: the compiler slides next to offset 16 so it lands on an 8-byte boundary. Flipping the fields doesn’t save bytes: the struct size rounds up to a multiple of its largest alignment (8), so arrays of entry still line up.

hash_table itself is three 8-byte fields in a row, no padding needed, total 24 bytes. Whether you malloc one hash_table or ten, each one is 24 bytes of heap plus the allocator’s own overhead.

A single entry with a 6-character key costs you: 24 B for the struct, 8 B of malloc header on the struct, another ~8 B of slack, 7 B for the strdup’d key (6 chars plus \0), 8 B of malloc header on that, and padding to the allocator’s minimum chunk. Storing "apples" → 3 is already north of 60 bytes of heap for what is, at the surface, an 8-byte key-value pair. Abstractions aren’t free.

The Hash Function

We need a function that turns any string into a number. djb2 is the one everybody copies for a reason, three lines, good spread, no external dependencies.

size_t hash(const char *s) {
    size_t h = 5381;
    int    c;
    while ((c = *s++)) {
        h = ((h << 5) + h) + c;   // h * 33 + c
    }
    return h;
}

For "abc":

start:             h = 5381
after 'a' (97):    h = 5381 * 33 + 97  = 177670
after 'b' (98):    h = 177670 * 33 + 98 = 5863208
after 'c' (99):    h = 5863208 * 33 + 99 = 193485963

Why These Magic Numbers?

Two constants, both load-bearing.

5381 is the seed. Any non-zero odd number works; 5381 happened to test well across English text when Dan Bernstein picked it in the 90s. Start with 0 and an empty string still hashes to 0, which collides with a literal zero key later, hence a non-zero seed.

33 is the multiplier. h << 5 is h * 32; (h << 5) + h is h * 33. Multiplying by an odd number that’s not a power of two mixes bits into positions where the next character’s + c can still disturb them. The shift-plus-add trick is a leftover from the era when integer multiplication was slow; modern CPUs do the multiply in one cycle, and compilers usually rewrite h * 33 into the shift form anyway. Leaving it written out makes the intent obvious.

Why not 31 (Java’s choice for String.hashCode)? Also fine, both are small odd primes with good mixing. The literature has no strong verdict; either one produces acceptable distribution for typical string keys.

This is not a cryptographic hash. djb2 is fast and spreads well for friendly inputs, but an attacker who knows you’re using it can craft keys that all collide into one bucket and turn your O(1) lookups into O(n). Production systems (Python, Ruby, Rust) use hashes like SipHash with a random seed per process to defeat that. For a teaching example, djb2 is more than enough.

Picking a Bucket

Once hash(key) returns a size_t (often a 64-bit number), we fold it into the range [0, capacity) with modulo:

size_t i = hash(key) % t->capacity;

Modulo is how “a number that could be anything” becomes “a number that’s a valid array index.” If two different keys produce hashes that agree modulo capacity, they land on the same bucket, a collision.

When bitmask beats modulo. % on a 64-bit integer takes a few cycles. If capacity is a power of two, you can replace hash % capacity with hash & (capacity - 1):

capacity = 16                  mask = 15 = 0b00001111
hash     = 0xABCDEF12

hash & 15   keeps the bottom 4 bits → 0x02 → bucket 2
hash % 16   also gives 2, but slower on some CPUs

The bitmask trick is why most production hash tables force capacity to be a power of two. We’ll use plain modulo here because it works for any capacity and keeps the code easier to read. If you swap in the bitmask, make sure the hash itself spreads bits into the low positions. Some weak hashes put all their variation in the high bits, and the mask would throw it away.

Create the Table

One malloc for the handle, one calloc for the array of bucket pointers.

hash_table *ht_new(size_t capacity) {
    hash_table *t = malloc(sizeof(hash_table));
    if (t == NULL) return NULL;

    t->buckets  = calloc(capacity, sizeof(entry *));
    if (t->buckets == NULL) { free(t); return NULL; }

    t->capacity = capacity;
    t->size     = 0;
    return t;
}

STACK                HEAP
┌──────────┐         ┌─────────┬─────┬──────┐
│    t     │────────→│ buckets │ cap │ size │   hash_table (24 B)
│ (8 B ptr)│         └────┬────┴─────┴──────┘
└──────────┘              │
                          ▼
                    ┌──────┬──────┬──────┬─── ─ ┬──────┐
                    │ NULL │ NULL │ NULL │  …   │ NULL │   capacity slots
                    └──────┴──────┴──────┴─── ─ ┴──────┘

Why calloc for the Bucket Array

Part 2 explained that malloc leaves the bytes uninitialised. For the hash_table handle that’s fine: we assign every field right after. For the bucket array, it’s not: the traversal code will read buckets[i] before anything is written, and needs to see NULL to know the chain is empty.

Two ways to get there:

entry **b = malloc(capacity * sizeof(entry *));
memset(b, 0, capacity * sizeof(entry *));

or

entry **b = calloc(capacity, sizeof(entry *));

calloc does both in one call, allocate and zero. On most systems it’s also smart enough to hand you freshly-mapped OS pages that are already zero, skipping the memset. For a small table the difference is academic; for a 16-million-slot table, the zero-fill is measurable.

Three important notes on “zero” here:

1. On every platform you’ll realistically ship to, the bit pattern of a null pointer is all-zero bits. So calloc zeroing the array is the same as filling it with NULL pointers. The C standard doesn’t technically require this, but in practice it’s true everywhere.
2. calloc(n, size) also checks for multiplication overflow: calloc(SIZE_MAX, 2) fails cleanly instead of wrapping around and allocating 4 bytes.
3. calloc only zeroes what you asked for, same as malloc only gives you what you asked for. The allocator header and trailing slack are still “allocator business”, not yours to read.

Insert

Three things can happen when you call ht_set. Either the bucket is empty, or the bucket has a chain and the key is new, or the key already lives in the chain and we’re updating it. The code handles all three in one pass.

void ht_set(hash_table *t, const char *key, int value) {
    size_t i = hash(key) % t->capacity;

    for (entry *cur = t->buckets[i]; cur != NULL; cur = cur->next) {
        if (strcmp(cur->key, key) == 0) {
            cur->value = value;            // key exists → update in place
            return;
        }
    }

    entry *e   = malloc(sizeof(entry));
    e->key     = strdup(key);              // heap-owned copy
    e->value   = value;
    e->next    = t->buckets[i];            // prepend to chain
    t->buckets[i] = e;
    t->size++;
}

Walk ht_set(t, "banana", 7) on a table where bucket 2 already holds "apple" → 3 and the rest are empty. Assume hash("banana") % 16 == 2, so we collide with "apple".

State before.

buckets[2] ─→ ┌─────────┐
              │ "apple" │ → NULL
              │    3    │
              └─────────┘

Step 1. Walk the chain looking for "banana". Only "apple" is there, strcmp fails, cursor hits NULL.

Step 2. Allocate a fresh entry and strdup the key.

e ─→ ┌──────────┐
     │ "banana" │ → NULL
     │    7     │
     └──────────┘

Step 3. Point e->next at the current bucket head.

e ─→ ┌──────────┐     ┌─────────┐
     │ "banana" │ ──→ │ "apple" │ → NULL
     │    7     │     │    3    │
     └──────────┘     └─────────┘
                          ▲
                          │
                       buckets[2] (still points here)

Step 4. Overwrite the bucket pointer with e. size++.

buckets[2] ─→ ┌──────────┐     ┌─────────┐
              │ "banana" │ ──→ │ "apple" │ → NULL
              │    7     │     │    3    │
              └──────────┘     └─────────┘

Constant-time insert. No walk-to-tail. If a future lookup asks for "banana", it gets answered on the first chain step.

Why strdup the Key

The entry stores char *key. If we assigned the caller’s pointer directly (e->key = key;), two things would break.

Problem 1: caller frees the string. A perfectly reasonable program does this:

char buf[] = "apples";
ht_set(t, buf, 3);
strcpy(buf, "oranges");     // reuse the buffer
ht_set(t, buf, 9);

If ht_set stored the raw pointer, both entries now think their key is "oranges". ht_get(t, "apples") would walk the chain, compare against "oranges", miss, and return NULL. The entry is still there, it just has the wrong label.

Problem 2: caller frees the memory. Even more direct: the caller’s buffer goes out of scope, and the hash table is now holding a pointer into freed memory. Any strcmp against it is use-after-free.

strdup solves both by making the table the owner of an independent copy on the heap. The table now has to free the copy later, which is why ht_free has a free(cur->key) inside the chain walk.

without strdup:                        with strdup:

caller ──┐                             caller ──→ [ "apples" ]
         ▼                                            (caller owns)
      [ "apples" ]  ←── entry->key
                                       entry->key ──→ [ "apples" ]
caller mutates or frees buf                                (table owns)
         ▼
      [ "oranges" ]  ← entry still points here,
                      sees wrong data

Symmetric point on the value. The int value is stored by copy, a 4-byte scalar that lives inside the entry struct. If the value were itself a pointer to caller-owned memory, you’d face the same ownership decision: copy it or borrow it. Most C hash tables pick a convention (“we own all keys, caller owns all values”) and document it. Sloppy ownership is the single biggest source of C bugs; picking a rule and sticking to it is worth more than any optimisation.

Why Push to the Head, Not the Tail

Two reasons.

O(1) vs O(chain length). Pushing to the tail means walking the whole chain first. For most buckets, chains are short (load factor < 1). For a few buckets after a round of bad hashing, they’re not. Head-insert doesn’t care.

Recency. Keys inserted more recently sit near the head. If your access pattern has any recency bias at all (caching workloads, repeated updates, loops that touch the same key twice), recent keys get found faster. Tail-insert does the opposite.

The only reason to tail-insert would be to preserve insertion order for iteration. Java’s LinkedHashMap does it by keeping a separate doubly-linked list across all entries. For a plain hash table, head-insert is strictly better.

Lookup

Same chain walk as insert, but returns the value instead of adding.

int *ht_get(hash_table *t, const char *key) {
    size_t i = hash(key) % t->capacity;
    for (entry *cur = t->buckets[i]; cur != NULL; cur = cur->next) {
        if (strcmp(cur->key, key) == 0) {
            return &cur->value;
        }
    }
    return NULL;
}

ht_get(t, "apple") on the state from earlier:

iter 1:  cur ─→ ["banana" | 7]      strcmp("banana","apple") → not equal
iter 2:         ["banana" | 7] → ["apple" | 3]
                                    cur ───┘
                                    strcmp("apple","apple")  → equal
                                    return &cur->value        → pointer to 3
iter 3:  (never reached)

Why Return a Pointer, Not a Value

Two reasons, both about expressing “absent” and “mutable.”

“Absent” vs “zero.” If ht_get returned int, how does the caller tell "banana" → 0 apart from "banana" does not exist? Returning int * gives us a free sentinel: NULL means “not here,” any other pointer means “here, dereference for the value.”

int *v = ht_get(t, "apple");
if (v == NULL) {
    printf("apple is not in the table\n");
} else {
    printf("apple = %d\n", *v);
}

Cheap updates. A caller who wants to increment a counter can do it without another hash:

int *v = ht_get(t, "hits");
if (v) (*v)++;

One lookup, one memory write. The alternative (ht_set(t, "hits", ht_get(t, "hits") + 1)) hashes twice and walks twice.

The trade-off is that the returned pointer has the same lifetime as the entry it points into. Rehash the table (see below) and every pointer returned earlier becomes stale. For code that holds onto these, that’s a footgun, document it, or copy the value out immediately.

Delete

Removing an entry is the mirror of Part 2’s delete_value, with two pointers walking the chain and one re-link around the doomed entry.

bool ht_delete(hash_table *t, const char *key) {
    size_t i = hash(key) % t->capacity;
    entry *cur  = t->buckets[i];
    entry *prev = NULL;

    while (cur != NULL && strcmp(cur->key, key) != 0) {
        prev = cur;
        cur  = cur->next;
    }

    if (cur == NULL) return false;     // not found

    if (prev == NULL) {
        t->buckets[i] = cur->next;     // removing the head of the chain
    } else {
        prev->next = cur->next;        // skip cur
    }

    free(cur->key);                    // entry owned a strdup'd key
    free(cur);
    t->size--;
    return true;
}

Walk ht_delete(t, "apple") on buckets[2] → ["banana"|7] → ["apple"|3] → ["cherry"|5].

before:
buckets[2] ─→ [banana|7] ─→ [apple|3] ─→ [cherry|5] → NULL

After the while loop, prev = [banana|7], cur = [apple|3].

              prev         cur
               │            │
               ▼            ▼
buckets[2] ─→ [banana|7] ─→ [apple|3] ─→ [cherry|5] → NULL

prev->next = cur->next re-links around [apple|3]:

              prev         cur
               │            │
               ▼            ▼
buckets[2] ─→ [banana|7] ─→ [apple|3] ─→ [cherry|5] → NULL
                     │                    ▲
                     └────────────────────┘

Then free cur->key (the strdup’d "apple" string), then cur itself. Both are separate heap chunks, two frees, not one. Forgetting free(cur->key) is the most common leak in a hand-rolled hash table.

after:
buckets[2] ─→ [banana|7] ─→ [cherry|5] → NULL

Two edge cases the code handles:

• Key not found. Loop exits with cur == NULL. Return false, no frees.
• Removing the head. prev stays NULL. Write t->buckets[i] = cur->next before freeing.

Load Factor: When the Table Slows Down

A hash table’s average lookup is O(1) only while chains stay short. The metric that decides “short” is the load factor, entries divided by buckets.

load_factor = t->size / t->capacity

capacity 16,  size   4   → load factor 0.25    chains ~empty, O(1) clean
capacity 16,  size  12   → load factor 0.75    chains 0–2 long, still fine
capacity 16,  size 100   → load factor 6.25    chains avg 6 long, lookup crawls
capacity 16,  size 10000 → load factor 625     chains avg 625 long, O(n) in disguise

A perfectly spread hash with load factor L gives chains of average length L. Double L, double the average probe count on every lookup. At load factor 100, a “hash table lookup” is walking a 100-node linked list, same O(1)-on-paper, but you’ve thrown the constant factor through the roof.

The fix is to notice when the table is filling up and grow the array. The standard rule of thumb across languages: when load factor crosses 0.75, double the capacity, allocate a fresh bucket array, and rehash every entry into it.

Resize and Rehash

This is the operation that the draft glosses over and the one that makes the data structure actually work at scale.

static void ht_resize(hash_table *t, size_t new_capacity) {
    entry **new_buckets = calloc(new_capacity, sizeof(entry *));
    if (new_buckets == NULL) return;    // out of memory, keep old table

    for (size_t i = 0; i < t->capacity; i++) {
        entry *cur = t->buckets[i];
        while (cur != NULL) {
            entry *next = cur->next;                    // save before we move cur

            size_t j = hash(cur->key) % new_capacity;   // recompute bucket
            cur->next = new_buckets[j];                 // prepend to new chain
            new_buckets[j] = cur;

            cur = next;
        }
    }

    free(t->buckets);
    t->buckets  = new_buckets;
    t->capacity = new_capacity;
}

Three things worth pausing on.

No new malloc per entry. We’re not cloning entries. We’re re-using the exact same heap chunks, just re-threading their next pointers into a new bucket array. Fewer allocations, no need to free old chains, and the strdup’d keys come along for free.

next is saved before cur->next is overwritten. Same trick as Part 2’s free_list loop. Once you rewrite cur->next to point into the new array, you’ve lost the way back to the rest of the old chain. Save it first.

calloc again. New bucket array starts fully NULL-ed. Every prepend expects to find either NULL or a valid chain head, so zero-fill is load-bearing here.

Walking a Resize

Start with capacity = 4, size = 3. Entries: A hashes to old bucket 1, B and C hash to old bucket 3. Assume in the new 8-slot array A lands at 5, B lands at 3, C lands at 7. (Made-up numbers; the point is that the indices change.)

Before.

old buckets (capacity 4):
[0] → NULL
[1] → [A] → NULL
[2] → NULL
[3] → [B] → [C] → NULL

New array allocated.

new buckets (capacity 8):
[0] [1] [2] [3] [4] [5] [6] [7]
 N   N   N   N   N   N   N   N

Walk old bucket 1. Take A, compute hash % 8 = 5, prepend to new[5].

new: [0] [1] [2] [3] [4] [5] [6] [7]
      N   N   N   N   N  [A]→N N   N

Walk old bucket 3. Take B, compute hash % 8 = 3, prepend to new[3].

new: [0] [1] [2] [3]      [4] [5]     [6] [7]
      N   N   N  [B]→N     N  [A]→N    N   N

Take C, compute hash % 8 = 7, prepend to new[7].

new: [0] [1] [2] [3]     [4] [5]     [6] [7]
      N   N   N  [B]→N    N  [A]→N    N  [C]→N

Free old bucket array. Swap in new one.

hash_table after resize:
  capacity = 8
  size     = 3     (unchanged)
  buckets  = new_buckets

Note that the entry structs for A, B, C are literally the same heap chunks as before. Their addresses didn’t move. Their next pointers got rewritten. Any int * the caller was holding from ht_get is still valid: the pointer into cur->value still points to the same bytes.

Why You Can’t memcpy

The temptation is: “the new array is just a bigger version of the old one, why not memcpy(new_buckets, t->buckets, old_capacity * sizeof(entry*))?”

Because hash(key) % 4 and hash(key) % 8 are almost always different indices:

hash("A") = 177670

177670 % 4 = 2         old bucket 2
177670 % 8 = 6         new bucket 6

Every entry’s index changes with the modulus. A memcpy would put every entry in a bucket where ht_get will never look for it, a fully-populated table that answers every lookup with NULL.

There’s a clever wrinkle when capacity is always a power of two and you use the bitmask trick: an entry’s new index is always either the old index, or the old index plus the old capacity. You can split each chain into “stays” and “moves” without a full rehash. Java’s HashMap (Java 8) exploits this. It’s a nice optimisation but not essential for a teaching implementation.

Hooking Resize Into Insert

One line added to ht_set:

void ht_set(hash_table *t, const char *key, int value) {
    if ((t->size + 1) * 4 > t->capacity * 3) {   // load factor > 0.75
        ht_resize(t, t->capacity * 2);
    }

    size_t i = hash(key) % t->capacity;
    /* ... rest unchanged ... */
}

(size + 1) * 4 > capacity * 3 is just (size + 1) / capacity > 0.75 rearranged to avoid floating-point. We check before inserting because a fresh insert is what would push us over the line.

Amortized O(1)

Resize walks every entry. That’s O(n). “But insert is supposed to be O(1)?”

It is, on average. The trick is that resize only fires when the table is already full to the 0.75 mark. To go from a just-resized table of capacity 2c back to the resize trigger, you need another 0.75 * 2c - 0.75 * c = 0.75 * c inserts. Each of those was O(1). The next resize walks 1.5c entries, which is O(n). Spread the resize cost across the inserts that provoked it:

cheap inserts:        n       each costs ~1 unit
expensive resize:     1       costs ~n units

total cost:           ~2n
average per insert:   ~2  = O(1)

That’s what “amortized O(1)” means, the average over a sequence of operations, not a probabilistic claim about any single one. Some individual inserts are genuinely slow. The promise is only that you don’t pay for it over and over.

For a real-time system (game tick, audio callback) you might not be able to afford the occasional O(n) hiccup. The fix is incremental rehashing: keep both arrays alive during a resize and move a few buckets per insert. That’s what Redis does. It’s a lot of bookkeeping; we’re skipping it.

Freeing Everything

Three layers of heap, three layers of free.

void ht_free(hash_table *t) {
    if (t == NULL) return;

    for (size_t i = 0; i < t->capacity; i++) {
        entry *cur = t->buckets[i];
        while (cur != NULL) {
            entry *next = cur->next;
            free(cur->key);           // the strdup'd string
            free(cur);                // the entry struct
            cur = next;
        }
    }
    free(t->buckets);                 // the bucket array
    free(t);                          // the table handle
}

for each bucket:
  for each entry in its chain:
    free(entry->key)       ← layer 1: the string
    free(entry)            ← layer 2: the entry struct
free(buckets)              ← layer 3: the bucket array
free(table)                ← layer 4: the handle itself

Miss free(cur->key) and valgrind tells you exactly how many bytes of keys you leaked. Miss free(t->buckets) and you leak capacity * 8 bytes. Miss free(t) and you leak 24 bytes. Each mistake is visible.

Order matters: you can’t free(cur) then read cur->next. Same rule as Part 2, save the pointer, then free.

Setup

Same toolchain as Part 2. If you don’t already have it:

• Linux (gcc): gcc.gnu.org/install or your distro’s package manager.
• macOS (clang): Xcode Command Line Tools.
• Windows (MSYS2 / MinGW-w64): msys2.org.
• Windows (WSL): Install WSL, then follow the Linux instructions inside it.
• valgrind: valgrind.org/downloads (Linux and WSL only; on macOS use leaks or AddressSanitizer via -fsanitize=address).

Files You’ll Write

One source file again. Create a new directory alongside last post’s linked-list/:

hash-table/
└── ht.c

Everything from this post (the two structs, hash, ht_new, ht_set, ht_get, ht_delete, ht_resize, ht_free, and main) goes in that single file, in the order it appears. At the top:

#define _POSIX_C_SOURCE 200809L   // for strdup on strict compilers

#include <stdio.h>      // printf
#include <stdlib.h>     // malloc, calloc, free
#include <string.h>     // strcmp, strdup
#include <stdbool.h>    // bool
#include <stddef.h>     // size_t

// structs + functions + main go here, in the order they appear in the post

strdup is POSIX, not strict C99. The #define at the top of the file is the conventional way to tell glibc “yes, I want POSIX extensions.” Without it, some compilers warn about implicit declaration of strdup.

Then open a shell inside the hash-table/ folder and compile. On Windows with MSYS2:

> cd D:\path\to\hash-table
> C:\msys64\msys2_shell.cmd -ucrt64 -here

On macOS or Linux, cd in from any terminal. Once you’re in the right directory (ls should show ht.c):

$ cc -Wall -Wextra -o ht ht.c
$ ./ht

One file in, one binary out.

Putting It Together

int main(void) {
    hash_table *t = ht_new(4);        // tiny capacity to force a resize

    ht_set(t, "apples",  3);
    ht_set(t, "bananas", 7);
    ht_set(t, "limes",   12);
    ht_set(t, "pears",   4);          // this one trips 0.75, resize fires
    ht_set(t, "apples",  5);          // update

    int *v = ht_get(t, "apples");
    printf("apples  = %d  (capacity now %zu)\n", v ? *v : -1, t->capacity);

    ht_delete(t, "bananas");
    v = ht_get(t, "bananas");
    printf("bananas = %s\n", v ? "found" : "not found");

    ht_free(t);
    return 0;
}

Build and run:

$ cc -Wall -Wextra -o ht ht.c
$ ./ht
apples  = 5  (capacity now 8)
bananas = not found

Then under valgrind:

$ valgrind --leak-check=full ./ht
...
All heap blocks were freed -- no leaks are possible
ERROR SUMMARY: 0 errors from 0 contexts

If valgrind reports “definitely lost”, you missed a free. Most likely a free(cur->key) inside ht_free or ht_delete. If it reports “invalid read”, you read a pointer after free. The pattern is always the same: match every malloc/strdup/calloc with exactly one free along every path.

Stress it a bit to feel the resize:

char buf[32];
for (int i = 0; i < 10000; i++) {
    snprintf(buf, sizeof buf, "key_%d", i);
    ht_set(t, buf, i);
}
printf("stored %zu entries in %zu buckets\n", t->size, t->capacity);

You’ll watch capacity double through 4 → 8 → 16 → 32 → 64 → 128 → … → 16384. valgrind will still come back clean.

What It Cost

Python’s dict uses open addressing rather than chaining, and it’s written in C. Go’s map is a chained table with some clever growth. Java’s HashMap is chained and switches to a red-black tree above chain length 8. They’re all the same shape as what you just wrote, with twenty years of optimisation and a threat model stapled on.

One ratio worth keeping in mind, from the cost walk earlier: a ("apples", 3) entry in this table costs roughly 60 bytes of heap for 8 bytes of data. Every hash-table-heavy workload pays this tax.

What’s Next

Part 4: a binary search tree. Pointers and recursion in one structure, and the first time we’ll have to free a shape that doesn’t lie flat: you’ll traverse post-order so children are freed before parents. Same malloc discipline, a new kind of cursor.

Glossary

• Hash table: an array of buckets indexed by a hash of the key. Average O(1) lookup and insert.
• Bucket: one slot in the array. Holds the chain of entries whose keys all hashed here.
• Hash function: turns a key into a number. Good ones spread keys evenly across buckets.
• Collision: two different keys hashing to the same bucket. Not an error, every table handles it.
• Chaining: collision strategy where each bucket is a linked list.
• Open addressing: collision strategy where entries live inside the bucket array itself.
• Load factor: size / capacity. The fullness metric that tells you when to resize.
• Rehash: recompute every entry’s bucket index after resizing. Can’t memcpy: the indices change.
• Amortized: the per-operation cost averaged across many. Resize is O(n) but fires rarely enough that inserts stay O(1) on average.
• strdup: libc helper that mallocs a copy of a string. The caller owns the copy and must free it.
• calloc: like malloc, but zeros the memory before returning.