Collision Handling Using Open Addressing Linear Probing in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the main idea behind open addressing with linear probing in hash tables?

It means when a collision happens (two keys want the same spot), we look for the next empty spot in the table by moving one step at a time until we find a free slot.

intermediate

In linear probing, what happens if the hash table is full or nearly full?

The search for an empty spot can take longer because many slots are occupied, causing clustering and slowing down insertions and lookups.

beginner

Why do we use modulus (%) operation in linear probing?

To wrap around the hash table index when we reach the end, so we continue searching from the start of the table.

intermediate

What is a primary disadvantage of linear probing compared to other collision handling methods?

It can cause clustering, where groups of filled slots build up, making collisions more frequent and slowing down operations.

beginner

How does linear probing find a key during search in a hash table?

It starts at the hashed index and checks each slot moving forward one by one until it finds the key or an empty slot (meaning the key is not present).

What does linear probing do when a collision occurs in a hash table?

A Rehashes the key with a different function

B Creates a linked list at the collided slot

C Deletes the existing key to insert the new one

D Checks the next slot sequentially until an empty one is found

Linear probing searches the next slots one by one to find an empty slot after a collision.

Which problem is commonly caused by linear probing in hash tables?

A Clustering of filled slots

B Memory leaks

C Stack overflow

D Infinite loops in all cases

Linear probing can cause clustering, where many filled slots group together, slowing down operations.

How does linear probing handle the end of the hash table array during probing?

A Skips to the middle of the table

B Stops searching and returns failure

C Wraps around to the beginning using modulus operation

D Doubles the size of the table automatically

Linear probing uses modulus to wrap around the array index to continue searching from the start.

When searching for a key using linear probing, what indicates the key is not in the table?

A Finding a slot with a different key

B Encountering an empty slot during the probe

C Reaching the last slot in the table

D Finding a slot with the same key

If an empty slot is found during probing, it means the key was never inserted.

What is the main operation performed repeatedly in linear probing after a collision?

A Incrementing the index by one and checking the slot

B Rehashing the key with a new function

C Removing the collided key

D Splitting the table into smaller parts

Linear probing increments the index by one each time to find the next available slot.

Explain how linear probing handles collisions in a hash table and what happens when the end of the table is reached.

Think about walking forward in a circle looking for an empty seat.

Describe the main disadvantage of linear probing and how it affects hash table performance.

Imagine people sitting close together making it hard to find a free seat.

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