Collision Handling Using Open Addressing Linear Probing in DSA Rust - Time & Space Complexity

Time Complexity: Collision Handling Using Open Addressing Linear Probing

O(n)

Understanding Time Complexity

We want to understand how long it takes to insert or find items when collisions happen in a hash table using linear probing.

How does the time grow as the table fills up?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn linear_probing_insert(table: &mut [Option], key: i32) {
    let size = table.len();
    let mut index = (key as usize) % size;
    while table[index].is_some() {
        index = (index + 1) % size;
    }
    table[index] = Some(key);
}
    

This code inserts a key into a hash table using linear probing to find the next free spot when a collision occurs.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that checks each slot until an empty one is found.
• How many times: In the worst case, it can check almost every slot in the table.

How Execution Grows With Input

When the table is mostly empty, the loop runs very few times. As the table fills, the loop runs more times, sometimes nearly the whole table.

Input Size (n)	Approx. Operations
10 (mostly empty)	1-2 checks
100 (half full)	5-10 checks
1000 (almost full)	up to 1000 checks

Pattern observation: The more full the table, the longer the search for an empty slot, growing roughly linearly with table size.

Final Time Complexity

Time Complexity: O(n)

This means in the worst case, the time to insert or find a key grows linearly with the size of the table.

Common Mistake

[X] Wrong: "Insertion always takes constant time because we just compute the hash once."

[OK] Correct: When collisions happen, we may need to check many slots, so the time depends on how full the table is.

Interview Connect

Understanding how collision handling affects performance shows you know practical trade-offs in data structures, a key skill in coding interviews.

Self-Check

"What if we changed linear probing to quadratic probing? How would the time complexity change?"

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