Collision Handling Using Chaining in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is collision handling in hashing?

Collision handling is a method to resolve the problem when two keys hash to the same index in a hash table.

beginner

Explain chaining as a collision handling technique.

Chaining stores all elements that hash to the same index in a linked list or chain at that index, allowing multiple elements to share one slot.

beginner

What data structure is commonly used in chaining to handle collisions?

A linked list is commonly used to store multiple elements at the same hash index in chaining.

intermediate

How does chaining affect the search operation in a hash table?

Search involves hashing to find the index, then traversing the linked list at that index to find the element, which may take longer if many collisions occur.

intermediate

What is the average time complexity of search in a hash table using chaining?

The average time complexity is O(1 + α), where α is the load factor (number of elements divided by number of buckets).

What happens when two keys hash to the same index in chaining?

A Both keys are stored in a linked list at that index

B The second key replaces the first key

C The hash table resizes immediately

D The keys are stored in separate arrays

In chaining, all keys that hash to the same index are stored in a linked list at that index.

Which data structure is NOT typically used in chaining?

A Linked list

B Array

C Binary tree

D Hash table

Chaining uses linked lists or sometimes trees, but not another hash table inside each bucket.

What is the main advantage of chaining over open addressing?

A Handles collisions without probing

B Uses less memory

C Always faster search

D No need for hash function

Chaining handles collisions by storing multiple elements in a list, avoiding probing for empty slots.

If the load factor increases, what happens to the average search time in chaining?

A It decreases

B It stays the same

C It increases

D It becomes zero

Higher load factor means longer chains, so average search time increases.

In chaining, what is stored at each index of the hash table?

A A single element

B A linked list of elements

C A sorted array

D A binary search tree

Each index stores a linked list of elements that hash to that index.

Describe how chaining handles collisions in a hash table.

Think about storing multiple items in one bucket.

Explain the impact of load factor on the performance of chaining.

Consider how crowded the buckets get.

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