Collision Handling Using Chaining in DSA C++

Mental Model

When two keys want to go to the same spot in a table, we keep them in a small linked list at that spot.

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

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

Dry Run Walkthrough

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

Goal: Show how collisions are handled by adding nodes to linked lists at the same index

Step 1: Insert 15: compute index 15 % 5 = 0, add 15 at index 0

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

Why: We place 15 in the slot given by the hash function

Step 2: Insert 25: compute index 25 % 5 = 0, collision at index 0, add 25 at front of list

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

Why: Collision handled by chaining: add new node at head of linked list

Step 3: Insert 33: compute index 33 % 5 = 3, add 33 at index 3

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

Why: No collision at index 3, insert normally

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

class Node {
public:
    int key;
    Node* next;
    Node(int k) : key(k), next(nullptr) {}
};

class HashTable {
    int size;
    vector<Node*> table;
public:
    HashTable(int s) : size(s), table(s, nullptr) {}

    int hashFunction(int key) {
        return key % size; // compute index
    }

    void insert(int key) {
        int index = hashFunction(key); // find slot
        Node* newNode = new Node(key); // create node
        newNode->next = table[index]; // link new node to current head
        table[index] = newNode; // update head to new node
    }

    void printTable() {
        for (int i = 0; i < size; i++) {
            cout << "[" << i << "] -> ";
            Node* curr = table[i];
            while (curr) {
                cout << curr->key << " -> ";
                curr = curr->next; // move to next node
            }
            cout << "null" << endl;
        }
    }
};

int main() {
    HashTable ht(5);
    ht.insert(15);
    ht.insert(25);
    ht.insert(33);
    ht.printTable();
    return 0;
}

int index = hashFunction(key); // find slot

compute index using hash function

Node* newNode = new Node(key); // create node

create new node for key

newNode->next = table[index]; // link new node to current head

link new node to existing chain at index

table[index] = newNode; // update head to new node

update head pointer to new node to handle collision

curr = curr->next; // move to next node

traverse linked list to print all keys at index

Output

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

[1] -> null

[2] -> null

[3] -> 33 -> null

[4] -> null

Complexity Analysis

Time: O(1) average for insert because we add at head; worst O(n) if many collisions in one slot

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

vs Alternative: Compared to open addressing, chaining allows easier handling of collisions without probing, but uses extra memory for pointers

Edge Cases

Inserting into empty slot

Node becomes head of linked list at that index

DSA C++

table[index] = newNode; // update head to new node

Multiple keys hashing to same index

New nodes are added at the front of the linked list

DSA C++

newNode->next = table[index]; // link new node to current head

Hash table size is 1 (all keys collide)

All keys form a single linked list at index 0

DSA C++

table[index] = newNode; // update head to new node

When to Use This Pattern

When you see a hash table problem with collisions, reach for chaining because it stores collided keys in linked lists for easy insertion.

Common Mistakes

Mistake: Overwriting existing node instead of linking new node in chain
Fix: Always link new node's next to current head before updating head pointer

Summary

It stores collided keys in linked lists at each hash table index.

Use it when multiple keys can hash to the same index and you want simple collision handling.

The key is to keep a linked list at each slot to hold all collided keys.

Practice

1. What is the main idea behind collision handling using chaining in hash tables?

easy

A. Store all elements that hash to the same index in a linked list at that index

B. Resize the hash table when a collision occurs

C. Use a second hash function to find a new index

D. Ignore collisions and overwrite existing data

Solution

1. Step 1: Understand collision in hash tables

   When two keys hash to the same index, a collision occurs.

2. Step 2: Explain chaining method

   Chaining stores all collided elements in a linked list at that index to keep them separate.

3. Final Answer:

   Store all elements that hash to the same index in a linked list at that index -> Option A

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Chaining means linked list at each hash index [OK]

Common Mistakes:

• Thinking chaining resizes the table
• Confusing chaining with open addressing
• Ignoring collisions instead of handling them

2. Which of the following is the correct way to declare a hash table using chaining in C++?

easy

A. std::vector<int> hashTable(size);

B. std::list hashTable(size);

C. std::vector hashTable(size);

D. std::list<int> hashTable(size);

Solution

1. Step 1: Understand chaining data structure

   Chaining uses a list at each index, so a vector of lists is needed.

2. Step 2: Check syntax correctness

   std::vector creates a vector where each element is a list, perfect for chaining.

3. Final Answer:

   std::vector hashTable(size); -> Option C

4. Quick Check:

   Vector of lists = chaining hash table [OK]

Hint: Chaining = vector of lists in C++ [OK]

Common Mistakes:

• Using list of vectors instead of vector of lists
• Using vector of ints only (no chaining)
• Incorrect container nesting order

3. Consider the following code snippet using chaining for collision handling:

std::vector hashTable(5);
int hashFunction(int key) { return key % 5; }

// Insert keys
hashTable[hashFunction(7)].push_back(7);
hashTable[hashFunction(12)].push_back(12);
hashTable[hashFunction(17)].push_back(17);

// Print contents at index 2
for (int val : hashTable[2]) {
    std::cout << val << " ";
}

What will be the output?

medium

A. 7 12 17

B. 12 17

C. 7

D. No output

Solution

1. Step 1: Calculate hash indices for keys

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2. All keys go to index 2.

2. Step 2: Check what is printed at index 2

   All three keys (7, 12, 17) are stored in the list at index 2 and printed in insertion order.

3. Final Answer:

   7 12 17 -> Option A

4. Quick Check:

   Keys mod 5 = 2, print all at index 2 [OK]

Hint: Calculate key % size to find index [OK]

Common Mistakes:

• Forgetting all keys collide at index 2
• Printing keys at wrong index
• Assuming keys overwrite each other

4. The following code attempts to insert keys into a hash table using chaining but causes a runtime error:

std::vector hashTable;
int hashFunction(int key) { return key % 10; }

void insertKey(int key) {
    int index = hashFunction(key);
    hashTable[index].push_back(key);
}

int main() {
    insertKey(15);
    insertKey(25);
    return 0;
}

What is the error and how to fix it?

medium

A. hashFunction returns wrong index; change modulo to 5

B. hashTable is empty; initialize with size before insertions

C. push_back is wrong method; use insert instead

D. No error; code runs fine

Solution

1. Step 1: Identify cause of runtime error

   hashTable is declared but not sized, so accessing hashTable[index] causes out-of-range error.

2. Step 2: Fix by initializing hashTable size

   Initialize hashTable with size 10 (e.g., std::vector hashTable(10);) before insertions.

3. Final Answer:

   hashTable is empty; initialize with size before insertions -> Option B

4. Quick Check:

   Vector size must match hash range [OK]

Hint: Initialize vector size before accessing indices [OK]

Common Mistakes:

• Ignoring vector size causes crash
• Changing hash function unnecessarily
• Using wrong list methods

5. You have a hash table of size 7 using chaining. You insert keys: 10, 21, 17, 14, 28, 35.
After all insertions, which index will have the longest chain and what will be its contents?
Use hash function: index = key % 7.

hard

A. Index 0: 10 -> 21 -> 35

B. Index 3: 10 -> 17

C. Index 4: 21 -> 14

D. Index 0: 21 -> 14 -> 28 -> 35

Solution

1. Step 1: Calculate hash indices for each key

   10 % 7 = 3, 21 % 7 = 0, 17 % 7 = 3, 14 % 7 = 0, 28 % 7 = 0, 35 % 7 = 0.

2. Step 2: Group keys by index

   Index 0: 21, 14, 28, 35 (4 keys); Index 3: 10, 17 (2 keys).

3. Step 3: Identify longest chain and contents

   Index 0 has the longest chain with keys 21, 14, 28, 35 inserted in order.

4. Final Answer:

   Index 0: 21 -> 14 -> 28 -> 35 -> Option D

5. Quick Check:

   Keys mod 7 grouped; longest chain at index 0 [OK]

Hint: Calculate key % size, count keys per index [OK]

Common Mistakes:

• Miscomputing modulo results
• Mixing up indices and keys
• Ignoring insertion order in chain