Collision Handling Using Chaining in DSA C++ - Build from Scratch

Collision Handling Using Chaining

📖 Scenario: Imagine you are building a simple phone book application that stores names and phone numbers. To quickly find a phone number by name, you use a hash table. Sometimes, two names might hash to the same spot. To handle this, you will use chaining, which means storing multiple entries in a list at the same spot.

🎯 Goal: You will create a hash table using chaining to handle collisions. You will insert some names and phone numbers, then display the hash table's contents showing how collisions are handled.

📋 What You'll Learn

Create a hash table with 5 buckets using an array of linked lists

Insert exactly these entries: ('Alice', 12345), ('Bob', 67890), ('Charlie', 54321), ('David', 98765), ('Eve', 19283)

Use a simple hash function: sum of characters in the name modulo 5

Display the hash table showing each bucket and the linked list of entries

💡 Why This Matters

🌍 Real World

Hash tables with chaining are used in many applications like databases, caches, and symbol tables in compilers to efficiently store and retrieve data even when collisions occur.

💼 Career

Understanding collision handling is essential for software engineers working on performance-critical systems, data storage, and designing efficient algorithms.

1

Create the hash table buckets

Create an array called hashTable of size 5 where each element is a std::list of std::pair<std::string, int>.

DSA C++

#include 
#include 
#include 

int main() {
    // Create hashTable array of 5 lists of pairs
    // Your code here
}

Hint

Use std::list<std::pair<std::string, int>> hashTable[5]; to create the array of linked lists.

2

Create the hash function

Create a function called hashFunction that takes a const std::string &name and returns an int. It should calculate the sum of ASCII values of characters in name modulo 5.

DSA C++

#include 
#include 
#include 

// Create hashFunction here

int main() {
    std::list> hashTable[5];
}

Hint

Loop over each character in name, add its ASCII value to sum, then return sum % 5.

3

Insert entries into the hash table

Insert these entries into hashTable using chaining: ("Alice", 12345), ("Bob", 67890), ("Charlie", 54321), ("David", 98765), ("Eve", 19283). Use hashFunction to find the bucket index and add the pair to the corresponding list.

DSA C++

#include 
#include 
#include 

int hashFunction(const std::string &name) {
    int sum = 0;
    for (char c : name) {
        sum += c;
    }
    return sum % 5;
}

int main() {
    std::list> hashTable[5];
    // Insert entries into hashTable
    // Your code here
}

Hint

Use hashTable[hashFunction(name)].push_back({name, number}); for each entry.

4

Display the hash table contents

Use a for loop with variable i from 0 to 4 to print each bucket number. Inside, use a for loop with variables entry to iterate over hashTable[i] and print each entry.first and entry.second separated by a colon. Format each bucket as: Bucket i: name1:number1 -> name2:number2 -> null.

DSA C++

#include 
#include 
#include 

int hashFunction(const std::string &name) {
    int sum = 0;
    for (char c : name) {
        sum += c;
    }
    return sum % 5;
}

int main() {
    std::list> hashTable[5];

    hashTable[hashFunction("Alice")].push_back({"Alice", 12345});
    hashTable[hashFunction("Bob")].push_back({"Bob", 67890});
    hashTable[hashFunction("Charlie")].push_back({"Charlie", 54321});
    hashTable[hashFunction("David")].push_back({"David", 98765});
    hashTable[hashFunction("Eve")].push_back({"Eve", 19283});

    // Print hash table contents
    // Your code here
}

Hint

Use nested loops: outer loop from 0 to 4 for buckets, inner loop over hashTable[i]. Print each entry as name:number -> , then print null at the end of each bucket line.

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