Collision Handling Using Chaining in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after inserting keys with collisions?

Consider a hash table using chaining with a simple hash function:
hash(key) = key % 3.
We insert keys 3, 6, 9, and 4 in that order.
What is the state of the hash table's buckets after these insertions?

DSA Javascript

class HashTable {
  constructor() {
    this.buckets = [[], [], []];
  }
  hash(key) {
    return key % 3;
  }
  insert(key) {
    const index = this.hash(key);
    this.buckets[index].push(key);
  }
}
const ht = new HashTable();
ht.insert(3);
ht.insert(6);
ht.insert(9);
ht.insert(4);
console.log(ht.buckets);

A [[3, 6], [9, 4], []]

B [[3], [4], [6, 9]]

C [[3, 6, 9], [4], []]

D [[], [4], [3, 6, 9]]

💡 Hint

Remember the hash function divides the key by 3 and uses the remainder as the bucket index.

Keys 3, 6, and 9 all have remainder 0 when divided by 3, so they go into bucket 0. Key 4 has remainder 1, so it goes into bucket 1. Bucket 2 remains empty.

🧠 Conceptual

intermediate

Why is chaining used in collision handling?

In hash tables, collisions happen when multiple keys map to the same bucket. Why do we use chaining to handle collisions?

A Chaining stores collided keys in a linked list at the bucket, allowing multiple keys per bucket.

B Chaining replaces the old key with the new key to avoid duplicates.

C Chaining sorts all keys in the hash table to prevent collisions.

D Chaining uses open addressing to find another empty bucket for the collided key.

💡 Hint

Think about how multiple items can be stored in the same bucket without losing data.

Chaining keeps all keys that hash to the same bucket in a list (like a linked list), so collisions don't overwrite data.

🔧 Debug

advanced

Find the bug in this chaining insertion code

This code tries to insert keys into a hash table using chaining. It should add keys to the correct bucket. What is the bug?

DSA Javascript

class HashTable {
  constructor(size) {
    this.buckets = new Array(size).fill([]);
  }
  hash(key) {
    return key % this.buckets.length;
  }
  insert(key) {
    const index = this.hash(key);
    this.buckets[index].push(key);
  }
}
const ht = new HashTable(3);
ht.insert(1);
ht.insert(4);
console.log(ht.buckets);

A All buckets share the same array because fill([]) uses the same reference, causing all keys to appear in every bucket.

B The hash function is incorrect and causes keys to be inserted in wrong buckets.

C The insert method overwrites the bucket instead of pushing keys.

D The constructor does not initialize buckets as arrays.

💡 Hint

Check how the buckets array is initialized and if each bucket is independent.

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

❓ Predict Output

advanced

What is the output after deleting a key in chaining?

Given a hash table with chaining, after inserting keys 2, 5, 8 and then deleting key 5, what is the state of the buckets?

DSA Javascript

class HashTable {
  constructor() {
    this.buckets = [[], [], []];
  }
  hash(key) {
    return key % 3;
  }
  insert(key) {
    const index = this.hash(key);
    this.buckets[index].push(key);
  }
  delete(key) {
    const index = this.hash(key);
    this.buckets[index] = this.buckets[index].filter(k => k !== key);
  }
}
const ht = new HashTable();
ht.insert(2);
ht.insert(5);
ht.insert(8);
ht.delete(5);
console.log(ht.buckets);

A [[2], [], [8]]

B [[], [2, 8], []]

C [[2, 8], [], []]

D [[], [], [2, 8]]

💡 Hint

Check the hash values of keys 2, 5, and 8 and which buckets they belong to.

2 % 3 = 2, 5 % 3 = 2, 8 % 3 = 2, so all keys go to bucket 2. After deleting 5, bucket 2 has [2,8]. Buckets 0 and 1 are empty.

🧠 Conceptual

expert

What is the average time complexity of search in chaining with a good hash function?

Assuming a hash table uses chaining and a good hash function that distributes keys evenly, what is the average time complexity to search for a key?

A O(n) - Linear time because all keys could be in one chain.

B O(1) - Constant time because keys are evenly distributed and chains are short on average.

C O(log n) - Logarithmic time because chains are sorted.

D O(n^2) - Quadratic time due to nested loops in chaining.

💡 Hint

Think about how chaining works when keys are spread evenly across buckets.

With a good hash function, each bucket has few keys, so searching a chain is fast and average time is constant.

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