C in 100 Seconds: Hash Table Chaining

Hash Table — Chaining Implementation

Last episode, collisions overwrote values. Chaining fixes that — each bucket holds a linked list, so multiple keys can share the same index.

The Entry Struct

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

Each entry has a key, a value, and a next pointer to chain with other entries at the same bucket.

Insert — Prepend to Chain

void insert(char *key, int value) {
  int idx = hash(key);
  Entry *e = malloc(sizeof(Entry));
  e->key = key;
  e->value = value;
  e->next = table[idx];
  table[idx] = e;
}

New entries prepend to the front of the chain. Works even if the bucket is empty — NULL becomes the next pointer.

Lookup — Walk the Chain

int lookup(char *key) {
  Entry *e = table[hash(key)];
  while (e != NULL) {
    if (strcmp(e->key, key) == 0) return e->value;
    e = e->next;
  }
  return -1;
}

Walk the chain comparing keys with strcmp. Return the value on match, or -1 if not found.

Delete — Rewire and Free

Find the entry, rewire the previous node's next pointer to skip it, then free. Same pattern as deleting from a linked list.

Student Code

Try it yourself: episode49/hashmap.c