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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting keys with collisions in a chained hash table

Consider a hash table of size 3 using chaining for collision handling. The hash function is key % 3. Insert keys 2, 5, 8 in this order. What is the state of the hash table after these insertions?

DSA Typescript

class Node {
  constructor(public key: number, public next: Node | null = null) {}
}

class HashTable {
  table: Array<Node | null> = [null, null, null];

  hash(key: number): number {
    return key % 3;
  }

  insert(key: number): void {
    const index = this.hash(key);
    const newNode = new Node(key);
    if (!this.table[index]) {
      this.table[index] = newNode;
    } else {
      newNode.next = this.table[index];
      this.table[index] = newNode;
    }
  }

  print(): string {
    return this.table.map((head, i) => {
      let result = `${i}: `;
      let current = head;
      while (current) {
        result += `${current.key} -> `;
        current = current.next;
      }
      return result + 'null';
    }).join(' | ');
  }
}

const ht = new HashTable();
ht.insert(2);
ht.insert(5);
ht.insert(8);
console.log(ht.print());

A 0: null | 1: 2 -> 5 -> 8 -> null | 2: null

B 0: null | 1: null | 2: 8 -> 5 -> 2 -> null

C 0: 8 -> 5 -> 2 -> null | 1: null | 2: null

D 0: 2 -> 5 -> 8 -> null | 1: null | 2: null

💡 Hint

Remember the hash function key % 3 and that new nodes are inserted at the head of the chain.

The hash function key % 3 maps keys 2, 5, and 8 to index 2. Each new key is inserted at the head of the linked list at index 2, so the order is 8 -> 5 -> 2 -> null.

🧠 Conceptual

intermediate

Understanding the effect of chaining on hash table search time

In a hash table using chaining, if the load factor (number of keys / table size) increases significantly, what happens to the average search time for a key?

A Average search time becomes zero because all keys are found instantly.

B Average search time remains constant regardless of load factor.

C Average search time increases because chains become longer.

D Average search time decreases because chains become shorter.

💡 Hint

Think about how many elements are in each chain as more keys are added.

As the load factor increases, more keys hash to the same index, making chains longer. Searching requires traversing these chains, increasing average search time.

🔧 Debug

advanced

Identify the bug in chaining insertion code

The following TypeScript code attempts to insert keys into a hash table using chaining. It compiles but does not insert keys correctly. What is the bug?

DSA Typescript

class Node {
  constructor(public key: number, public next: Node | null = null) {}
}

class HashTable {
  table: Array<Node | null> = [null, null, null];

  hash(key: number): number {
    return key % 3;
  }

  insert(key: number): void {
    const index = this.hash(key);
    const newNode = new Node(key);
    if (this.table[index]) {
      this.table[index] = newNode;
    } else {
      newNode.next = this.table[index];
      this.table[index] = newNode;
    }
  }
}

A The hash function should use key % 2 instead of key % 3.

B The table array should be initialized with empty arrays instead of null.

C The Node class should not have a next property.

D The condition in insert should be reversed; currently it overwrites existing chains.

💡 Hint

Check what happens when the bucket already has nodes.

The insert method overwrites the existing chain when the bucket is not empty, losing all previous nodes. The condition should insert new nodes at the head when the bucket is not empty.

📝 Syntax

advanced

Identify the syntax error in chaining insertion code

Which option contains a syntax error in the chaining insertion method?

DSA Typescript

insert(key: number): void {
  const index = this.hash(key);
  const newNode = new Node(key);
  if (!this.table[index]) {
    this.table[index] = newNode;
  } else {
    newNode.next = this.table[index];
    this.table[index] = newNode;
  }
}

A

insert(key: number): void {
  const index = this.hash(key);
  const newNode = new Node(key);
  if !this.table[index] {
    this.table[index] = newNode;
  } else {
    newNode.next = this.table[index];
    this.table[index] = newNode;
  }
}

B

insert(key: number) {
  const index = this.hash(key)
  const newNode = new Node(key)
  if (!this.table[index]) {
    this.table[index] = newNode
  } else {
    newNode.next = this.table[index]
    this.table[index] = newNode
  }
}

C

insert(key: number): void {
  const index = this.hash(key);
  const newNode = new Node(key);
  if (!this.table[index]) {
    this.table[index] = newNode;
  } else {
    newNode.next = this.table[index];
    this.table[index] = newNode;
  }
}

D

}
}  
;edoNwen = ]xedni[elbat.siht    
;]xedni[elbat.siht = txen.edoNwen    
{ esle }  
;edoNwen = ]xedni[elbat.siht    
{ )]xedni[elbat.siht!( fi  
;)yek(edoN wen = edoNwen tsnoc  
;)yek(hsah.siht = xedni tsnoc  
{ diov :)rebmun :yek(tresni

💡 Hint

Check the syntax of the if statement.

Option A is missing parentheses around the if condition, causing a syntax error.

🚀 Application

expert

Resulting chain after multiple insertions and deletions

A hash table of size 4 uses chaining with the hash function key % 4. Insert keys 3, 7, 11, 15 in this order. Then delete key 7. What is the chain at index 3 after these operations?

DSA Typescript

class Node {
  constructor(public key: number, public next: Node | null = null) {}
}

class HashTable {
  table: Array<Node | null> = [null, null, null, null];

  hash(key: number): number {
    return key % 4;
  }

  insert(key: number): void {
    const index = this.hash(key);
    const newNode = new Node(key);
    newNode.next = this.table[index];
    this.table[index] = newNode;
  }

  delete(key: number): void {
    const index = this.hash(key);
    let current = this.table[index];
    let prev: Node | null = null;
    while (current) {
      if (current.key === key) {
        if (prev) {
          prev.next = current.next;
        } else {
          this.table[index] = current.next;
        }
        return;
      }
      prev = current;
      current = current.next;
    }
  }

  printChain(index: number): string {
    let current = this.table[index];
    let result = '';
    while (current) {
      result += `${current.key} -> `;
      current = current.next;
    }
    return result + 'null';
  }
}

const ht = new HashTable();
ht.insert(3);
ht.insert(7);
ht.insert(11);
ht.insert(15);
ht.delete(7);
console.log(ht.printChain(3));

A 15 -> 11 -> 3 -> null

B 3 -> 11 -> 15 -> null

C 11 -> 15 -> 3 -> null

D 15 -> 7 -> 11 -> 3 -> null

💡 Hint

Remember insertions add nodes at the head and deletion removes the matching key.

All keys hash to index 3 (3 % 4 = 3, 7 % 4 = 3, 11 % 4 = 3, 15 % 4 = 3). Insertions add at head, so chain before deletion is 15 -> 11 -> 7 -> 3 -> null. Deleting 7 removes it from the chain, resulting in 15 -> 11 -> 3 -> null.

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