Collision Handling Using Chaining in DSA Typescript - Build from Scratch

Collision Handling Using Chaining

📖 Scenario: Imagine you are building a simple phone book app. You want to store names and phone numbers so you can find a number quickly by name. But sometimes, two names might hash to the same spot in your storage. To handle this, you will use chaining: each spot holds a list of entries that share the same hash.

🎯 Goal: You will create a hash table using chaining to store and retrieve phone numbers by name. You will add entries, handle collisions by chaining, and then print the stored phone book.

📋 What You'll Learn

Create a hash table with chaining using an array of lists

Add entries with names and phone numbers

Handle collisions by adding entries to the list at the hashed index

Print the full phone book showing all chains

💡 Why This Matters

🌍 Real World

Hash tables with chaining are used in many software systems to store and quickly find data even when keys collide.

💼 Career

Understanding collision handling is important for software engineers working on databases, caches, and any system requiring fast data lookup.

1

Create the hash table array

Create a variable called hashTable that is an array with 5 empty arrays inside it to hold chained entries.

DSA Typescript

const hashTable: [string, string][][] = [[], [], [], [], []];
// Your code here

Hint

Think of hashTable as a shelf with 5 boxes. Each box can hold many name-phone pairs.

2

Create a simple hash function

Create a function called hash that takes a key string and returns a number between 0 and 4 by summing the character codes of key and taking modulo 5.

DSA Typescript

const hashTable: [string, string][][] = [[], [], [], [], []];

function hash(key: string): number {
  // Your code here
}

Hint

This function turns a name into a number from 0 to 4 to find the right box on the shelf.

3

Add entries to the hash table with chaining

Create a function called addEntry that takes name and phone strings, computes the index using hash(name), and pushes the pair [name, phone] into the array at hashTable[index].

DSA Typescript

const hashTable: [string, string][][] = [[], [], [], [], []];

function hash(key: string): number {
  let sum = 0;
  for (let i = 0; i < key.length; i++) {
    sum += key.charCodeAt(i);
  }
  return sum % 5;
}

function addEntry(name: string, phone: string): void {
  // Your code here
}

Hint

This function puts the name and phone number into the right box on the shelf, adding to the list if there are others.

4

Print the full phone book with chains

Use a for loop with variable i from 0 to 4 to print each index and its chained entries in hashTable. Format each line as Index i: name1 -> phone1, name2 -> phone2 or Index i: empty if no entries.

DSA Typescript

const hashTable: [string, string][][] = [[], [], [], [], []];

function hash(key: string): number {
  let sum = 0;
  for (let i = 0; i < key.length; i++) {
    sum += key.charCodeAt(i);
  }
  return sum % 5;
}

function addEntry(name: string, phone: string): void {
  const index = hash(name);
  hashTable[index].push([name, phone]);
}

addEntry("Alice", "1234");
addEntry("Bob", "5678");
addEntry("Charlie", "9101");
addEntry("David", "1121");
addEntry("Eve", "3141");

// Your code here

Hint

Print each box number and the list of names and phones chained there. Show 'empty' if no entries.

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