Collision Handling Using Chaining in DSA Typescript - Execution Trace

Concept Flow - Collision Handling Using Chaining

Insert key

↓

Compute hash index

↓

Check bucket at index

↓

Bucket empty?

Yes→Create new linked list with key

↓

Insert key

↓

Bucket not empty?

No→Traverse linked list

↓

Insert key at list end

↓

Done

When inserting a key, compute its hash index. If the bucket is empty, create a new linked list and insert the key. If not, add the key at the end of the linked list to handle collisions.

Execution Sample

DSA Typescript

hashTable = Array(3)
insert(5)
insert(8)
insert(11)

Insert keys 5, 8, and 11 into a hash table of size 3 using chaining to handle collisions.

Execution Table

Step	Operation	Bucket Index	Bucket State Before	Pointer Changes	Bucket State After	Visual State
1	Insert 5	5 % 3 = 2	[]	Create new node with 5	[5]	[[], [], 5 -> null]
2	Insert 8	8 % 3 = 2	[5]	Add node with 8 at end	[5 -> 8]	[[], [], 5 -> 8 -> null]
3	Insert 11	11 % 3 = 2	[5 -> 8]	Add node with 11 at end	[5 -> 8 -> 11]	[[], [], 5 -> 8 -> 11 -> null]
4	End	-	[[], [], 5 -> 8 -> 11]	-	-	Insertion complete

💡 All keys inserted; chaining handled collisions at bucket index 2.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
hashTable	[[], [], []]	[[], [], [5]]	[[], [], [5 -> 8]]	[[], [], [5 -> 8 -> 11]]	[[], [], [5 -> 8 -> 11]]
bucketIndex	-	2	2	2	-
currentBucket	-	[]	[5]	[5 -> 8]	[5 -> 8 -> 11]

Key Moments - 3 Insights

Why do all keys 5, 8, and 11 go to the same bucket?

Because the hash function uses modulo 3, and 5 % 3 = 2, 8 % 3 = 2, 11 % 3 = 2, so all keys map to bucket index 2 as shown in execution_table rows 1-3.

How does chaining prevent data loss when multiple keys collide?

Chaining stores collided keys in a linked list at the same bucket. The execution_table shows how nodes are added at the end of the list, preserving all keys.

What happens if the bucket is empty when inserting a key?

A new linked list node is created with the key, as seen in step 1 of execution_table where bucket 2 was empty before inserting 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the bucket state after inserting key 8?

A [5]

B [5 -> 8]

C [8]

D []

💡 Hint

Refer to execution_table row 2 under 'Bucket State After' column.

At which step does the bucket at index 2 first contain more than one key?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Check the 'Bucket State After' column in execution_table for when the list length changes.

If the hash table size changed to 5, where would key 11 be inserted?

A Bucket 3

B Bucket 2

C Bucket 1

D Bucket 4

💡 Hint

Calculate 11 % 5 and check bucket index.

Concept Snapshot

Collision Handling Using Chaining:
- Use a hash function to find bucket index.
- If bucket empty, create linked list node.
- If bucket occupied, add node at list end.
- Handles collisions by storing multiple keys in a list.
- Maintains all keys without overwriting.

Full Transcript

Collision handling using chaining stores multiple keys that hash to the same bucket in a linked list. When inserting a key, the hash function computes the bucket index. If the bucket is empty, a new linked list node is created. If not, the key is added at the end of the linked list. This way, collisions do not cause data loss. The example inserts keys 5, 8, and 11 into a hash table of size 3. All keys map to bucket 2, so they form a linked list there. The execution table shows each insertion step, bucket states, and pointer changes. Variable tracking shows how the hash table and bucket contents evolve. Key moments clarify why keys collide and how chaining preserves them. The visual quiz tests understanding of bucket states and hash calculations.

Practice

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

easy

A. Store all elements that hash to the same index in a linked list at that index

B. Replace the existing element with the new one when a collision occurs

C. Use a secondary hash function to find a new index

D. Resize the hash table immediately when a collision happens

Solution

1. Step 1: Understand collision in hash tables

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

2. Step 2: How chaining handles collisions

   Chaining stores all collided elements in a linked list at that index, allowing multiple elements per slot.

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 replaces old elements
• Confusing chaining with open addressing
• Assuming chaining resizes table on collision

2. Which of the following TypeScript code snippets correctly initializes a hash table with chaining?

easy

A. const table: Array = new Array(10).fill([]);

B. const table: Array<number> = Array(10).map(() => []);

C. const table: Array<number> = new Array(10).fill(0);

D. const table: Array = Array.from({ length: 10 }, () => []);

Solution

1. Step 1: Understand how to initialize array of arrays in TypeScript

   Using Array.from with a function creates separate arrays for each slot.

2. Step 2: Analyze each option

   const table: Array = new Array(10).fill([]); uses fill([]) which fills all slots with the same array reference (wrong). const table: Array = Array.from({ length: 10 }, () => []); correctly creates separate empty arrays. const table: Array<number> = new Array(10).fill(0); is a number array, not array of arrays. const table: Array<number> = Array(10).map(() => []); uses map on uninitialized array, which won't work.

3. Final Answer:

   const table: Array = Array.from({ length: 10 }, () => []); -> Option D

4. Quick Check:

   Use Array.from with function for separate arrays [OK]

Hint: Use Array.from with () => [] for separate chains [OK]

Common Mistakes:

• Using fill([]) causes all slots to share one array
• Using map on uninitialized array returns empty
• Initializing as number array instead of array of arrays

3. Consider the following TypeScript code using chaining for collision handling:

class HashTable {
  table: Array;
  size: number;

  constructor(size: number) {
    this.size = size;
    this.table = Array.from({ length: size }, () => []);
  }

  hash(key: number): number {
    return key % this.size;
  }

  insert(key: number) {
    const index = this.hash(key);
    this.table[index].push(key);
  }
}

const ht = new HashTable(5);
ht.insert(1);
ht.insert(6);
ht.insert(11);
ht.insert(3);
console.log(ht.table);

What will be printed to the console?

medium

A. [[1, 6, 11], [ ], [3], [ ], [ ]]

B. [[ ], [1, 6, 11], [ ], [3], [ ]]

C. [[ ], [1], [6], [11, 3], [ ]]

D. [[ ], [1, 6], [11], [3], [ ]]

Solution

1. Step 1: Calculate hash index for each inserted key

   Using hash = key % 5:
   1 % 5 = 1
   6 % 5 = 1
   11 % 5 = 1
   3 % 5 = 3

2. Step 2: Insert keys into chains at calculated indices

   Index 1 chain: [1, 6, 11]
   Index 3 chain: [3]
   Other indices remain empty arrays.

3. Final Answer:

   [[], [1, 6, 11], [], [3], []] -> Option B

4. Quick Check:

   Keys grouped by modulo 5 index [OK]

Hint: Use modulo to find index, then add to that chain [OK]

Common Mistakes:

• Miscomputing modulo results
• Inserting keys into wrong index
• Confusing array positions in output

4. The following TypeScript code attempts to insert keys into a hash table using chaining, but it has a bug:

class HashTable {
  table: Array;
  size: number;

  constructor(size: number) {
    this.size = size;
    this.table = new Array(size).fill([]);
  }

  hash(key: number): number {
    return key % this.size;
  }

  insert(key: number) {
    const index = this.hash(key);
    this.table[index].push(key);
  }
}

const ht = new HashTable(3);
ht.insert(1);
ht.insert(4);
console.log(ht.table);

What is the bug and how to fix it?

medium

A. Bug: All slots share the same array due to fill([]). Fix: Use Array.from with () => []

B. Bug: hash function is incorrect. Fix: Use key % (size - 1)

C. Bug: insert method overwrites array. Fix: Use concat instead of push

D. Bug: size is not initialized. Fix: Initialize size before table

Solution

1. Step 1: Identify problem with fill([])

   Using fill([]) assigns the same array reference to all slots, so pushing to one affects all.

2. Step 2: Correct initialization method

   Use Array.from({ length: size }, () => []) to create separate arrays for each slot.

3. Final Answer:

   Bug: All slots share the same array due to fill([]). Fix: Use Array.from with () => [] -> Option A

4. Quick Check:

   fill([]) shares references; Array.from creates unique arrays [OK]

Hint: Avoid fill([]); use Array.from with function for unique arrays [OK]

Common Mistakes:

• Thinking hash function is wrong
• Trying to fix by changing push to concat
• Ignoring array reference sharing issue

5. You have a hash table of size 4 using chaining. You insert keys 2, 6, 10, 14, and 18. Then you want to remove key 10. Which of the following shows the correct state of the hash table chains after removal?

Hash function: key % 4

hard

A. [[2, 6, 14, 18], [ ], [ ], [ ]] with 10 removed

B. [[2, 6, 14, 18], [ ], [ ], [ ]]

C. [[ ], [ ], [2, 6, 14, 18], [ ]] with 10 removed

D. [[6, 14, 18], [ ], [2], [ ]]

Solution

1. Step 1: Calculate hash indices for all keys

   2 % 4 = 2
   6 % 4 = 2
   10 % 4 = 2
   14 % 4 = 2
   18 % 4 = 2
   All keys hash to index 2.

2. Step 2: Insert keys into chain at index 2 and remove 10

   Initial chain at index 2: [2, 6, 10, 14, 18]
   After removing 10: [2, 6, 14, 18]

3. Step 3: Represent hash table chains

   Index 2 chain: [2, 6, 14, 18]
   Other indices: empty arrays

4. Step 4: Correct representation

   [[ ], [ ], [2, 6, 14, 18], [ ]] with 10 removed from index 2 chain.

5. Final Answer:

   [[ ], [ ], [2, 6, 14, 18], [ ]] with 10 removed -> Option C

6. Quick Check:

   All keys at index 2; 10 removed from chain [OK]

Hint: All keys mod 4 go to index 2; remove 10 from that chain [OK]

Common Mistakes:

• Placing keys in wrong indices
• Forgetting to remove key 10
• Misreading hash function modulo