Collision Handling Using Open Addressing Linear Probing in DSA Rust - 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)

↓

Back to Check slot

↓

If full cycle done

→Table full, insertion fails

Insert key by hashing to index; if occupied, check next slot linearly until empty slot found or full cycle done.

Execution Sample

DSA Rust

let mut table = vec![None; 5];
let keys = [7, 12, 17];
for &key in &keys {
    let mut idx = key % 5;
    while table[idx].is_some() {
        idx = (idx + 1) % 5;
    }
    table[idx] = Some(key);
}

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

Execution Table

Step	Operation	Key	Index Checked	Slot Empty?	Action	Table State
1	Insert	7	7 % 5 = 2	Yes	Insert 7 at index 2	[None, None, 7, None, None]
2	Insert	12	12 % 5 = 2	No (7 present)	Probe next index 3	[None, None, 7, None, None]
3	Insert	12	3	Yes	Insert 12 at index 3	[None, None, 7, 12, None]
4	Insert	17	17 % 5 = 2	No (7 present)	Probe next index 3	[None, None, 7, 12, None]
5	Insert	17	3	No (12 present)	Probe next index 4	[None, None, 7, 12, None]
6	Insert	17	4	Yes	Insert 17 at index 4	[None, None, 7, 12, 17]
7	End	-	-	-	All keys inserted	[None, None, 7, 12, 17]

💡 All keys inserted successfully; no full cycle needed.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
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]
idx (for 7)	N/A	2	2	2	2	2	2	2
idx (for 12)	N/A	N/A	2 -> 3	3	3	3	3	3
idx (for 17)	N/A	N/A	N/A	2 -> 3	2 -> 3 -> 4	4	4	4

Key Moments - 3 Insights

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

Because the slot is already occupied by another key, so we use linear probing to find the next empty slot 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, continuing the search for an empty slot until we either find one or complete a full cycle, as seen in the index calculations in variable_tracker.

Why does the insertion stop after all keys are placed?

Because each key finds an empty slot without completing a full cycle, so the process ends successfully as indicated in step 7 of the execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, at which index is key 12 inserted?

A Index 3

B Index 2

C Index 4

D Index 1

💡 Hint

Check step 3 in the execution_table where key 12 is inserted.

At which step does the probing move from index 3 to index 4 for key 17?

A Step 4

B Step 6

C Step 5

D Step 2

💡 Hint

Look at steps 4 and 5 in the execution_table for key 17's index changes.

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

A Insertion fails due to full table

B Insertion succeeds at index 2

C Insertion succeeds at index 0

D Insertion overwrites existing key

💡 Hint

Hashes: 7%3=1 at index 1, 12%3=0 at index 0, 17%3=2 at index 2. No collisions, direct insertion at index 2.

Concept Snapshot

Collision Handling Using Open Addressing Linear Probing:
- Compute hash index for key
- If slot occupied, move to next index (linear probing)
- Wrap around table using modulo
- Insert key at first empty slot found
- If full cycle done, insertion fails

Full Transcript

This visualization shows how keys are inserted into a hash table using open addressing with linear probing. Each key is hashed to an index. If that slot is empty, the key is placed there. If occupied, the algorithm checks the next slot, moving forward one by one, wrapping around the table if needed. This continues until an empty slot is found or the table is full. The execution table traces each step, showing index checks, slot status, and table state. Variable tracker records the table and index changes for each key. Key moments clarify why probing moves forward, how wrap-around works, and when insertion stops. The quiz tests understanding of insertion positions, probing steps, and table capacity effects.

Practice

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

easy

A. Use a secondary hash function to find a new slot.

B. Use a linked list to store multiple values at the same index.

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 collision handling methods

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

2. Step 2: Compare with other methods

   Other methods include chaining (linked lists), resizing, or double hashing, but linear probing specifically uses sequential slots.

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 linear probing uses a second hash function
• Assuming table size doubles on collision

2. Which of the following Rust code snippets correctly implements linear probing to find the next index after a collision in a hash table of size table_size?

easy

A. let next_index = (current_index + 1) % table_size;

B. let next_index = (current_index * 2) % table_size;

C. let next_index = (current_index - 1) % table_size;

D. let next_index = (current_index + 3) % table_size;

Solution

1. Step 1: Understand linear probing index calculation

   Linear probing moves to the next slot by adding 1 to the current index and wrapping around using modulo.

2. Step 2: Check each option

   let next_index = (current_index + 1) % table_size; adds 1 and uses modulo, which is correct. Others multiply or subtract, which are not standard linear probing steps.

3. Final Answer:

   let next_index = (current_index + 1) % table_size; -> Option A

4. Quick Check:

   Linear probing = increment index by 1 modulo table size [OK]

Hint: Linear probing increments index by 1 modulo table size [OK]

Common Mistakes:

• Using multiplication instead of addition
• Subtracting index without handling negative wrap
• Skipping modulo operation causing out-of-bounds

3. Consider the following Rust code snippet for inserting keys into a hash table using linear probing. What will be the final state of the hash table array after inserting keys [5, 15, 25] with table size 10 and hash function key % 10?

let mut table = vec![None; 10];
let keys = vec![5, 15, 25];
for &key in &keys {
    let mut index = key % 10;
    while table[index].is_some() {
        index = (index + 1) % 10;
    }
    table[index] = Some(key);
}
println!("{:?}", table);

medium

A. [None, None, None, None, None, Some(5), Some(15), None, Some(25), None]

B. [None, None, None, None, None, Some(5), None, Some(15), Some(25), None]

C. [None, None, None, None, None, Some(5), Some(15), Some(25), None, None]

D. [Some(5), Some(15), Some(25), None, None, None, None, None, None, None]

Solution

1. Step 1: Calculate initial indices for keys

   Keys 5, 15, 25 all hash to index 5 (5 % 10 = 5, 15 % 10 = 5, 25 % 10 = 5).

2. Step 2: Insert keys using linear probing

   Insert 5 at index 5. For 15, index 5 is occupied, so move to 6. Insert 15 at 6. For 25, indices 5 and 6 are occupied, move to 7 and insert 25.

3. Final Answer:

   [None, None, None, None, None, Some(5), Some(15), Some(25), None, None] -> Option C

4. Quick Check:

   Linear probing places keys at 5, 6, 7 [OK]

Hint: Keys with same hash go to next free slot sequentially [OK]

Common Mistakes:

• Placing all keys at index 5 ignoring collisions
• Skipping modulo wrap-around
• Inserting keys at wrong indices after collision

4. The following Rust code attempts to insert keys into a hash table using linear probing. However, it sometimes causes an infinite loop. What is the bug?

let mut table = vec![None; 5];
let keys = vec![1, 6, 11];
for &key in &keys {
    let mut index = key % 5;
    while table[index].is_some() {
        index = (index + 1) % 5;
    }
    table[index] = Some(key);
}

medium

A. The code does not check if the table is full, causing infinite loop when no empty slot exists.

B. The modulo operator is used incorrectly; it should be key % 6.

C. The loop should break after checking only once to avoid infinite loop.

D. The vector size is too large, causing index out of bounds.

Solution

1. Step 1: Analyze the while loop condition

   The loop continues while the slot is occupied, moving to next index with wrap-around.

2. Step 2: Identify missing termination condition

   If the table is full, the loop cycles endlessly because no empty slot is found and no exit condition exists.

3. Final Answer:

   The code does not check if the table is full, causing infinite loop when no empty slot exists. -> Option A

4. Quick Check:

   Missing full-table check causes infinite loop [OK]

Hint: Always check for full table to avoid infinite loops [OK]

Common Mistakes:

• Ignoring full table condition
• Changing modulo divisor incorrectly
• Breaking loop too early causing wrong insertion

5. You have a hash table of size 7 using linear probing for collision handling. You insert keys [10, 20, 15, 7, 32] with hash function key % 7. After all insertions, what is the state of the table? Represent empty slots as null. Explain your answer step-by-step.

medium

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

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

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

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

Solution

1. Step 1: Calculate initial indices for each key

   10 % 7 = 3, 20 % 7 = 6, 15 % 7 = 1, 7 % 7 = 0, 32 % 7 = 4.

2. Step 2: Insert keys using linear probing

   All hashed indices are empty, so place: 10 at 3, 20 at 6, 15 at 1, 7 at 0, 32 at 4.

3. Step 3: Final table state

   Indices 2 and 5 remain null: [7, 15, null, 10, 32, null, 20].

4. Final Answer:

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

5. Quick Check:

   Insert keys at hashed index or next free slot [OK]

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

Common Mistakes:

• Not applying modulo correctly
• Placing keys at wrong indices after collision
• Ignoring empty slots in final output