Collision Handling Using Chaining in DSA C#

Mental Model

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

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

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

Dry Run Walkthrough

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

Goal: Show how collisions are handled by storing multiple keys in the same bucket using linked lists

Step 1: Insert key 5 at index 0 (5 % 5 = 0)

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

Why: Place key 5 in its bucket since it's empty

Step 2: Insert key 15 at index 0 (15 % 5 = 0), collision occurs

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

Why: Add 15 at the front of the linked list to handle collision

Step 3: Insert key 3 at index 3 (3 % 5 = 3)

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

Why: Place key 3 in its empty bucket

Result:

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

Annotated Code

DSA C#

using System;

class Node
{
    public int Key;
    public Node Next;
    public Node(int key) { Key = key; Next = null; }
}

class HashTable
{
    private int size;
    private Node[] table;

    public HashTable(int size)
    {
        this.size = size;
        table = new Node[size];
    }

    public void Insert(int key)
    {
        int index = key % size; // compute bucket index
        Node newNode = new Node(key);
        // Insert at head of linked list for chaining
        newNode.Next = table[index]; // link new node to current head
        table[index] = newNode; // update head to new node
    }

    public void PrintTable()
    {
        for (int i = 0; i < size; i++)
        {
            Console.Write("[{0}] -> ", i);
            Node curr = table[i];
            while (curr != null)
            {
                Console.Write(curr.Key + " -> ");
                curr = curr.Next; // move to next node
            }
            Console.WriteLine("null");
        }
    }
}

class Program
{
    static void Main()
    {
        HashTable ht = new HashTable(5);
        ht.Insert(5);
        ht.Insert(15);
        ht.Insert(3);
        ht.PrintTable();
    }
}

int index = key % size; // compute bucket index

calculate bucket index using modulo to find where key belongs

newNode.Next = table[index]; // link new node to current head

attach new node before current head to handle collisions by chaining

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

update bucket head to new node, inserting at front of chain

curr = curr.Next; // move to next node

traverse linked list in bucket to print all keys

Output

[0] -> 15 -> 5 -> null

[1] -> null

[2] -> null

[3] -> 3 -> null

[4] -> null

Complexity Analysis

Time: O(1) average for insert because we add at the head of the linked list; worst case O(n) if all keys collide in one bucket

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

vs Alternative: Compared to open addressing which stores keys directly in array slots, chaining uses extra linked lists but handles collisions more flexibly without clustering

Edge Cases

Inserting into an empty bucket

Key is placed directly as the head node of the bucket's linked list

DSA C#

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

Inserting multiple keys that hash to the same bucket

New keys are added at the front of the linked list, preserving all keys

DSA C#

newNode.Next = table[index]; // link new node to current head

Hash table size is small causing many collisions

Linked lists grow longer but insertion still works by chaining

DSA C#

newNode.Next = table[index]; // link new node to current head

When to Use This Pattern

When you see a hash table problem with collisions, reach for chaining because it stores multiple keys in a linked list at each bucket to avoid losing data.

Common Mistakes

Mistake: Overwriting the bucket head without linking the old nodes causes loss of existing keys
Fix: Always link the new node's next pointer to the current head before updating the bucket head

Summary

It handles collisions in hash tables by storing multiple keys in a linked list at each bucket.

Use it when multiple keys can hash to the same index and you want to keep all keys safely.

The key insight is to keep a chain (linked list) of keys in each bucket instead of replacing existing keys.

Practice

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

easy

A. Replace the existing element with the new one

B. Resize the hash table immediately when collision occurs

C. Store collided elements in a linked list at the same index

D. Ignore the new element causing collision

Solution

1. Step 1: Understand collision in hash tables

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

2. Step 2: How chaining handles collisions

   Chaining stores all collided elements in a linked list at that index.

3. Final Answer:

   Store collided elements in a linked list at the same index -> Option C

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Chaining means linked list at one index [OK]

Common Mistakes:

• Thinking chaining replaces old elements
• Confusing chaining with open addressing
• Assuming collisions are ignored

2. Which of the following is the correct way to declare a hash table with chaining in C# using List<T> for chaining?

easy

A. Dictionary hashTable = new Dictionary();

B. Dictionary hashTable = new Dictionary();

C. List hashTable = new List();

D. Dictionary hashTable = new Dictionary();

Solution

1. Step 1: Understand chaining data structure

   Chaining uses a list to store multiple values per key index.

2. Step 2: Correct C# syntax for dictionary with list values

   Dictionary means keys are int, values are lists of strings.

3. Final Answer:

   Dictionary hashTable = new Dictionary(); -> Option D

4. Quick Check:

   Dictionary with List values = Dictionary hashTable = new Dictionary(); [OK]

Hint: Use Dictionary with List as value for chaining [OK]

Common Mistakes:

• Using List with two generic types (invalid)
• Using Dictionary with simple string values only
• Confusing key and value types

3. What will be the output of the following C# code snippet using chaining?

var hashTable = new Dictionary();
int key = 2;
if (!hashTable.ContainsKey(key))
    hashTable[key] = new List<string>();
hashTable[key].Add("apple");
hashTable[key].Add("banana");

foreach(var item in hashTable[key])
    Console.Write(item + " ");

medium

A. No output

B. apple banana

C. apple

D. banana apple

Solution

1. Step 1: Initialize dictionary and add list for key 2

   Since key 2 is not present, a new list is created and assigned.

2. Step 2: Add "apple" and "banana" to list at key 2

   Both strings are added in order: "apple", then "banana".

3. Step 3: Print all items in list at key 2

   Loop prints "apple " then "banana " in order.

4. Final Answer:

   apple banana -> Option B

5. Quick Check:

   List order preserved = apple banana [OK]

Hint: Items print in insertion order in chaining list [OK]

Common Mistakes:

• Assuming reversed order output
• Forgetting to initialize list before adding
• Expecting no output if key missing

4. Identify the error in this C# code snippet implementing chaining:

var hashTable = new Dictionary();
int key = 5;
hashTable[key].Add("orange");

medium

A. Key does not exist; list not initialized before Add

B. Dictionary cannot have List as value type

C. Add method does not exist for List

D. Key must be string, not int

Solution

1. Step 1: Check if key 5 exists in dictionary

   Key 5 is not added yet, so hashTable[key] is null.

2. Step 2: Adding to null list causes runtime error

   Cannot call Add on null; list must be initialized first.

3. Final Answer:

   Key does not exist; list not initialized before Add -> Option A

4. Quick Check:

   Initialize list before Add [OK]

Hint: Always initialize list before adding elements [OK]

Common Mistakes:

• Assuming dictionary auto-creates lists
• Confusing key types
• Thinking Add method is invalid

5. You want to implement a hash table with chaining in C# that stores multiple values per key and supports removing a specific value from the chain. Which approach correctly supports this feature?

hard

A. Use Dictionary and call Remove(value) on the list at the key

B. Use Dictionary and overwrite value to remove

C. Use Dictionary but clear entire list to remove one value

D. Use Dictionary but do not implement removal

Solution

1. Step 1: Understand chaining with multiple values per key

   Chaining uses a list to hold multiple values at one key.

2. Step 2: Removing a specific value requires list's Remove method

   List<string> supports Remove(value) to delete one item without affecting others.

3. Step 3: Other options either overwrite or clear all values, not specific removal

   Overwriting loses all values; clearing removes all; ignoring removal is incomplete.

4. Final Answer:

   Use Dictionary and call Remove(value) on the list at the key -> Option A

5. Quick Check:

   List Remove supports specific value deletion [OK]

Hint: Use List and Remove(value) to delete specific chained item [OK]

Common Mistakes:

• Overwriting value instead of removing one
• Clearing entire list to remove one item
• Ignoring removal feature