C: a hash index with chaining

Before you start

C structs, pointers, malloc, and linked lists.

Store keys in buckets of linked lists and see how collisions lengthen a lookup.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

With few collisions each list has about one entry, so a lookup takes O(1) comparisons on average. If many keys collide the chains grow and the lookup degrades toward a linear scan. Real systems keep the load factor low by resizing the table and use hash functions that spread keys evenly. The keys 3, 11, and 19 all map to bucket 3 here, which shows the cost of a poor spread.

Code example

#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;
}

Output

bucket 3 holds 3 key(s)
bucket 5 holds 3 key(s)
bucket 7 holds 1 key(s)
lookup 19: found after 1 comparison(s)
lookup 3: found after 3 comparison(s)
lookup 4: not found after 0 comparison(s)
lookup 27: not found after 3 comparison(s)

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1#include <stdio.h>

2#include <stdlib.h>

4#define BUCKETS 8

6typedef struct Node {

7 int key;

8 struct Node *next;

9} Node;

11static Node *table[BUCKETS];

13static void insert(int key) {

14 Node *node = malloc(sizeof *node);

15 if (node == NULL) {

16 exit(1);

17 }

18 node->key = key;

19 node->next = table[key % BUCKETS];

20 table[key % BUCKETS] = node;

21}

23static int lookup(int key, int *comparisons) {

24 *comparisons = 0;

25 for (Node *n = table[key % BUCKETS]; n != NULL; n = n->next) {

26 (*comparisons)++;

27 if (n->key == key) {

28 return 1;

29 }

30 }

31 return 0;

32}

34int main(void) {

35 int keys[] = {3, 11, 19, 5, 13, 21, 7};

36 for (int i = 0; i < 7; i++) {

37 insert(keys[i]);

38 }

40 for (int b = 0; b < BUCKETS; b++) {

41 int length = 0;

42 for (Node *n = table[b]; n != NULL; n = n->next) {

43 length++;

44 }

45 if (length > 0) {

46 printf("bucket %d holds %d key(s)\n", b, length);

47 }

48 }

50 int probes[] = {19, 3, 4, 27};

51 for (int i = 0; i < 4; i++) {

52 int comparisons;

53 int found = lookup(probes[i], &comparisons);

54 printf("lookup %d: %s after %d comparison(s)\n", probes[i], found ? "found" : "not found", comparisons);

55 }

57 for (int b = 0; b < BUCKETS; b++) {

58 Node *n = table[b];

59 while (n != NULL) {

60 Node *next = n->next;

61 free(n);

62 n = next;

63 }

64 }

65 return 0;

66}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
New nodes are added at the head of the bucket's list, which is O(1).	`—`	—
3, 11, and 19 collide in bucket 3, and 5, 13, and 21 collide in bucket 5.	`—`	bucket 3 holds 3 key(s) bucket 5 holds 3 key(s) bucket 7 holds 1 key(s)
A lookup scans only one chain. The newest key in a chain is found first.	`—`	bucket 3 holds 3 key(s) bucket 5 holds 3 key(s) bucket 7 holds 1 key(s)
19 is first in its chain, 3 is last. Key 4 hits an empty bucket, and 27 is missing from a full chain of 3.	`—`	bucket 3 holds 3 key(s) bucket 5 holds 3 key(s) bucket 7 holds 1 key(s) lookup 19: found after 1 comparison(s) lookup 3: found after 3 comparison(s) lookup 4: not found after 0 comparison(s) lookup 27: not found after 3 comparison(s)

Behind the scenes

How C processes this code

The C compiler produces a native program. Variables occupy memory, and execution enters main.

Cost and common mistakes

Average O(1) per lookup with a low load factor; worst case O(n) when all keys collide.

Negative keys make key % BUCKETS negative in C, which is an invalid array index. Use an unsigned hash.
Every malloc needs a matching free. The cleanup loop walks each chain.
Keys that follow a pattern, such as multiples of 8, all land in one bucket. A good hash function mixes the bits.

Try it yourself

What is the load factor of this table?

Reveal answer and reasoning

7 keys in 8 buckets gives a load factor of 7 / 8 = 0.875.