C: a hash index with chaining

A hash index maps a key to a bucket with a hash function, here key % 8. Different keys can land in the same bucket, which is called a collision. Chaining handles it by keeping a linked list in each bucket. A lookup computes the bucket and then scans only that list.

#include <stdio.h>
#include <stdlib.h>

#define BUCKETS 8

typedef struct Node {
  int key;
  struct Node *next;
} Node;

static Node *table[BUCKETS];

static void insert(int key) {
  Node *node = malloc(sizeof *node);
  if (node == NULL) {
    exit(1);
  }
  node->key = key;
  node->next = table[key % BUCKETS];
  table[key % BUCKETS] = node;
}

static int lookup(int key, int *comparisons) {
  *comparisons = 0;
  for (Node *n = table[key % BUCKETS]; n != NULL; n = n->next) {
    (*comparisons)++;
    if (n->key == key) {
      return 1;
    }
  }
  return 0;
}

int main(void) {
  int keys[] = {3, 11, 19, 5, 13, 21, 7};
  for (int i = 0; i < 7; i++) {
    insert(keys[i]);
  }

  for (int b = 0; b < BUCKETS; b++) {
    int length = 0;
    for (Node *n = table[b]; n != NULL; n = n->next) {
      length++;
    }
    if (length > 0) {
      printf("bucket %d holds %d key(s)\n", b, length);
    }
  }

  int probes[] = {19, 3, 4, 27};
  for (int i = 0; i < 4; i++) {
    int comparisons;
    int found = lookup(probes[i], &comparisons);
    printf("lookup %d: %s after %d comparison(s)\n", probes[i], found ? "found" : "not found", comparisons);
  }

  for (int b = 0; b < BUCKETS; b++) {
    Node *n = table[b];
    while (n != NULL) {
      Node *next = n->next;
      free(n);
      n = next;
    }
  }
  return 0;
}

Read the full lesson