Collision Handling Using Chaining in DSA Javascript

Mental Model

When two keys map to the same spot, we keep a list there to hold all items. This way, no data is lost.

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

Hash Table Array:
[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

After inserting keys with collisions:
[0] -> (key1) -> (key5) -> null
[1] -> null
[2] -> (key2) -> null
[3] -> null
[4] -> (key3) -> (key8) -> null

Dry Run Walkthrough

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

Goal: Show how collisions are handled by storing multiple keys in a linked list at the same index

Step 1: Insert key 5: hash(5) = 5, place at index 5

[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null
[5] -> (5) -> null
[6] -> null
[7] -> null
[8] -> null
[9] -> null

Why: Key 5 hashes to index 5, which is empty, so we put it there.

Step 2: Insert key 15: hash(15) = 5, collision at index 5, add to linked list

[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null
[5] -> (5) -> (15) -> null
[6] -> null
[7] -> null
[8] -> null
[9] -> null

Why: Key 15 also hashes to index 5, so we add it after key 5 in the list.

Step 3: Insert key 25: hash(25) = 5, collision at index 5, add to linked list

[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null
[5] -> (5) -> (15) -> (25) -> null
[6] -> null
[7] -> null
[8] -> null
[9] -> null

Why: Key 25 also hashes to index 5, so we add it at the end of the list.

Result:

[0] -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null
[5] -> (5) -> (15) -> (25) -> null
[6] -> null
[7] -> null
[8] -> null
[9] -> null

Annotated Code

DSA Javascript

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

class HashTable {
  constructor(size) {
    this.size = size;
    this.buckets = new Array(size).fill(null);
  }

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

  insert(key) {
    const index = this.hash(key); // find bucket index
    const newNode = new Node(key);
    if (this.buckets[index] === null) {
      this.buckets[index] = newNode; // place node if empty
    } else {
      let current = this.buckets[index];
      while (current.next !== null) {
        current = current.next; // move to end of list
      }
      current.next = newNode; // add new node at end
    }
  }

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

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

const index = this.hash(key);

compute bucket index using hash function

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

if bucket empty, place new node directly

while (current.next !== null) { current = current.next;

traverse linked list to find last node

current.next = newNode;

append new node at end of chain to handle collision

Output

[0] -> null

[1] -> null

[2] -> null

[3] -> null

[4] -> null

[5] -> (5) -> (15) -> (25) -> null

[6] -> null

[7] -> null

[8] -> null

[9] -> null

Complexity Analysis

Time: O(n/k) on average, where n is number of keys and k is number of buckets, because each bucket's chain length is n/k on average

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

vs Alternative: Compared to open addressing which stores all keys in array slots, chaining uses extra space for linked lists but handles collisions more flexibly without clustering.

Edge Cases

Inserting into an empty bucket

Key is placed directly without chaining

DSA Javascript

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

Multiple keys hashing to same index

Keys are linked in a chain at that bucket

DSA Javascript

while (current.next !== null) {
  current = current.next;

Hash table size is 1 (all keys collide)

All keys form one long chain at index 0

DSA Javascript

const index = this.hash(key);

When to Use This Pattern

When you see a hash table problem where multiple keys can map to the same index, reach for chaining because it stores collided keys in linked lists to avoid losing data.

Common Mistakes

Mistake: Overwriting existing key in bucket instead of chaining
Fix: Check if bucket is empty before inserting; if not, traverse to end and append new node.

Mistake: Not handling null next pointer when traversing chain
Fix: Use a while loop to move until current.next is null before adding new node.

Summary

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

Use it when your hash function causes collisions and you want to keep all keys safely.

The key insight is to keep a chain of nodes at each bucket to hold collided keys instead of replacing them.

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