Collision Handling Using Chaining in DSA Typescript

Mental Model

When two keys want to go to the same spot in a table, we keep a list there to hold both.

Analogy: Imagine a mailbox with many slots. If two letters come for the same slot, you put them in a small basket inside that slot instead of throwing one away.

Hash Table:
[0] -> null
[1] -> 15 -> 25 -> null
[2] -> 7 -> null
[3] -> null
[4] -> 12 -> null

Dry Run Walkthrough

Input: Insert keys 15, 25, 7, 12 into a hash table of size 5 using chaining

Goal: Show how collisions are handled by adding nodes to linked lists at the same index

Step 1: Insert 15 at index 15 % 5 = 0

[0] -> 15 -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: 15 goes to index 0 because 15 mod 5 is 0

Step 2: Insert 25 at index 25 % 5 = 0, collision with 15

[0] -> 15 -> 25 -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: 25 also maps to index 0, so we add it after 15 in the list

Step 3: Insert 7 at index 7 % 5 = 2

[0] -> 15 -> 25 -> null
[1] -> null
[2] -> 7 -> null
[3] -> null
[4] -> null

Why: 7 maps to index 2, no collision, so just add it there

Step 4: Insert 12 at index 12 % 5 = 2, collision with 7

[0] -> 15 -> 25 -> null
[1] -> null
[2] -> 7 -> 12 -> null
[3] -> null
[4] -> null

Why: 12 also maps to index 2, so we add it after 7 in the list

Result:

[0] -> 15 -> 25 -> null
[1] -> null
[2] -> 7 -> 12 -> null
[3] -> null
[4] -> null

Annotated Code

DSA Typescript

class Node {
  key: number;
  next: Node | null;
  constructor(key: number) {
    this.key = key;
    this.next = null;
  }
}

class HashTable {
  size: number;
  table: Array<Node | null>;

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

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

  insert(key: number): void {
    const index = this.hash(key);
    const newNode = new Node(key);
    if (this.table[index] === null) {
      this.table[index] = newNode; // place new node if empty
    } else {
      let curr = this.table[index];
      while (curr!.next !== null) {
        curr = curr!.next; // move to end of chain
      }
      curr!.next = newNode; // add new node at end
    }
  }

  print(): void {
    for (let i = 0; i < this.size; i++) {
      let curr = this.table[i];
      let chain = '';
      while (curr !== null) {
        chain += curr.key + ' -> ';
        curr = curr.next;
      }
      chain += 'null';
      console.log(`[${i}] -> ${chain}`);
    }
  }
}

// Driver code
const ht = new HashTable(5);
ht.insert(15);
ht.insert(25);
ht.insert(7);
ht.insert(12);
ht.print();

const index = this.hash(key);

compute index using hash function

if (this.table[index] === null) { this.table[index] = newNode; }

insert node directly if no collision

while (curr.next !== null) { curr = curr.next; }

traverse to end of chain to handle collision

curr.next = newNode;

append new node at end of chain

Output

[0] -> 15 -> 25 -> null

[1] -> null

[2] -> 7 -> 12 -> null

[3] -> null

[4] -> null

Complexity Analysis

Time: O(n) in worst case because all keys could hash to the same index and form a long chain, but average O(1) if keys distribute well

Space: O(n) because we store all keys in linked lists inside the table

vs Alternative: Compared to open addressing which stores all keys in the table array itself, chaining uses extra linked lists but handles collisions more flexibly

Edge Cases

Inserting into an empty hash table

Node is placed directly at computed index without chaining

DSA Typescript

if (this.table[index] === null) { this.table[index] = newNode; }

Multiple keys hashing to same index

Nodes are linked in a chain at that index

DSA Typescript

while (curr.next !== null) { curr = curr.next; }

Inserting duplicate keys

Duplicates are added as separate nodes in the chain

DSA Typescript

No explicit check for duplicates, so duplicates chain normally

When to Use This Pattern

When you see a hash table problem with collisions, reach for chaining because it stores collided keys in linked lists to keep insertion simple and efficient.

Common Mistakes

Mistake: Overwriting existing node at index instead of chaining
Fix: Traverse to the end of the linked list at that index and append the new node

Mistake: Not handling null pointers when traversing chains
Fix: Always check if next is null before moving forward in the chain

Summary

It stores multiple keys that hash to the same index in a linked list at that index.

Use it when your hash function can cause collisions and you want to keep all keys accessible.

The key insight is to keep a chain (linked list) at each index to hold all collided keys.

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