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

Concept Flow - Collision Handling Using Open Addressing Linear Probing

Start Insert

↓

Compute Hash Index

↓

Is Slot Empty?

No→Move to Next Slot (index+1)%size

↓

Repeat Check

↓

Insert Key Here

↓

Done

Insert key by computing hash index, if slot occupied, move linearly to next slot until empty slot found.

Execution Sample

DSA C#

int[] table = new int[5];
// Insert keys: 7, 12, 17
// Hash function: key % 5
// Linear probing on collision

Insert keys 7, 12, 17 into hash table of size 5 using linear probing for collisions.

Execution Table

Step	Operation	Key	Computed Index	Slot Status	Pointer Changes	Table State
1	Insert	7	7 % 5 = 2	Empty	Insert at index 2	[null, null, 7, null, null]
2	Insert	12	12 % 5 = 2	Occupied (7)	Move to index 3	[null, null, 7, null, null]
3	Check Slot	12	3	Empty	Insert at index 3	[null, null, 7, 12, null]
4	Insert	17	17 % 5 = 2	Occupied (7)	Move to index 3	[null, null, 7, 12, null]
5	Check Slot	17	3	Occupied (12)	Move to index 4	[null, null, 7, 12, null]
6	Check Slot	17	4	Empty	Insert at index 4	[null, null, 7, 12, 17]
7	End	-	-	-	-	[null, null, 7, 12, 17]

💡 All keys inserted; linear probing resolved collisions by moving to next empty slot.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
table	[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]
currentIndex	N/A	2	2 then 3	3	2 then 3	3 then 4	4	N/A
key	N/A	7	12	12	17	17	17	N/A

Key Moments - 3 Insights

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

Because the slot at the computed index already holds a key, linear probing moves step-by-step to the next slot to find an empty place, as shown in steps 2, 4, and 5 in the execution_table.

What happens if we reach the end of the table while probing?

We wrap around to the start of the table using modulo operation, ensuring we check all slots. This is implied by the pointer changes moving to (index + 1) % size.

Why is the table state unchanged when we check an occupied slot?

Because no insertion happens until an empty slot is found, so the table remains the same during these checks, as seen in steps 2 and 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the slot status for key 17 at index 2?

A Empty

B Occupied by 7

C Occupied by 12

D Null

💡 Hint

Check the 'Slot Status' column at step 4 in execution_table.

At which step does the key 12 get inserted into the table?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for 'Insert at index 3' operation in execution_table.

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

A Inserted at index 2 immediately

B Inserted at index 0 after probing

C Causes infinite loop because table is full

D Inserted at index 1 immediately

💡 Hint

Consider modulo operation key % 3 and linear probing steps.

Concept Snapshot

Open Addressing Linear Probing:
- Compute index = key % table_size
- If slot empty, insert key
- If occupied, move to next slot (index+1)%size
- Repeat until empty slot found
- Wrap around table if needed
- Resolves collisions by probing linearly

Full Transcript

This concept shows how to handle collisions in a hash table using open addressing with linear probing. When inserting a key, we compute its hash index using key modulo table size. If the slot at that index is empty, we insert the key there. If the slot is occupied, we move step-by-step to the next slot, wrapping around the table if needed, until we find an empty slot. This process is repeated for each key. The execution table traces inserting keys 7, 12, and 17 into a table of size 5, showing how collisions at index 2 are resolved by moving to the next available slots at indices 3 and 4. The variable tracker shows how the table and pointers change after each step. Key moments clarify why we probe linearly and how wrapping around works. The visual quiz tests understanding of slot status, insertion steps, and behavior with different table sizes.

Practice

1. What is the main idea behind Linear Probing in collision handling for hash tables?

easy

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

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

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

D. Replace the existing element in the slot with the new one.

Solution

1. Step 1: Understand collision handling methods

   Linear probing is a method where if a collision happens, the algorithm checks the next slot in the array sequentially.

2. Step 2: Compare options with linear probing definition

   If a collision occurs, check the next slot sequentially until an empty slot is found. correctly describes checking the next slot sequentially until an empty slot is found, which matches linear probing.

3. Final Answer:

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

4. Quick Check:

   Linear probing = check next slot sequentially [OK]

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

Common Mistakes:

• Confusing linear probing with chaining
• Thinking linear probing replaces existing elements
• Assuming table size doubles on collision

2. Which of the following is the correct way to calculate the next index in linear probing for a hash table of size tableSize when a collision occurs at index?

easy

A. nextIndex = (index * 2) % tableSize;

B. nextIndex = (index - 1) % tableSize;

C. nextIndex = (index + 1) % tableSize;

D. nextIndex = (index + 3) % tableSize;

Solution

1. Step 1: Recall linear probing formula

   Linear probing moves to the next slot by adding 1 to the current index and taking modulo with table size to wrap around.

2. Step 2: Match formula with options

   nextIndex = (index + 1) % tableSize; uses (index + 1) % tableSize, which is the correct formula for linear probing.

3. Final Answer:

   nextIndex = (index + 1) % tableSize; -> Option C

4. Quick Check:

   Linear probing next index = (index + 1) % size [OK]

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

Common Mistakes:

• Multiplying index instead of adding
• Subtracting instead of adding
• Adding a number other than 1

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

medium

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

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

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

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

Solution

1. Step 1: Calculate initial indices for each key

   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 index 3 (empty), insert 12. Insert 17: index 2 and 3 occupied, try index 4 (empty), insert 17.

3. Final Answer:

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

4. Quick Check:

   Keys collide at 2, placed at 2,3,4 sequentially [OK]

Hint: All keys hash to same index, place next free slot [OK]

Common Mistakes:

• Placing all keys at index 2 ignoring collisions
• Not wrapping around the table
• Inserting keys in wrong order

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

int tableSize = 5;
int[] hashTable = new int[tableSize];
for (int i = 0; i < tableSize; i++) hashTable[i] = -1;

int Hash(int key) => key % tableSize;

void Insert(int key) {
    int index = Hash(key);
    while (hashTable[index] != -1) {
        index = (index + 1);
    }
    hashTable[index] = key;
}

Insert(7);
Insert(12);
Insert(17);

medium

A. The hash function is incorrect for linear probing.

B. The Insert method should use recursion instead of a loop.

C. The initial hash table values should be 0, not -1.

D. The code does not wrap index back to 0 when it reaches the end of the table.

Solution

1. Step 1: Analyze the index update in the loop

   The code increments index by 1 on collision but does not use modulo to wrap around the table size.

2. Step 2: Identify the consequence of missing modulo

   Without modulo, index can go beyond array bounds causing runtime error or incorrect behavior.

3. Final Answer:

   The code does not wrap index back to 0 when it reaches the end of the table. -> Option D

4. Quick Check:

   Linear probing requires modulo to wrap index [OK]

Hint: Always use modulo to wrap index in linear probing [OK]

Common Mistakes:

• Forgetting modulo causes index out of range
• Changing hash function unnecessarily
• Thinking initial values must be zero

5. You have a hash table of size 7 using linear probing. The hash function is h(key) = key % 7. You insert keys: 10, 24, 31, 17, 3. Then you delete key 24 by marking its slot as empty. Now you want to search for key 31. What problem might occur and how to fix it?

hard

A. Search may stop early at the empty slot of deleted key 24, missing key 31; fix by using a special 'deleted' marker instead of empty.

B. Search will always find key 31 without issues; no fix needed.

C. Key 31 will be overwritten by key 24; fix by rehashing all keys after deletion.

D. The hash function is wrong; fix by changing it to key % 5.

Solution

1. Step 1: Understand deletion effect in linear probing

   Deleting by marking slot empty breaks the probe chain, so search may stop early and miss keys inserted after the deleted slot.

2. Step 2: Identify correct deletion method

   Use a special 'deleted' marker to indicate slot is free for insertion but search should continue probing.

3. Final Answer:

   Search may stop early at the empty slot of deleted key 24, missing key 31; fix by using a special 'deleted' marker instead of empty. -> Option A

4. Quick Check:

   Deleted slots need special marker to continue search [OK]

Hint: Use 'deleted' marker, not empty slot, to avoid search errors [OK]

Common Mistakes:

• Marking deleted slots as empty breaks search
• Assuming search always finds keys after deletion
• Changing hash function unnecessarily