Collision Handling Using Chaining in DSA Javascript - Build from Scratch

Collision Handling Using Chaining

📖 Scenario: Imagine you are building a simple phone book app that stores names and phone numbers. To keep things fast, you use a hash table. But sometimes, two names might get the same spot in the table. This is called a collision. To fix this, you will use chaining, which means storing multiple entries in a list at the same spot.

🎯 Goal: You will create a hash table using chaining to handle collisions. You will add entries and then print the table to see how collisions are handled.

📋 What You'll Learn

Create a hash table with a fixed size

Implement a simple hash function

Use chaining (arrays) to handle collisions

Add multiple entries to the hash table

Print the hash table showing chains

💡 Why This Matters

🌍 Real World

Hash tables with chaining are used in many apps to store and quickly find data like usernames, phone numbers, or product info even when collisions happen.

💼 Career

Understanding collision handling is important for software developers working with databases, caching systems, or any data storage that needs fast access.

1

Create the hash table array

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

DSA Javascript

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

Hint

Think of the hash table as 5 buckets, each bucket can hold many items.

2

Create a simple hash function

Create a function called hash that takes a string key and returns the sum of the character codes modulo 5.

DSA Javascript

const hashTable = [[], [], [], [], []];

function hash(key) {
    // Your code here
}

Hint

Loop over each character in the key, add its code to sum, then use modulo 5 to get the index.

3

Add entries using chaining

Write a function called addEntry that takes key and value. Use the hash function to find the index. Then push an object with key and value into the array at that index in hashTable.

DSA Javascript

const hashTable = [[], [], [], [], []];

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

function addEntry(key, value) {
    // Your code here
}

Hint

Use the hash function to find the bucket, then add the key and value as an object to that bucket's array.

4

Add entries and print the hash table

Use addEntry to add these entries: 'Alice' with '123', 'Bob' with '456', 'Charlie' with '789', 'David' with '101', and 'Eve' with '112'. Then print hashTable.

DSA Javascript

const hashTable = [[], [], [], [], []];

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

function addEntry(key, value) {
    const index = hash(key);
    hashTable[index].push({ key: key, value: value });
}

// Your code here

Hint

Call addEntry for each name and number, then print the whole hashTable to see the chains.

Practice

1. What is the main idea behind collision handling using chaining in hash tables?

easy

A. Resize the hash table immediately after every insertion

B. Replace the existing element with the new one when a collision happens

C. Store multiple elements in a linked list at the same index when collisions occur

D. Use a secondary hash function to find a new index

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.

3. Final Answer:

   Store multiple elements in a linked list at the same index when collisions occur -> Option C

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Chaining means linked list at one index for collisions [OK]

Common Mistakes:

• Thinking chaining replaces old values
• Confusing chaining with open addressing
• Assuming resizing happens on every collision

2. Which of the following is the correct way to initialize a hash table with chaining in JavaScript?

easy

A. const table = new Array(10).fill([]);

B. const table = Array.from({ length: 10 }, () => []);

C. const table = new Array(10);

D. const table = Array(10).fill(null);

Solution

1. Step 1: Understand array initialization with unique lists

   Using fill([]) fills all indexes with the same array reference.

2. Step 2: Use Array.from with a function to create unique arrays

   Array.from({ length: 10 }, () => []) creates a new empty array at each index.

3. Final Answer:

   const table = Array.from({ length: 10 }, () => []); -> Option B

4. Quick Check:

   Unique arrays per index = const table = Array.from({ length: 10 }, () => []); [OK]

Hint: Use Array.from with function for unique arrays [OK]

Common Mistakes:

• Using fill([]) causes all indexes to share one array
• new Array(10) leaves slots undefined
• Filling with null does not create lists for chaining

3. Consider the following JavaScript code for inserting keys into a hash table with chaining:

const table = Array.from({ length: 5 }, () => []);
function hash(key) { return key % 5; }

// Insert keys
[7, 12, 17].forEach(key => {
  const index = hash(key);
  table[index].push(key);
});

console.log(table);

What is the output printed?

medium

A. [[7, 12, 17], [], [], [], []]

B. [[], [], [], [7, 12, 17], []]

C. [[], [7], [12], [17], []]

D. [[], [], [7, 12, 17], [], []]

Solution

1. Step 1: Calculate hash index for each key

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2.

2. Step 2: Insert keys at index 2

   All keys go into table[2], so table[2] = [7, 12, 17].

3. Final Answer:

   [[], [], [7, 12, 17], [], []] -> Option D

4. Quick Check:

   All keys at index 2 = [[], [], [7, 12, 17], [], []] [OK]

Hint: Calculate key % size to find index [OK]

Common Mistakes:

• Miscomputing modulo results
• Inserting keys at wrong indexes
• Confusing array positions in output

4. The following code attempts to insert keys into a hash table with chaining but has a bug:

const table = new Array(3).fill([]);
function hash(key) { return key % 3; }

function insert(key) {
  const index = hash(key);
  table[index].push(key);
}

insert(1);
insert(4);
insert(7);
console.log(table);

What is the bug and how to fix it?

medium

A. Bug: All indexes share the same array; Fix: Use Array.from with () => []

B. Bug: hash function is incorrect; Fix: Use key % 10 instead

C. Bug: push method is wrong; Fix: Use unshift instead

D. Bug: table size is too small; Fix: Increase size to 10

Solution

1. Step 1: Identify the bug with fill([])

   Using fill([]) assigns the same array reference to all indexes.

2. Step 2: Fix by creating unique arrays per index

   Use Array.from({ length: 3 }, () => []) to create separate arrays.

3. Final Answer:

   Bug: All indexes share the same array; Fix: Use Array.from with () => [] -> Option A

4. Quick Check:

   fill([]) shares arrays, Array.from creates unique ones [OK]

Hint: Avoid fill([]); use Array.from with function [OK]

Common Mistakes:

• Changing hash function unnecessarily
• Using wrong array methods
• Ignoring shared reference problem

5. You have a hash table of size 4 using chaining. You insert keys [3, 7, 11, 15, 19]. The hash function is key % 4. After all insertions, which index has the longest chain and what is its content?

medium

A. Index 3: [3, 7, 11, 15, 19]

B. Index 1: [3, 7, 11, 15, 19]

C. Index 3: [3, 7, 11, 15]

D. Index 3: [3, 7, 11]

Solution

1. Step 1: Compute hash index for each key

   3 % 4 = 3, 7 % 4 = 3, 11 % 4 = 3, 15 % 4 = 3, 19 % 4 = 3.

2. Step 2: Insert all keys at index 3

   All keys go into table[3], so chain is [3, 7, 11, 15, 19].

3. Final Answer:

   Index 3: [3, 7, 11, 15, 19] -> Option A

4. Quick Check:

   All keys mod 4 = 3, chain length 5 [OK]

Hint: All keys mod 4 equal 3, so chain at index 3 [OK]

Common Mistakes:

• Miscomputing modulo for some keys
• Assuming keys spread across indexes
• Forgetting all keys collide at same index