Collision Handling Using Chaining in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to add a new key-value pair to the hash table using chaining.

DSA C#

public void Add(int key, string value) {
    int index = GetHash(key);
    if (buckets[index] == null) {
        buckets[index] = new LinkedList<KeyValuePair<int, string>>();
    }
    buckets[index].[1](new KeyValuePair<int, string>(key, value));
}

Drag options to blanks, or click blank then click option'

AAddFirst

BAddLast

CAdd

DInsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using AddFirst adds the element at the start, which is allowed but not the usual chaining approach.

Using Add or Insert causes errors because LinkedList does not have these methods.

We use AddLast to add the new key-value pair at the end of the linked list in the bucket.

2fill in blank

medium

Complete the code to find the bucket index for a given key.

DSA C#

private int GetHash(int key) {
    return key [1] buckets.Length;
}

Drag options to blanks, or click blank then click option'

A/

B*

C%

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using division (/) returns a float or int division result, not suitable for index.

Using multiplication (*) or subtraction (-) does not ensure index within array bounds.

The modulo operator (%) gives the remainder, which is used to find the bucket index within array bounds.

3fill in blank

hard

Fix the error in the code that searches for a key in the linked list bucket.

DSA C#

public string Get(int key) {
    int index = GetHash(key);
    if (buckets[index] != null) {
        foreach (var pair in buckets[index]) {
            if (pair.Key [1] key) {
                return pair.Value;
            }
        }
    }
    return null;
}

Drag options to blanks, or click blank then click option'

A==

B=

C<

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '=' causes a compile error because it's assignment, not comparison.

Using '!=' or '<' will not find the correct key.

We use '==' to check if the keys are equal to find the correct value.

4fill in blank

hard

Fill both blanks to remove a key-value pair from the hash table using chaining.

DSA C#

public bool Remove(int key) {
    int index = GetHash(key);
    if (buckets[index] != null) {
        var node = buckets[index].First;
        while (node != null) {
            if (node.Value.Key [1] key) {
                buckets[index].[2](node);
                return true;
            }
            node = node.Next;
        }
    }
    return false;
}

Drag options to blanks, or click blank then click option'

A==

B!=

CRemove

DRemoveNode

Attempts:

3 left

💡 Hint

Common Mistakes

Using '!=' in the if condition skips the correct node.

Using RemoveNode causes errors because LinkedList does not have this method; Remove accepts a node.

We check equality with '==' and remove the node using Remove method.

5fill in blank

hard

Fill all three blanks to update the value for an existing key in the hash table using chaining.

DSA C#

public void Update(int key, string newValue) {
    int index = GetHash(key);
    if (buckets[index] != null) {
        foreach (var node in buckets[index]) {
            if (node.Key [1] key) {
                var pair = new KeyValuePair<int, string>(node.Key, [2]);
                buckets[index].[3](pair);
                return;
            }
        }
    }
}

Drag options to blanks, or click blank then click option'

A==

BnewValue

CRemove

DAddLast

Attempts:

3 left

💡 Hint

Common Mistakes

Using '=' instead of '==' in the if condition.

Using old value instead of newValue.

Using Remove instead of AddLast to add the updated pair.

We check equality with '==', create a new pair with newValue, and add it at the end with AddLast.

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