Collision Handling Using Chaining in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting keys with collisions in chaining hash table

What is the printed state of the hash table buckets after inserting keys 5, 15, 25 into a hash table of size 10 using chaining with hash function key % 10?

DSA C#

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

class HashTable {
    private Node[] buckets = new Node[10];

    private int Hash(int key) => key % 10;

    public void Insert(int key) {
        int index = Hash(key);
        Node newNode = new Node(key);
        if (buckets[index] == null) {
            buckets[index] = newNode;
        } else {
            Node current = buckets[index];
            while (current.Next != null) {
                current = current.Next;
            }
            current.Next = newNode;
        }
    }

    public void Print() {
        for (int i = 0; i < buckets.Length; i++) {
            Console.Write(i + ": ");
            Node current = buckets[i];
            while (current != null) {
                Console.Write(current.Key + " -> ");
                current = current.Next;
            }
            Console.WriteLine("null");
        }
    }
}

var ht = new HashTable();
ht.Insert(5);
ht.Insert(15);
ht.Insert(25);
ht.Print();

A

0: null
1: null
2: null
3: null
4: null
5: 25 -> 15 -> 5 -> null
6: null
7: null
8: null
9: null

B

0: null
1: null
2: null
3: null
4: null
5: 5 -> 15 -> 25 -> null
6: null
7: null
8: null
9: null

C

0: null
1: null
2: null
3: null
4: null
5: 5 -> null
6: null
7: null
8: null
9: 15 -> 25 -> null

D

0: null
1: null
2: null
3: null
4: null
5: 15 -> 5 -> 25 -> null
6: null
7: null
8: null
9: null

💡 Hint

Remember that chaining adds new nodes at the end of the linked list in the bucket.

The hash function key % 10 maps 5, 15, and 25 all to bucket 5. They are inserted in order, so the linked list at bucket 5 is 5 -> 15 -> 25 -> null.

🧠 Conceptual

intermediate

Number of items in a bucket after collisions

If a hash table uses chaining and the hash function maps keys 12, 22, 32, and 42 to the same bucket, how many nodes will be in that bucket's linked list after inserting all keys?

A Depends on the size of the hash table

B 1

C 0

D 4

💡 Hint

Each key that hashes to the same bucket adds one node to the linked list.

All four keys map to the same bucket, so the linked list in that bucket will have four nodes, one for each key.

🔧 Debug

advanced

Identify the bug in chaining insertion code

What error will occur when running this chaining insertion code snippet?

DSA C#

public void Insert(int key) {
    int index = key % buckets.Length;
    Node newNode = new Node(key);
    if (buckets[index] == null) {
        buckets[index] = newNode;
    } else {
        Node current = buckets[index];
        while (current.Next != null) {
            current = current.Next;
        }
        current.Next = newNode;
    }
}

A NullReferenceException at current.Next = newNode

B No error, code runs correctly

C IndexOutOfRangeException when accessing buckets

D StackOverflowException due to infinite loop

💡 Hint

Check the while loop condition and what happens when current becomes null.

The while loop continues until current is null, so after the loop current is null. Trying to access current.Next causes NullReferenceException.

❓ Predict Output

advanced

State of hash table after deletions in chaining

Given a hash table with chaining and keys 7, 17, 27 inserted (all hash to bucket 7), what is the bucket 7 state after deleting key 17?

DSA C#

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

class HashTable {
    private Node[] buckets = new Node[10];

    private int Hash(int key) => key % 10;

    public void Insert(int key) {
        int index = Hash(key);
        Node newNode = new Node(key);
        if (buckets[index] == null) {
            buckets[index] = newNode;
        } else {
            Node current = buckets[index];
            while (current.Next != null) {
                current = current.Next;
            }
            current.Next = newNode;
        }
    }

    public void Delete(int key) {
        int index = Hash(key);
        Node current = buckets[index];
        Node prev = null;
        while (current != null) {
            if (current.Key == key) {
                if (prev == null) {
                    buckets[index] = current.Next;
                } else {
                    prev.Next = current.Next;
                }
                return;
            }
            prev = current;
            current = current.Next;
        }
    }

    public void PrintBucket(int index) {
        Console.Write(index + ": ");
        Node current = buckets[index];
        while (current != null) {
            Console.Write(current.Key + " -> ");
            current = current.Next;
        }
        Console.WriteLine("null");
    }
}

var ht = new HashTable();
ht.Insert(7);
ht.Insert(17);
ht.Insert(27);
ht.Delete(17);
ht.PrintBucket(7);

A 7: null

B 7: 17 -> 7 -> 27 -> null

C 7: 7 -> 27 -> null

D 7: 7 -> 17 -> 27 -> null

💡 Hint

Deleting key 17 removes it from the linked list, linking 7 directly to 27.

After deleting 17, the linked list in bucket 7 contains 7 and 27 linked directly.

🧠 Conceptual

expert

Effect of poor hash function on chaining performance

What is the main effect on a hash table using chaining if the hash function maps most keys to the same bucket?

A The hash table behaves like a linked list, causing slower search times

B The hash table will have faster insertions due to fewer buckets used

C The hash table will use less memory overall

D The hash table will automatically resize to fix collisions

💡 Hint

Think about what happens when many keys collide into one bucket.

If many keys map to the same bucket, the linked list grows long, making search, insert, and delete operations slower, similar to a linked list.

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