Collision Handling Using Chaining in DSA Typescript - Time & Space Complexity

Time Complexity: Collision Handling Using Chaining

O(1 + n/k)

Understanding Time Complexity

When we use chaining to handle collisions in a hash table, we want to know how fast operations like search, insert, and delete run.

We ask: How does the time to do these operations grow as the number of items increases?

Scenario Under Consideration

Analyze the time complexity of the insert operation using chaining.

function insert(hashTable: Array>, key: number): void {
  const index = key % hashTable.length;
  hashTable[index].push(key);
}
    

This code adds a key to the hash table by placing it in a linked list (chain) at the computed index.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding an element to the chain (linked list) at the computed index.
• How many times: Insert itself is constant time, but searching or deleting requires traversing the chain, which depends on chain length.

How Execution Grows With Input

As more keys are added, chains get longer if the table size stays the same.

Input Size (n)	Approx. Operations (search/insert)
10	About 1 operation per chain (short chains)
100	About 10 operations per chain (longer chains)
1000	About 100 operations per chain (much longer chains)

Pattern observation: The time grows roughly proportional to the number of items per chain, which depends on how full the table is.

Final Time Complexity

Time Complexity: O(1 + n/k) where n is number of keys and k is table size

This means operations are fast if chains stay short, but slow down if many keys share the same index.

Common Mistake

[X] Wrong: "Insert and search always take constant time in chaining."

[OK] Correct: If many keys collide, chains grow longer, making search and delete slower than constant time.

Interview Connect

Understanding how chaining affects time helps you explain hash table performance clearly and shows you know how to handle collisions well.

Self-Check

What if we resized the hash table dynamically to keep chains short? How would the time complexity change?

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