Collision Handling Using Open Addressing Linear Probing in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Linear Probing Insertions

What is the state of the hash table after inserting keys 10, 22, 31, 4, 15 into an empty hash table of size 7 using linear probing?

DSA Javascript

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

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

  insert(key) {
    let idx = this.hash(key);
    while (this.table[idx] !== null) {
      idx = (idx + 1) % this.size;
    }
    this.table[idx] = key;
  }
}

const ht = new HashTable(7);
[10, 22, 31, 4, 15].forEach(k => ht.insert(k));
console.log(ht.table);

A [null, 22, 15, 10, 31, 4, null]

B [10, 22, 31, 4, 15, null, null]

C [10, null, 22, 31, 4, 15, null]

D [null, 10, 22, 31, 4, 15, null]

💡 Hint

Remember linear probing moves to the next slot if the hashed index is occupied.

Keys are inserted using hash = key % 7. Collisions are resolved by moving to the next empty slot.

• 10 % 7 = 3 → slot 3 empty → insert 10
• 22 % 7 = 1 → slot 1 empty → insert 22
• 31 % 7 = 3 → slot 3 occupied → move to 4 → empty → insert 31
• 4 % 7 = 4 → slot 4 occupied → move to 5 → empty → insert 4
• 15 % 7 = 1 → slot 1 occupied → move to 2 → empty → insert 15

Final table: [null, 22, 15, 10, 31, 4, null]

🧠 Conceptual

intermediate

Linear Probing Search Result

Given a hash table of size 5 with keys inserted using linear probing: [null, 12, 22, 32, 42], what will be the result of searching for key 42?

A Not found

B Found at index 1

C Found at index 0

D Found at index 4

💡 Hint

Check the hash index and probe linearly until key is found or empty slot.

Hash function: key % 5

• 42 % 5 = 2
• Index 2 has 22 (not 42), move to 3
• Index 3 has 32 (not 42), move to 4
• Index 4 has 42 → found

🔧 Debug

advanced

Identify the Bug in Linear Probing Insert

What error will occur when running this linear probing insert method if the hash table is full?

DSA Javascript

insert(key) {
  let idx = this.hash(key);
  while (this.table[idx] !== null) {
    idx = (idx + 1) % this.size;
  }
  this.table[idx] = key;
}

A TypeError due to null access

B IndexError out of bounds

C Infinite loop when table is full

D No error, inserts successfully

💡 Hint

Consider what happens if all slots are occupied.

If the table is full, the while loop cycles through all indices endlessly because no null slot is found, causing an infinite loop.

❓ Predict Output

advanced

Output After Deletion and Re-insertion

Given a hash table of size 5 with keys 12, 22, 32, 42 inserted using linear probing: [42, null, 12, 22, 32], if key 22 is deleted and then key 52 is inserted, what is the final state of the table?

DSA Javascript

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

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

  insert(key) {
    let idx = this.hash(key);
    while (this.table[idx] !== null && this.table[idx] !== 'DELETED') {
      idx = (idx + 1) % this.size;
    }
    this.table[idx] = key;
  }

  delete(key) {
    let idx = this.hash(key);
    let start = idx;
    while (this.table[idx] !== null) {
      if (this.table[idx] === key) {
        this.table[idx] = 'DELETED';
        return true;
      }
      idx = (idx + 1) % this.size;
      if (idx === start) break;
    }
    return false;
  }
}

const ht = new HashTable(5);
[12, 22, 32, 42].forEach(k => ht.insert(k));
ht.delete(22);
ht.insert(52);
console.log(ht.table);

A [52, 12, 'DELETED', 32, 42]

B [42, null, 12, 52, 32]

C [null, 12, 'DELETED', 32, 42]

D [null, 12, 52, 32, null]

💡 Hint

Deleted slots can be reused for new insertions.

Initial table after insertions: [42, null, 12, 22, 32]

Delete 22 sets index 3 to 'DELETED'.

Insert 52 hashes to 2, probes to 3 ('DELETED'), inserts 52 there.

Final table: [42, null, 12, 52, 32]

🧠 Conceptual

expert

Why Linear Probing Causes Clustering

Why does linear probing cause primary clustering in hash tables?

A Because consecutive occupied slots cause longer probe sequences for new keys hashing nearby

B Because it uses a secondary hash function to resolve collisions

C Because it rehashes the entire table on every insertion

D Because it stores keys in linked lists at each slot

💡 Hint

Think about how linear probing searches for empty slots.

Linear probing places collided keys in the next available slot, creating groups of occupied slots. This makes future collisions near these groups cause longer searches, called primary clustering.

Practice

1. What is the main idea behind linear probing in collision handling for hash tables?

easy

A. If a collision occurs, check the next slot sequentially until an empty slot is found.

B. Use a linked list at each slot to store multiple values.

C. Double the size of the hash table when a collision happens.

D. Replace the existing value in the slot with the new value.

Solution

1. Step 1: Understand collision handling methods

   Linear probing handles collisions by searching the next available slot in a sequence.

2. Step 2: Identify linear probing behavior

   When a collision happens, linear probing checks the next slot one by one until it finds an empty slot.

3. Final Answer:

   If a collision occurs, check the next slot sequentially until an empty slot is found. -> Option A

4. Quick Check:

   Linear probing = sequential slot check [OK]

Hint: Linear probing means try next slot one by one [OK]

Common Mistakes:

• Confusing linear probing with chaining
• Thinking collision means resizing immediately
• Replacing existing values instead of probing

2. Which of the following is the correct way to calculate the next index in linear probing for a hash table of size m when current index is i?

easy

A. (i * 2) % m

B. (i - 1) % m

C. (i + 3) % m

D. (i + 1) % m

Solution

1. Step 1: Recall linear probing index update

   Linear probing moves to the next slot by adding 1 to the current index.

2. Step 2: Apply modulo to wrap around

   To stay within table size, use modulo operation with table size m.

3. Final Answer:

   (i + 1) % m -> Option D

4. Quick Check:

   Next index = (current + 1) mod size [OK]

Hint: Next index in linear probing is (i + 1) mod table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• Not using modulo to wrap index
• Subtracting instead of adding

3. Consider a hash table of size 5 using linear probing. The hash function is h(k) = k % 5. Insert keys 7, 12, 17 in order. What is the final state of the table (index: value)?

medium

A. 0: null, 1: null, 2: 7, 3: 12, 4: 17

B. 0: null, 1: 7, 2: null, 3: 12, 4: 17

C. 0: 7, 1: 12, 2: 17, 3: null, 4: null

D. 0: null, 1: 7, 2: 12, 3: 17, 4: null

Solution

1. Step 1: Calculate initial positions using hash function

   7 % 5 = 2, 12 % 5 = 2, 17 % 5 = 2. All keys initially map to index 2.

2. Step 2: Insert keys using linear probing

   Insert 7 at index 2 (empty). Insert 12: index 2 occupied, try 3 (empty), insert at 3. Insert 17: index 2 occupied, 3 occupied, try 4 (empty), insert at 4.

3. Final Answer:

   0: null, 1: null, 2: 7, 3: 12, 4: 17 -> Option A

4. Quick Check:

   Keys placed at 2, 3, 4 with probing [OK]

Hint: All keys hash to 2, probe next slots for empty [OK]

Common Mistakes:

• Placing all keys at index 2 ignoring collisions
• Skipping slots incorrectly during probing
• Miscomputing hash values

4. The following code snippet tries to insert keys into a hash table using linear probing. What is the bug?

const size = 7;
const table = new Array(size).fill(null);
function hash(key) {
  return key % size;
}
function insert(key) {
  let index = hash(key);
  while (table[index] !== null) {
    index = (index + 1) % size;
  }
  table[index] = key;
}
insert(10);
insert(17);
insert(24);
console.log(table);

medium

A. The hash function should use key % (size - 1) instead of key % size.

B. The table array should be initialized with zeros instead of null.

C. The insert function does not handle the case when the table is full, causing an infinite loop.

D. The index update in the while loop should subtract 1 instead of adding 1.

Solution

1. Step 1: Analyze insert function loop

   The while loop probes next slots until it finds an empty slot (null).

2. Step 2: Identify missing full table check

   If the table is full, the loop cycles endlessly without exit condition, causing infinite loop.

3. Final Answer:

   The insert function does not handle the case when the table is full, causing an infinite loop. -> Option C

4. Quick Check:

   Missing full table check causes infinite loop [OK]

Hint: Always check for full table to avoid infinite loops [OK]

Common Mistakes:

• Thinking modulo should be size-1
• Ignoring infinite loop possibility
• Confusing null with zero initialization

5. You have a hash table of size 10 using linear probing. The table currently stores keys at indices: 2, 3, 4, 5. You want to insert key 22. The hash function is h(k) = k % 10. Which index will key 22 be inserted into?

hard

A. 2

B. 6

C. 7

D. 5

Solution

1. Step 1: Calculate initial index for key 22

   22 % 10 = 2, so initial index is 2.

2. Step 2: Apply linear probing to find empty slot

   Indices 2, 3, 4, 5 are occupied. Next index is 6, which is free.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Start at 2, probe until free slot at 6 [OK]

Hint: Probe forward from hash index until empty slot found [OK]

Common Mistakes:

• Inserting at first hashed index ignoring occupancy
• Stopping probing too early
• Choosing wrong next index