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

↓

Place key

↓

Repeat check until empty slot found

↓

Done

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

Execution Sample

DSA C

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;
}

This code inserts keys into a hash table using linear probing to handle collisions.

Execution Table

Step	Operation	Key	Computed Index	Slot Checked	Slot Status	Action	Table State
1	Insert key	10	10 % 11 = 10	10	Empty	Place key at index 10	[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10]
2	Insert key	22	22 % 11 = 0	0	Empty	Place key at index 0	[22, -1, -1, -1, -1, -1, -1, -1, -1, -1, 10]
3	Insert key	31	31 % 11 = 9	9	Empty	Place key at index 9	[22, -1, -1, -1, -1, -1, -1, -1, -1, 31, 10]
4	Insert key	4	4 % 11 = 4	4	Empty	Place key at index 4	[22, -1, -1, -1, 4, -1, -1, -1, -1, 31, 10]
5	Insert key	15	15 % 11 = 4	4	Occupied (4)	Move to index 5	[22, -1, -1, -1, 4, -1, -1, -1, -1, 31, 10]
6	Check slot	15	5	5	Empty	Place key at index 5	[22, -1, -1, -1, 4, 15, -1, -1, -1, 31, 10]
7	Insert key	28	28 % 11 = 6	6	Empty	Place key at index 6	[22, -1, -1, -1, 4, 15, 28, -1, -1, 31, 10]
8	Insert key	17	17 % 11 = 6	6	Occupied (28)	Move to index 7	[22, -1, -1, -1, 4, 15, 28, -1, -1, 31, 10]
9	Check slot	17	7	7	Empty	Place key at index 7	[22, -1, -1, -1, 4, 15, 28, 17, -1, 31, 10]
10	Insert key	88	88 % 11 = 0	0	Occupied (22)	Move to index 1	[22, -1, -1, -1, 4, 15, 28, 17, -1, 31, 10]
11	Check slot	88	1	1	Empty	Place key at index 1	[22, 88, -1, -1, 4, 15, 28, 17, -1, 31, 10]
12	Insert key	59	59 % 11 = 4	4	Occupied (4)	Move to index 5	[22, 88, -1, -1, 4, 15, 28, 17, -1, 31, 10]
13	Check slot	59	5	5	Occupied (15)	Move to index 6	[22, 88, -1, -1, 4, 15, 28, 17, -1, 31, 10]
14	Check slot	59	6	6	Occupied (28)	Move to index 7	[22, 88, -1, -1, 4, 15, 28, 17, -1, 31, 10]
15	Check slot	59	7	7	Occupied (17)	Move to index 8	[22, 88, -1, -1, 4, 15, 28, 17, -1, 31, 10]
16	Check slot	59	8	8	Empty	Place key at index 8	[22, 88, -1, -1, 4, 15, 28, 17, 59, 31, 10]
17	Insert key	5	5 % 11 = 5	5	Occupied (15)	Move to index 6	[22, 88, -1, -1, 4, 15, 28, 17, 59, 31, 10]
18	Check slot	5	6	6	Occupied (28)	Move to index 7	[22, 88, -1, -1, 4, 15, 28, 17, 59, 31, 10]
19	Check slot	5	7	7	Occupied (17)	Move to index 8	[22, 88, -1, -1, 4, 15, 28, 17, 59, 31, 10]
20	Check slot	5	8	8	Occupied (59)	Move to index 9	[22, 88, -1, -1, 4, 15, 28, 17, 59, 31, 10]
21	Check slot	5	9	9	Occupied (31)	Move to index 10	[22, 88, -1, -1, 4, 15, 28, 17, 59, 31, 10]
22	Check slot	5	10	10	Occupied (10)	Move to index 0	[22, 88, -1, -1, 4, 15, 28, 17, 59, 31, 10]
23	Check slot	5	0	0	Occupied (22)	Move to index 1	[22, 88, -1, -1, 4, 15, 28, 17, 59, 31, 10]
24	Check slot	5	1	1	Occupied (88)	Move to index 2	[22, 88, -1, -1, 4, 15, 28, 17, 59, 31, 10]
25	Check slot	5	2	2	Empty	Place key at index 2	[22, 88, 5, -1, 4, 15, 28, 17, 59, 31, 10]
26	End	-	-	-	-	-	Insertion complete
27	Final Table State	-	-	-	-	-	[22, 88, 5, -1, 4, 15, 28, 17, 59, 31, 10]

💡 Insertion stops when an empty slot is found or table is full.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 6	After Step 9	After Step 11	After Step 16	After Step 25	Final
index	-	10	0	9	4	5	7	1	8	2	-
table	[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]	[-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,10]	[22,-1,-1,-1,-1,-1,-1,-1,-1,-1,10]	[22,-1,-1,-1,-1,-1,-1,-1,-1,31,10]	[22,-1,-1,-1,4,-1,-1,-1,-1,31,10]	[22,-1,-1,-1,4,15,-1,-1,-1,31,10]	[22,-1,-1,-1,4,15,-1,17,-1,31,10]	[22,88,-1,-1,4,15,-1,17,-1,31,10]	[22,88,-1,-1,4,15,-1,17,59,31,10]	[22,88,5,-1,4,15,-1,17,59,31,10]	[22,88,5,-1,4,15,-1,17,59,31,10]

Key Moments - 3 Insights

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

Because in linear probing, if the computed slot is taken, we check the next slot to find an empty place. This is shown in execution_table rows 5, 8, 10, etc., where the slot is occupied and the index moves forward.

What happens if the index reaches the end of the table?

The index wraps around to the start using modulo operation. For example, in step 22, index moves from 10 to 0, ensuring we check all slots circularly.

Why do we stop inserting when we find an empty slot?

Because the key can be safely placed there without collision. This is shown in steps 1, 2, 3, 4, 6, 9, 11, 16, and 25 where insertion happens at empty slots.

Visual Quiz - 3 Questions

Look at the execution_table at step 5. What is the slot status at index 4?

A Empty

B Out of bounds

C Occupied

D Deleted

💡 Hint

Check the 'Slot Status' column for step 5 in execution_table.

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

A Step 16

B Step 14

C Step 13

D Step 15

💡 Hint

Look for the row where 'Place key at index 8' happens for key 59.

If the key 5 was inserted before key 59, at which index would it be placed according to the variable_tracker?

A Index 5

B Index 2

C Index 8

D Index 0

💡 Hint

Check variable_tracker for index values after step 25 where key 5 is placed.

Concept Snapshot

Collision Handling Using Open Addressing Linear Probing:
- Compute hash index: 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
- Stops when key inserted or table full

Full Transcript

This visualization shows how keys are inserted into a hash table using linear probing to handle collisions. Each key's hash index is computed using modulo operation. If the slot at that index is empty, the key is placed there. If occupied, the algorithm moves to the next slot, wrapping around the table if needed, until an empty slot is found. The execution table tracks each insertion step, showing the key, computed index, slot checked, slot status, action taken, and the table state after the operation. The variable tracker shows how the index and table change over time. Key moments clarify why the algorithm moves to the next slot on collision, how wrapping works, and when insertion stops. The visual quiz tests understanding of slot status, insertion steps, and final placement. This method ensures all keys are stored without overwriting existing keys by probing linearly for free slots.

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 to store multiple elements at the same index.

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

D. Rehash all elements using a new hash function when a collision occurs.

Solution

1. Step 1: Understand linear probing concept

   Linear probing handles collisions by checking the next slot in the array sequentially when the desired slot is occupied.

2. Step 2: Compare options with definition

   If a collision occurs, check the next slot sequentially until an empty slot is found. correctly describes this sequential checking. Other options describe different collision handling methods.

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 rehashing happens on every collision
• Assuming table size doubles automatically

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. next_index = (i + 3) % m

B. next_index = (i * 2) % m

C. next_index = (i - 1) % m

D. next_index = (i + 1) % m

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.

2. Step 2: Match formula with options

   next_index = (i + 1) % m matches this formula: (i + 1) % m. Other options use incorrect increments.

3. Final Answer:

   next_index = (i + 1) % m -> Option D

4. Quick Check:

   Linear probing next index = (i + 1) mod m [OK]

Hint: Linear probing adds 1 to index modulo table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• 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(k) = k % 5. Insert keys 7, 12, 17 in order. What is the final state of the table?

medium

A. [7, 12, 17, null, null]

B. [7, null, 12, 17, null]

C. [null, null, 7, 12, 17]

D. [null, 7, 12, 17, null]

Solution

1. Step 1: Calculate initial positions using hash function

   h(7) = 7 % 5 = 2, h(12) = 12 % 5 = 2, h(17) = 17 % 5 = 2.

2. Step 2: Insert keys using linear probing

   Insert 7 at index 2. For 12, index 2 is occupied, so try index 3. Insert 12 at index 3. For 17, indices 2 and 3 are occupied, so insert at index 4.

3. Final Answer:

   [null, null, 7, 12, 17] -> Option C

4. Quick Check:

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

Hint: Check hash index, then next slots if occupied [OK]

Common Mistakes:

• Placing all keys at same index ignoring collisions
• Not wrapping around table size
• Misplacing keys at wrong indices

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

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;
}

medium

A. The index update should subtract 1 instead of adding 1.

B. The table is not initialized with -1 for empty slots.

C. The while loop condition should check for table[index] == -1.

D. The hash function should use multiplication instead of modulo.

Solution

1. Step 1: Analyze the insert function logic

   The function checks for empty slots by comparing with -1, so the table must be initialized with -1 to mark empty slots.

2. Step 2: Identify missing initialization

   If the table is not initialized with -1, the condition table[index] != -1 may fail incorrectly, causing wrong insertions or infinite loops.

3. Final Answer:

   The table is not initialized with -1 for empty slots. -> Option B

4. Quick Check:

   Empty slots must be marked -1 [OK]

Hint: Initialize table slots with -1 before insertion [OK]

Common Mistakes:

• Ignoring table initialization
• Wrong loop condition in while
• Incorrect hash function usage

5. You have a hash table of size 7 using linear probing. Insert keys 10, 20, 15, 7, 32 in order using hash function h(k) = k % 7. After all insertions, what is the content of the table?

hard

A. [7, 15, null, 10, 32, null, 20]

B. [null, 15, 32, 10, null, 20, 7]

C. [null, 15, 32, 10, 20, 7, null]

D. [null, 15, 32, 10, 20, null, 7]

Solution

1. Step 1: Calculate initial indices for each key

   h(10)=3, h(20)=6, h(15)=1, h(7)=0, h(32)=4.

2. Step 2: Insert keys using linear probing

   Insert 10 at index 3. Insert 20 at index 6. Insert 15 at index 1. Insert 7 at index 0. Insert 32 at index 4 (empty). Final table: [7, 15, null, 10, 32, null, 20].

3. Step 3: Match with options

   [7, 15, null, 10, 32, null, 20] matches the correct order. Nulls at indices 2 and 5.

4. Final Answer:

   [7, 15, null, 10, 32, null, 20] -> Option A

5. Quick Check:

   Keys placed at their hash or next free slot [OK]

Hint: Calculate hash, insert or probe next free slot [OK]

Common Mistakes:

• Not probing when slot is occupied
• Misplacing keys at wrong indices
• Ignoring table size wrap-around