Collision Handling Using Chaining in DSA C

Mental Model

When two keys want the same spot in a table, we keep a list there to hold both.

Analogy: Imagine a mailbox with several slots. If two letters come for the same slot, you put them in a small basket inside that slot instead of throwing one away.

Hash Table:
[0] -> 15 -> 25 -> null
[1] -> null
[2] -> 7 -> 12 -> null
[3] -> null
[4] -> null

Dry Run Walkthrough

Input: Insert keys 15, 25, 7, 12 into a hash table of size 5 using chaining

Goal: Show how collisions are handled by linking nodes in the same bucket

Step 1: Insert 15 at index 15 % 5 = 0

[0] -> 15 -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: 15 goes to bucket 0 because 15 mod 5 is 0

Step 2: Insert 25 at index 25 % 5 = 0, collision with 15

[0] -> 15 -> 25 -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: 25 also maps to bucket 0, so we add it to the chain after 15

Step 3: Insert 7 at index 7 % 5 = 2

[0] -> 15 -> 25 -> null
[1] -> null
[2] -> 7 -> null
[3] -> null
[4] -> null

Why: 7 goes to bucket 2 with no collision

Step 4: Insert 12 at index 12 % 5 = 2, collision with 7

[0] -> 15 -> 25 -> null
[1] -> null
[2] -> 7 -> 12 -> null
[3] -> null
[4] -> null

Why: 12 also maps to bucket 2, so we add it to the chain after 7

Result:

[0] -> 15 -> 25 -> null
[1] -> null
[2] -> 7 -> 12 -> null
[3] -> null
[4] -> null

Annotated Code

DSA C

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

#define TABLE_SIZE 5

// Node for linked list in each bucket
typedef struct Node {
    int key;
    struct Node* next;
} Node;

// Hash table with chaining
Node* hashTable[TABLE_SIZE];

// Hash function
int hash(int key) {
    return key % TABLE_SIZE;
}

// Insert key into hash table
void insert(int key) {
    int index = hash(key); // find bucket
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = NULL;

    if (hashTable[index] == NULL) {
        hashTable[index] = newNode; // empty bucket
    } else {
        // collision: add to end of chain
        Node* curr = hashTable[index];
        while (curr->next != NULL) {
            curr = curr->next; // advance to last node
        }
        curr->next = newNode; // link new node
    }
}

// Print the hash table
void printTable() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("[%d] -> ", i);
        Node* curr = hashTable[i];
        while (curr != NULL) {
            printf("%d -> ", curr->key);
            curr = curr->next; // advance in chain
        }
        printf("null\n");
    }
}

int main() {
    // Initialize table
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }

    // Insert keys
    insert(15);
    insert(25);
    insert(7);
    insert(12);

    // Print final table
    printTable();
    return 0;
}

int index = hash(key); // find bucket

compute bucket index using hash function

if (hashTable[index] == NULL) { hashTable[index] = newNode; // empty bucket } else { Node* curr = hashTable[index]; while (curr->next != NULL) { curr = curr->next; // advance to last node } curr->next = newNode; // link new node }

handle collision by adding new node at end of linked list in bucket

while (curr != NULL) { printf("%d -> ", curr->key); curr = curr->next; // advance in chain }

traverse linked list in bucket to print all keys

Output

[0] -> 15 -> 25 -> null

[1] -> null

[2] -> 7 -> 12 -> null

[3] -> null

[4] -> null

Complexity Analysis

Time: O(n) in worst case because all keys could hash to same bucket and form a chain, but average O(1) if keys distribute well

Space: O(n) because we store all keys in linked lists inside the table

vs Alternative: Compared to open addressing, chaining uses extra memory for linked lists but handles collisions more flexibly without clustering

Edge Cases

Inserting into an empty bucket

Key is placed directly without collision

DSA C

if (hashTable[index] == NULL) { hashTable[index] = newNode; }

Multiple keys hashing to same bucket

Keys are linked in a chain in that bucket

DSA C

while (curr->next != NULL) { curr = curr->next; } curr->next = newNode;

Printing empty buckets

Prints bucket index followed by null

DSA C

while (curr != NULL) { ... } printf("null\n");

When to Use This Pattern

When you see a hash table with collisions and need to store multiple keys per bucket, use chaining to keep a linked list of keys in each bucket.

Common Mistakes

Mistake: Overwriting existing key in bucket instead of chaining
Fix: Always add new node at end of linked list instead of replacing head

Mistake: Not handling empty bucket case separately
Fix: Check if bucket is NULL before traversing chain

Summary

It stores multiple keys in the same bucket by linking them in a list.

Use it when hash collisions happen and you want to keep all keys safely.

The key is to keep a chain (linked list) at each bucket to hold collided keys.