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?
Sign in to answer questions and track your progress
Sign In