Rehashed With Old Modulus

This chained hash table doubles its bucket array. Capacities are always powers of two and n->hash caches the full hash of the key. Lookup elsewhere in the file computes n->hash % t->capacity.

void grow(HashTable *t) {
    int old_cap = t->capacity;
    Node **old = t->buckets;

    t->capacity = old_cap * 2;
    t->buckets  = calloc(t->capacity, sizeof(Node *));

    for (int i = 0; i < old_cap; i++) {
        Node *n = old[i];
        while (n) {
            Node *next = n->next;
            int j = n->hash % old_cap;      /* line 12 */
            n->next = t->buckets[j];
            t->buckets[j] = n;
            n = next;
        }
    }
    free(old);
}

What does a user of this table observe after the first grow?

A

The heap is corrupted, because free(old) releases memory that the relinked nodes still point into

B

Roughly half the keys already stored become unfindable, while lookups for the other half keep succeeding

C

Every key stays findable, but the upper half of the bucket array is never used, so lookups degrade toward O(n)

D

Every lookup fails after the first grow, including keys inserted afterwards