Collision Handling Using Chaining in DSA C# - Time & Space Complexity

Time Complexity: Collision Handling Using Chaining

O(n/k)

Understanding Time Complexity

When we use chaining to handle collisions in a hash table, we want to know how fast operations like insert or search run.

We ask: How does the time to find or add an item grow as the table gets more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Insert a key into hash table with chaining
void Insert(int key) {
    int index = HashFunction(key);
    Node newNode = new Node(key);
    newNode.Next = table[index];
    table[index] = newNode;
}

// Search for a key in the hash table
bool Search(int key) {
    int index = HashFunction(key);
    Node current = table[index];
    while (current != null) {
        if (current.Key == key) return true;
        current = current.Next;
    }
    return false;
}
    

This code inserts and searches keys in a hash table using linked lists to handle collisions.

Identify Repeating Operations

• Primary operation: Traversing the linked list at a hash index during search.
• How many times: Depends on the number of keys hashed to the same index (length of the chain).

How Execution Grows With Input

As more keys are added, chains get longer if the table size stays the same.

Input Size (n)	Approx. Operations (chain length)
10	1 to 2
100	5 to 10
1000	50 to 100

Pattern observation: The time grows roughly in proportion to how many items share the same index.

Final Time Complexity

Time Complexity: O(n/k) where k is the number of buckets.

This means the time depends on how many items fall into one bucket; if spread evenly, operations stay fast.

Common Mistake

[X] Wrong: "Hash table operations always run in constant time regardless of collisions."

[OK] Correct: If many keys collide into the same bucket, the linked list grows, making search or insert slower.

Interview Connect

Understanding how chaining affects time helps you explain hash table performance clearly and shows you know how to handle collisions well.

Self-Check

"What if we used a balanced tree instead of a linked list for chaining? How would the time complexity change?"

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