Collision Handling Using Open Addressing Linear Probing in DSA Rust - Build from Scratch

Collision Handling Using Open Addressing Linear Probing

📖 Scenario: Imagine you are building a simple phone book app that stores phone numbers by names. Sometimes, two names might want to use the same spot in your storage. To handle this, you will use a method called linear probing to find the next free spot.

🎯 Goal: You will create a small hash table using a vector in Rust. You will insert names and phone numbers. When a spot is taken, you will use linear probing to find the next empty spot. Finally, you will print the state of the hash table.

📋 What You'll Learn

Create a vector to represent the hash table with fixed size

Create a simple hash function to find index from name

Implement linear probing to handle collisions

Insert multiple entries and print the final hash table

💡 Why This Matters

🌍 Real World

Hash tables with collision handling are used in databases, caches, and many software systems to store and retrieve data quickly.

💼 Career

Understanding collision handling and hash tables is essential for software engineers working on performance-critical applications and data storage solutions.

1

Create the hash table vector

Create a vector called hash_table with 5 elements, each initialized to None. Use Option<(String, String)> as the type to store name and phone number pairs.

DSA Rust

# Create a vector called hash_table with 5 None elements
# Your code here

Hint

Use vec![None; 5] to create a vector with 5 empty slots.

2

Create a simple hash function

Create a function called hash that takes a &str called key and returns a usize. The function should return the sum of the bytes of key modulo 5.

DSA Rust

let mut hash_table: Vec> = vec![None; 5];

// Create a hash function that sums bytes of key and mods by 5
// Your code here

Hint

Use key.bytes() to get bytes, sum them, then use % 5 to get index.

3

Insert entries using linear probing

Write a function called insert that takes hash_table: &mut Vec>, key: String, and value: String. Use the hash function to find the start index. If the spot is taken, move to the next index (wrap around) until an empty spot is found. Insert the (key, value) pair there.

DSA Rust

let mut hash_table: Vec> = vec![None; 5];

fn hash(key: &str) -> usize {
    key.bytes().map(|b| b as usize).sum::() % 5
}

// Write insert function using linear probing
// Your code here

Hint

Use a loop and check if hash_table[index] is None. If not, increase index by 1 and wrap around.

4

Insert entries and print the hash table

Insert these entries into hash_table using insert: ("Alice", "123"), ("Bob", "456"), ("Carol", "789"), ("Dave", "101"), ("Eve", "112"). Then print the hash_table showing each index and the stored pair or Empty if none.

DSA Rust

let mut hash_table: Vec> = vec![None; 5];

fn hash(key: &str) -> usize {
    key.bytes().map(|b| b as usize).sum::() % 5
}

fn insert(hash_table: &mut Vec>, key: String, value: String) {
    let mut index = hash(&key);
    let size = hash_table.len();
    loop {
        if hash_table[index].is_none() {
            hash_table[index] = Some((key, value));
            break;
        } else {
            index = (index + 1) % size;
        }
    }
}

// Insert entries and print the hash table
// Your code here

Hint

Call insert for each pair. Then use a for loop with enumerate() to print each index and its content.

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