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

Concept Flow - Collision Handling Using Open Addressing Linear Probing

Start: Insert key

↓

Compute hash index

↓

Check slot at index

↓

Slot empty?

Yes→Insert key here

No↓

Move to next index (linear probing)

↓

Index wraps around?

Yes→Start from 0

↓

Repeat check slot

↓

If full table, insertion fails

Insert key by hashing to index; if occupied, move step-by-step to next slot until empty found or table full.

Execution Sample

DSA Python

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

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

Execution Table

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

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
hash_table	[None, None, None, None, None]	[None, None, 7, None, None]	[None, None, 7, None, None]	[None, None, 7, 12, None]	[None, None, 7, 12, None]	[None, None, 7, 12, None]	[None, None, 7, 12, 17]	[None, None, 7, 12, 17]
index	N/A	2	2 then 3	3	2 then 3 then 4	4	N/A	N/A
key	N/A	7	12	12	17	17	N/A	N/A

Key Moments - 3 Insights

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

Because the slot at the computed index already holds a key (see steps 2 and 4 in execution_table), linear probing moves sequentially to the next slot to find an empty place.

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

The index wraps around to 0 (start of the table) as shown in the concept_flow, ensuring all slots are checked circularly.

Why does the insertion stop after finding an empty slot?

Because the key is successfully placed there, no need to continue probing (see steps 1, 3, and 6 where insertion happens).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the slot status at computed index?

A Empty

B Occupied by 12

C Occupied by 7

D Occupied by 17

💡 Hint

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

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

A Step 2

B Step 3

C Step 5

D Step 6

💡 Hint

Look for the 'Action' column mentioning insertion for key 12 in execution_table.

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

A Insertion would fail due to full table

B Inserted at index 2 without probing

C Probing would wrap around and find an empty slot

D Inserted at index 1 directly

💡 Hint

Consider the table size and probing steps in variable_tracker and concept_flow.

Concept Snapshot

Collision Handling Using Open Addressing Linear Probing:
- Compute index = key % table_size
- If slot occupied, move to next index (index + 1) % table_size
- Repeat until empty slot found or table full
- Insert key at empty slot
- Wrap around to start if end reached
- Ensures all slots checked sequentially
- Stops when key inserted or table full

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 index by taking the key modulo the table size. If the slot at that index is empty, we insert the key there. If it is occupied, we move step-by-step to the next slot, wrapping around to the start if needed, until we find an empty slot. This process is called linear probing. The execution table traces inserting keys 7, 12, and 17 into a size 5 table, showing how collisions at index 2 are resolved by moving to the next free slots. The variable tracker shows how the hash table and index change after each step. Key moments clarify why we probe next slots and how wrap-around works. The visual quiz tests understanding of slot status, insertion steps, and behavior with smaller table sizes. The snapshot summarizes the key rules for linear probing collision handling.

Practice

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

easy

A. Double the size of the hash table when a collision occurs.

B. If a slot is occupied, check the next slot sequentially until an empty one is found.

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

D. Rehash all elements using a new hash function.

Solution

1. Step 1: Understand linear probing concept

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

2. Step 2: Compare with other methods

   Other methods like chaining use linked lists, resizing, or rehashing, which are different from linear probing.

3. Final Answer:

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

4. Quick Check:

   Linear probing = sequential slot check [OK]

Hint: Linear probing means try next slot until free [OK]

Common Mistakes:

• Confusing linear probing with chaining
• Thinking linear probing resizes the table
• Assuming rehashing is part of linear 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 a collision occurs at index i?

easy

A. (i + 2) % m

B. (i * 2) % m

C. (i + 1) % m

D. (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: Apply modulo for wrap-around

   Using modulo ensures the index wraps around to the start if it reaches the end of the table.

3. Final Answer:

   (i + 1) % m -> Option C

4. Quick Check:

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

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

Common Mistakes:

• Adding 2 instead of 1 for next index
• Multiplying index instead of adding
• Not using modulo for wrap-around

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. [None, None, 7, 12, 17]

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

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

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

Solution

1. Step 1: Calculate initial positions

   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 taken, so try index 3. Insert 12 at index 3. For 17, indices 2 and 3 are taken, so insert at index 4.

3. Final Answer:

   [None, None, 7, 12, 17] -> Option A

4. Quick Check:

   Keys placed at 2, 3, 4 with linear probing [OK]

Hint: Check hash index, then next free slot sequentially [OK]

Common Mistakes:

• Placing all keys at same index ignoring collisions
• Not probing to next slot after collision
• Miscomputing hash values

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

def insert(table, key):
    m = len(table)
    index = key % m
    while table[index] is not None:
        index = (index + 1) % m
    table[index] = key

hash_table = [None]*5
insert(hash_table, 5)
insert(hash_table, 10)
insert(hash_table, 15)
insert(hash_table, 20)
insert(hash_table, 25)
insert(hash_table, 30)

medium

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

B. No bug; code works correctly for all insertions.

C. Wrong hash function used; should be key // m.

D. Table size should be dynamic, not fixed.

Solution

1. Step 1: Analyze insertion loop

   The while loop continues probing until it finds an empty slot but has no check for full table.

2. Step 2: Identify problem when table is full

   If all slots are occupied, the loop cycles endlessly, causing infinite loop.

3. Final Answer:

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

4. Quick Check:

   Full table causes infinite loop without exit [OK]

Hint: Check for full table to avoid infinite loop [OK]

Common Mistakes:

• Assuming hash function is wrong
• Ignoring infinite loop possibility
• Thinking dynamic size fixes this bug

5. You have a hash table of size 7 using linear probing. Insert keys [14, 21, 28, 35, 42] using hash function h(k) = k % 7. After all insertions, what is the index of key 42 in the table?

hard

A. 5

B. 0

C. 6

D. 4

Solution

1. Step 1: Calculate initial hash indices

   h(14)=0, h(21)=0, h(28)=0, h(35)=0, h(42)=0 (all keys hash to index 0).

2. Step 2: Insert keys using linear probing

   Insert 14 at 0. For 21, index 0 taken, try 1. Insert 21 at 1. For 28, indices 0 and 1 taken, insert at 2. For 35, insert at 3. For 42, insert at 4.

3. Step 3: Find index of key 42

   Key 42 is at index 4.

4. Final Answer:

   4 -> Option D

5. Quick Check:

   42 placed at first free slot after collisions [OK]

Hint: All keys collide; count steps from initial index [OK]

Common Mistakes:

• Assuming key stays at initial hash index
• Not probing sequentially after collisions
• Miscounting index after multiple collisions