Why Collision Handling Using Open Addressing Linear Probing in DSA C++?

The Big Idea

What if your data could always find a home without getting lost or overwritten?

The Scenario

Imagine you have a small mailbox with numbered slots for letters. When two letters arrive for the same slot number, you have to decide where to put the second letter. If you just try to put it in the same slot, it won't fit.

The Problem

Manually checking each slot to find an empty one takes a lot of time and can cause confusion. You might forget which slots you already checked or accidentally overwrite letters. This makes the process slow and error-prone.

The Solution

Open Addressing with Linear Probing solves this by automatically checking the next slot in order until it finds an empty one. This way, you don't lose any letters and can find them quickly by following the same order.

Before vs After

✗ Before

int index = hash(key);
if (table[index] != EMPTY) {
  // Manually search for empty slot
  while (table[index] != EMPTY) {
    index = (index + 1) % size;
  }
}
table[index] = key;

✓ After

int index = hash(key);
while (table[index] != EMPTY) {
  index = (index + 1) % size;
}
table[index] = key;

What It Enables

This method enables efficient storage and retrieval of data even when collisions happen, keeping operations fast and simple.

Real Life Example

Think of a parking lot with numbered spots. If your assigned spot is taken, you park in the next available spot. Later, you find your car by checking spots in order.

Key Takeaways

Manual collision handling is slow and error-prone.

Linear probing checks next slots automatically to find empty space.

This keeps data organized and easy to find despite collisions.

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