Collision Handling Using Chaining in DSA Javascript - Execution Trace

Concept Flow - Collision Handling Using Chaining

Compute hash index

↓

Check bucket at index

↓

Empty

↓

Insert

↓

Add new node at end

↓

Done

This flow shows how a key is hashed to an index, then inserted into a linked list at that index if a collision occurs.

Execution Sample

DSA Javascript

class HashTable {
  constructor(size) {
    this.buckets = Array(size).fill(null);
  }
  insert(key, value) {
    const index = this.hash(key);
    if (!this.buckets[index]) {
      this.buckets[index] = { key, value, next: null };
    } else {
      let current = this.buckets[index];
      while (current.next) current = current.next;
      current.next = { key, value, next: null };
    }
  }
  hash(key) {
    return key.length % this.buckets.length;
  }
}

This code inserts key-value pairs into a hash table using chaining to handle collisions.

Execution Table

Step	Operation	Index	Bucket State Before	Pointer Changes	Bucket State After	Visual State
1	Insert ('cat', 1)	3	[null, null, null, null, null]	buckets[3] = new node	[null, null, null, {cat:1, next:null}, null]	[null, null, null, cat(1) -> null, null]
2	Insert ('dog', 2)	3	[null, null, null, cat(1) -> null, null]	Traverse to end, add new node	[null, null, null, cat(1) -> dog(2) -> null, null]	[null, null, null, cat(1) -> dog(2) -> null, null]
3	Insert ('bird', 3)	4	[null, null, null, cat(1) -> dog(2) -> null, null]	buckets[4] = new node	[null, null, null, cat(1) -> dog(2) -> null, {bird:3, next:null}]	[null, null, null, cat(1) -> dog(2) -> null, bird(3) -> null]
4	Insert ('cow', 4)	3	[null, null, null, cat(1) -> dog(2) -> null, bird(3) -> null]	Traverse to end, add new node	[null, null, null, cat(1) -> dog(2) -> cow(4) -> null, bird(3) -> null]	[null, null, null, cat(1) -> dog(2) -> cow(4) -> null, bird(3) -> null]
5	Insert ('fish', 5)	4	[null, null, null, cat(1) -> dog(2) -> cow(4) -> null, bird(3) -> null]	Traverse to end, add new node	[null, null, null, cat(1) -> dog(2) -> cow(4) -> null, bird(3) -> fish(5) -> null]	[null, null, null, cat(1) -> dog(2) -> cow(4) -> null, bird(3) -> fish(5) -> null]
6	Stop	-	-	-	-	All keys inserted, chaining handled collisions

💡 All keys inserted; chaining linked lists store collided keys at same index.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	Final
buckets	[null, null, null, null, null]	[null, null, null, cat(1) -> null, null]	[null, null, null, cat(1) -> dog(2) -> null, null]	[null, null, null, cat(1) -> dog(2) -> null, bird(3) -> null]	[null, null, null, cat(1) -> dog(2) -> cow(4) -> null, bird(3) -> null]	[null, null, null, cat(1) -> dog(2) -> cow(4) -> null, bird(3) -> fish(5) -> null]	[null, null, null, cat(1) -> dog(2) -> cow(4) -> null, bird(3) -> fish(5) -> null]
index	-	3	3	4	3	4	-
current	-	cat(1)	dog(2)	bird(3)	cow(4)	fish(5)	-

Key Moments - 3 Insights

Why do we traverse the linked list before adding a new node?

Because the bucket already has nodes, we must find the end of the linked list to add the new node without overwriting existing data. See execution_table steps 2, 4, and 5.

What happens if the bucket is empty when inserting?

We directly insert the new node at that bucket index without traversal. This is shown in execution_table steps 1 and 3.

How does chaining help with collisions?

Chaining stores multiple key-value pairs in a linked list at the same bucket index, so collisions do not overwrite data but link nodes. See visual states in execution_table steps 2 and 4.

Visual Quiz - 3 Questions

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

A [null, null, null, cat(1) -> dog(2) -> null, null]

B [null, null, null, dog(2) -> cat(1) -> null, null]

C [null, null, null, cat(1) -> null, null]

D [null, null, null, null, null]

💡 Hint

Check the 'Bucket State After' column in row for step 2.

At which step does the bucket at index 4 first get a node?

A Step 1

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Index' and 'Bucket State After' columns for step 3.

If we insert a key with length 3, which index will it hash to given bucket size 5?

A Index 2

B Index 3

C Index 0

D Index 1

💡 Hint

Hash function is key.length % buckets.length; 3 % 5 = 3, but check carefully the code sample.

Concept Snapshot

Collision Handling Using Chaining:
- Use a linked list at each bucket to store multiple keys.
- Hash key to index.
- If bucket empty, insert node.
- If not, traverse list and append node.
- Handles collisions by chaining nodes in list.

Full Transcript

Collision handling using chaining means when two keys hash to the same index, we store them in a linked list at that index. We first compute the hash index from the key. If the bucket at that index is empty, we insert the new node directly. If not, we traverse the linked list at that bucket to find the end and add the new node there. This way, multiple keys can share the same bucket without overwriting each other. The execution table shows inserting keys 'cat', 'dog', 'bird', 'cow', and 'fish' into a hash table with 5 buckets. Keys 'cat', 'dog', and 'cow' collide at index 3 and form a linked list. Keys 'bird' and 'fish' collide at index 4 and form another linked list. This chaining method keeps all keys accessible even when collisions happen.

Practice

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

easy

A. Resize the hash table immediately after every insertion

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

C. Store multiple elements in a linked list at the same index when collisions occur

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

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.

3. Final Answer:

   Store multiple elements in a linked list at the same index when collisions occur -> Option C

4. Quick Check:

   Chaining = linked list at index [OK]

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

Common Mistakes:

• Thinking chaining replaces old values
• Confusing chaining with open addressing
• Assuming resizing happens on every collision

2. Which of the following is the correct way to initialize a hash table with chaining in JavaScript?

easy

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

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

C. const table = new Array(10);

D. const table = Array(10).fill(null);

Solution

1. Step 1: Understand array initialization with unique lists

   Using fill([]) fills all indexes with the same array reference.

2. Step 2: Use Array.from with a function to create unique arrays

   Array.from({ length: 10 }, () => []) creates a new empty array at each index.

3. Final Answer:

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

4. Quick Check:

   Unique arrays per index = const table = Array.from({ length: 10 }, () => []); [OK]

Hint: Use Array.from with function for unique arrays [OK]

Common Mistakes:

• Using fill([]) causes all indexes to share one array
• new Array(10) leaves slots undefined
• Filling with null does not create lists for chaining

3. Consider the following JavaScript code for inserting keys into a hash table with chaining:

const table = Array.from({ length: 5 }, () => []);
function hash(key) { return key % 5; }

// Insert keys
[7, 12, 17].forEach(key => {
  const index = hash(key);
  table[index].push(key);
});

console.log(table);

What is the output printed?

medium

A. [[7, 12, 17], [], [], [], []]

B. [[], [], [], [7, 12, 17], []]

C. [[], [7], [12], [17], []]

D. [[], [], [7, 12, 17], [], []]

Solution

1. Step 1: Calculate hash index for each key

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2.

2. Step 2: Insert keys at index 2

   All keys go into table[2], so table[2] = [7, 12, 17].

3. Final Answer:

   [[], [], [7, 12, 17], [], []] -> Option D

4. Quick Check:

   All keys at index 2 = [[], [], [7, 12, 17], [], []] [OK]

Hint: Calculate key % size to find index [OK]

Common Mistakes:

• Miscomputing modulo results
• Inserting keys at wrong indexes
• Confusing array positions in output

4. The following code attempts to insert keys into a hash table with chaining but has a bug:

const table = new Array(3).fill([]);
function hash(key) { return key % 3; }

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

insert(1);
insert(4);
insert(7);
console.log(table);

What is the bug and how to fix it?

medium

A. Bug: All indexes share the same array; Fix: Use Array.from with () => []

B. Bug: hash function is incorrect; Fix: Use key % 10 instead

C. Bug: push method is wrong; Fix: Use unshift instead

D. Bug: table size is too small; Fix: Increase size to 10

Solution

1. Step 1: Identify the bug with fill([])

   Using fill([]) assigns the same array reference to all indexes.

2. Step 2: Fix by creating unique arrays per index

   Use Array.from({ length: 3 }, () => []) to create separate arrays.

3. Final Answer:

   Bug: All indexes share the same array; Fix: Use Array.from with () => [] -> Option A

4. Quick Check:

   fill([]) shares arrays, Array.from creates unique ones [OK]

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

Common Mistakes:

• Changing hash function unnecessarily
• Using wrong array methods
• Ignoring shared reference problem

5. You have a hash table of size 4 using chaining. You insert keys [3, 7, 11, 15, 19]. The hash function is key % 4. After all insertions, which index has the longest chain and what is its content?

medium

A. Index 3: [3, 7, 11, 15, 19]

B. Index 1: [3, 7, 11, 15, 19]

C. Index 3: [3, 7, 11, 15]

D. Index 3: [3, 7, 11]

Solution

1. Step 1: Compute hash index for each key

   3 % 4 = 3, 7 % 4 = 3, 11 % 4 = 3, 15 % 4 = 3, 19 % 4 = 3.

2. Step 2: Insert all keys at index 3

   All keys go into table[3], so chain is [3, 7, 11, 15, 19].

3. Final Answer:

   Index 3: [3, 7, 11, 15, 19] -> Option A

4. Quick Check:

   All keys mod 4 = 3, chain length 5 [OK]

Hint: All keys mod 4 equal 3, so chain at index 3 [OK]

Common Mistakes:

• Miscomputing modulo for some keys
• Assuming keys spread across indexes
• Forgetting all keys collide at same index