Collision Handling Using Open Addressing Linear Probing in DSA C++ - 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, 20, 30, 40 into a hash table of size 5 using linear probing with hash function h(key) = key % 5?

DSA C++

int hashTable[5] = {-1, -1, -1, -1, -1};
int size = 5;
int keys[] = {10, 20, 30, 40};

for (int key : keys) {
    int index = key % size;
    while (hashTable[index] != -1) {
        index = (index + 1) % size;
    }
    hashTable[index] = key;
}

for (int i = 0; i < size; i++) {
    std::cout << hashTable[i] << " ";
}

A [10, 20, 30, 40, -1]

B [10, 20, 30, -1, 40]

C [10, -1, 20, 30, 40]

D [-1, 10, 20, 30, 40]

💡 Hint

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

Keys are inserted using h(key) = key % 5. For 10, index 0 is free. For 20, index 0 is occupied, so move to 1. For 30, index 0 and 1 are occupied, so move to 2. For 40, indices 0,1,2 are occupied, so move to 3.

❓ Predict Output

intermediate

Result of Searching in Linear Probing Hash Table

Given a hash table of size 7 with keys inserted using linear probing and hash function h(key) = key % 7, what is the index returned when searching for key 24 if the table contains keys [14, 21, 28, 35, 42, 49, 56] inserted in that order?

DSA C++

int hashTable[7] = {14, 21, 28, 35, 42, 49, 56};
int size = 7;
int key = 24;

int index = key % size;
int start = index;
while (hashTable[index] != key) {
    index = (index + 1) % size;
    if (index == start || hashTable[index] == -1) {
        index = -1;
        break;
    }
}
std::cout << index;

A -1

B 3

C 0

D 6

💡 Hint

If the key is not found after probing all slots, the search returns -1.

Key 24 hashes to index 3. The slot at index 3 contains 35, not 24. Linear probing checks next slots but none contain 24. After full cycle, key not found, so return -1.

🔧 Debug

advanced

Identify the Bug in Linear Probing Insertion

What is the error in the following linear probing insertion code snippet?

DSA C++

void insert(int hashTable[], int size, int key) {
    int index = key % size;
    while (hashTable[index] != -1) {
        index = (index + 1) % size;
    }
    hashTable[index] = key;
}

// hashTable initialized with -1 for empty slots

A No error, code works correctly for insertion.

B Wrong hash function used; should be key / size.

C Infinite loop if the table is full because no check for full table.

D Should use double hashing instead of linear probing.

💡 Hint

Consider what happens if all slots are occupied.

If the table is full, the while loop cycles endlessly because no slot is -1. There is no condition to stop or report full table.

🚀 Application

advanced

Handling Deletion in Linear Probing Hash Table

Which approach correctly handles deletion of a key in a linear probing hash table to avoid breaking the search chain?

A Set the slot to -1 (empty) directly after deletion.

B Rehash the entire table after every deletion.

C Shift all subsequent keys backward to fill the deleted slot.

D Mark the slot with a special 'deleted' marker and continue probing during search.

💡 Hint

Think about how search depends on continuous probing.

Directly setting a slot to empty breaks the search chain. Using a 'deleted' marker allows search to continue probing correctly.

🧠 Conceptual

expert

Why Linear Probing Causes Clustering

Why does linear probing in open addressing cause primary clustering in hash tables?

A Because linear probing uses multiple hash functions causing collisions.

B Because keys that hash to the same index form long contiguous blocks, increasing probe lengths.

C Because it deletes keys by shifting elements, causing gaps.

D Because it uses chaining with linked lists causing uneven distribution.

💡 Hint

Consider how linear probing handles collisions by moving sequentially.

Linear probing places collided keys in consecutive slots, creating clusters that grow and increase search times.

Practice

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

easy

A. Rehash all elements to a new table when a collision occurs.

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

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

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

Solution

1. Step 1: Understand linear probing concept

   Linear probing handles collisions by checking the next slot in order if the original slot is occupied.

2. Step 2: Compare with other methods

   Other options describe chaining or resizing, not linear probing.

3. Final Answer:

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

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
• Assuming random slot 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 - 1) % m

D. (i + 3) % m

Solution

1. Step 1: Recall linear probing formula

   Linear probing moves to the next slot by adding 1 to the current index, wrapping around using modulo.

2. Step 2: Verify modulo usage

   Modulo with table size m ensures index stays within bounds.

3. Final Answer:

   (i + 1) % m -> Option B

4. Quick Check:

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

Hint: Next slot 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 7 using linear probing. The hash function is h(k) = k % 7. Insert keys 10, 20, 15 in order. What is the final state of the table (index: value)?

medium

A. 0: null, 1: 15, 2: null, 3: 10, 4: null, 5: null, 6: 20

B. 0: null, 1: null, 2: 15, 3: 10, 4: 20, 5: null, 6: null

C. 0: null, 1: null, 2: 10, 3: 20, 4: 15, 5: null, 6: null

D. 0: null, 1: null, 2: 10, 3: 15, 4: 20, 5: null, 6: null

Solution

1. Step 1: Compute hashes and insert 10

   h(10) = 10 % 7 = 3, index 3 empty, insert 10 at 3.

2. Step 2: Insert 20

   h(20) = 20 % 7 = 6, index 6 empty, insert 20 at 6.

3. Step 3: Insert 15

   h(15) = 15 % 7 = 1, index 1 empty, insert 15 at 1.

4. Final Answer:

   0: null, 1: 15, 2: null, 3: 10, 4: null, 5: null, 6: 20 -> Option A

5. Quick Check:

   Positions 1:15, 3:10, 6:20 [OK]

Hint: Calculate hash, insert keys, probe next if occupied [OK]

Common Mistakes:

• Miscomputing hash values
• Not applying modulo correctly
• Placing keys at wrong indices

4. The following code snippet attempts to insert keys into a hash table using linear probing. Identify the bug:

int hash(int key, int size) { return key % size; }

void insert(int table[], int size, int key) {
  int index = hash(key, size);
  while (table[index] != -1) {
    index = (index + 1) % size;
  }
  table[index] = key;
}

int main() {
  int size = 5;
  int table[5] = {-1, -1, -1, -1, -1};
  insert(table, size, 5);
  insert(table, size, 10);
  insert(table, size, 15);
  insert(table, size, 20);
  insert(table, size, 25);
  insert(table, size, 30);
  return 0;
}

medium

A. Infinite loop possible when table is full because no stop condition in while loop.

B. Hash function is incorrect; should use (key + 1) % size.

C. No bug, code works correctly for all insertions.

D. Array initialization with -1 is invalid in C++.

Solution

1. Step 1: Analyze insertion loop

   The while loop probes next index until an empty slot (-1) is found.

2. Step 2: Check for full table scenario

   If the table is full, the loop will cycle endlessly without a stop condition.

3. Step 3: Confirm other options

   Hash function is correct modulo. Array initialization with -1 is valid. So only infinite loop is the bug.

4. Final Answer:

   Infinite loop possible when table is full because no stop condition in while loop. -> Option A

5. Quick Check:

   Full table causes infinite loop in linear probing [OK]

Hint: Check if loop stops when table is full [OK]

Common Mistakes:

• Ignoring full table infinite loop
• Thinking hash function is wrong
• Assuming array init with -1 is invalid

5. You have a hash table of size 10 using linear probing. The table currently stores keys at indices: 2, 3, 4, 5, 6. You want to insert key 12 where h(k) = k % 10. If index 2 is occupied, what sequence of indices will be checked before insertion? What index will key 12 be inserted at if indices 2 to 6 are occupied but index 7 is free?

hard

A. Check indices 2, 4, 6, 8; insert at 8

B. Check indices 2, 3, 4; insert at 4

C. Check indices 2, 3, 4, 5, 6, 7; insert at 7

D. Check indices 2, 3, 4, 5, 6; insert at 2

Solution

1. Step 1: Calculate initial index for key 12

   h(12) = 12 % 10 = 2, so start checking at index 2.

2. Step 2: Apply linear probing sequence

   Since indices 2, 3, 4, 5, 6 are occupied, check next indices sequentially: 2, 3, 4, 5, 6, then 7.

3. Step 3: Find first free slot

   Index 7 is free, so insert key 12 at index 7.

4. Final Answer:

   Check indices 2, 3, 4, 5, 6, 7; insert at 7 -> Option C

5. Quick Check:

   Linear probe checks sequential slots until free [OK]

Hint: Probe sequentially until free slot found [OK]

Common Mistakes:

• Skipping indices in probing
• Inserting at first occupied slot
• Not wrapping index with modulo