Collision Handling Using Open Addressing Linear Probing in DSA C++ - Execution Trace

Concept Flow - Collision Handling Using Open Addressing Linear Probing

Start: Insert key

↓

Compute hash index

↓

Check slot at index

↓

Insert key

↓

Repeat check slot

↓

If full table, stop

↓

Done

When inserting a key, compute its hash index. If the slot is empty, insert it. If occupied, move to the next slot and repeat until an empty slot is found or the table is full.

Execution Sample

DSA C++

hashTable = [null, null, null, null, null]
keys = [7, 12, 17]
for key in keys:
  index = key % 5
  while hashTable[index] is not None:
    index = (index + 1) % 5
  hashTable[index] = key

Insert keys 7, 12, and 17 into a hash table of size 5 using linear probing to handle collisions.

Execution Table

Step	Operation	Key	Computed Index	Slot Status	Action	Hash Table State
1	Insert	7	7 % 5 = 2	Empty	Insert 7 at index 2	[null, null, 7, null, null]
2	Insert	12	12 % 5 = 2	Occupied (7)	Probe next index 3	[null, null, 7, null, null]
3	Check slot	12	3	Empty	Insert 12 at index 3	[null, null, 7, 12, null]
4	Insert	17	17 % 5 = 2	Occupied (7)	Probe next index 3	[null, null, 7, 12, null]
5	Check slot	17	3	Occupied (12)	Probe next index 4	[null, null, 7, 12, null]
6	Check slot	17	4	Empty	Insert 17 at index 4	[null, null, 7, 12, 17]
7	End	-	-	-	All keys inserted	[null, null, 7, 12, 17]

💡 All keys inserted or table full; insertion complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
hashTable	[null, null, null, null, null]	[null, null, 7, null, null]	[null, null, 7, null, null]	[null, null, 7, 12, null]	[null, null, 7, 12, null]	[null, null, 7, 12, null]	[null, null, 7, 12, 17]	[null, null, 7, 12, 17]
index	-	2	2 then 3	3	2 then 3	2 then 3 then 4	4	-
key	-	7	12	12	17	17	17	-

Key Moments - 3 Insights

Why do we move to the next index when the computed index slot is occupied?

Because the slot is already taken by another key, linear probing moves sequentially to find the next empty slot, as shown in steps 2, 4, and 5 in the execution_table.

What happens if the table is full and no empty slot is found?

The insertion stops because there is no space left. This is implied in the concept_flow where if the table is full, the process ends without insertion.

Why do we use modulo operation when moving to the next index?

Modulo ensures the index wraps around to the start of the table when reaching the end, preventing out-of-bounds errors. This is shown in the concept_flow and variable_tracker where index cycles within table size.

Visual Quiz - 3 Questions

Look at the execution_table, what is the hashTable state after inserting key 12?

A [null, null, 12, null, null]

B [null, null, 7, 12, null]

C [null, null, 7, null, null]

D [null, 12, 7, null, null]

💡 Hint

Refer to execution_table row 3 showing insertion of key 12 at index 3.

At which step does the linear probing move from index 3 to index 4?

A Step 5

B Step 2

C Step 4

D Step 6

💡 Hint

Check execution_table rows 4 and 5 where key 17 probes from index 3 to 4.

If the table size was 3 instead of 5, what would happen when inserting key 17 after 7 and 12?

A It would cause an infinite loop trying to find empty slot

B It would insert at index 0 after probing

C It would insert at index 2 without collision

D It would overwrite existing key

💡 Hint

With size 3, 7 % 3 = 1, 12 % 3 = 0, 17 % 3 = 2 hash to distinct indices 0,1,2 causing no collision for 17; it inserts at index 2.

Concept Snapshot

Collision Handling Using Open Addressing Linear Probing:
- Compute hash index for key
- If slot empty, insert key
- If occupied, move to next slot (index+1)%size
- Repeat until empty slot found or table full
- Wrap around using modulo
- Used to resolve collisions in hash tables

Full Transcript

This concept shows how to handle collisions in hash tables using open addressing with linear probing. When inserting a key, we compute its hash index. If the slot is empty, we insert the key there. If the slot is occupied, we move to the next slot sequentially, wrapping around the table if needed, until we find an empty slot or the table is full. The execution table traces inserting keys 7, 12, and 17 into a size 5 table, showing how collisions at index 2 are resolved by probing subsequent slots. The variable tracker shows how the hash table and index change after each step. Key moments clarify why we probe next slots, what happens if the table is full, and why modulo is used to wrap indices. The visual quiz tests understanding of the table state after insertions and probing behavior. This method ensures all keys can be inserted if space is available, avoiding overwriting and handling collisions efficiently.

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