Collision Handling Using Open Addressing Linear Probing in DSA Rust

Mental Model

When two items want the same spot, try the next spots one by one until you find an empty one.

Analogy: Imagine parking cars in a row of parking spots. If your favorite spot is taken, you look at the next spot, then the next, until you find a free one.

Index: 0   1   2   3   4   5   6
Table: [ ] [ ] [ ] [ ] [ ] [ ] [ ]
          ↑
       hash position

Dry Run Walkthrough

Input: Insert keys 10, 20, 30 into a hash table of size 7 with hash function key % 7

Goal: Show how collisions are handled by moving to the next empty spot

Step 1: Insert 10 at index 3 (10 % 7 = 3)

Index: 0   1   2   3   4   5   6
Table: [ ] [ ] [ ] [10] [ ] [ ] [ ]

Why: 10's hash position is free, so insert directly

Step 2: Insert 20 at index 6 (20 % 7 = 6)

Index: 0   1   2   3   4   5   6
Table: [ ] [ ] [ ] [10] [ ] [ ] [20]

Why: 20's hash position is free, so insert directly

Step 3: Insert 30 at index 2 (30 % 7 = 2)

Index: 0   1   2   3   4   5   6
Table: [ ] [ ] [30] [10] [ ] [ ] [20]

Why: 30's hash position is free, so insert directly

Step 4: Insert 17 at index 3 (17 % 7 = 3), collision with 10, try next index 4

Index: 0   1   2   3   4   5   6
Table: [ ] [ ] [30] [10] [17] [ ] [20]

Why: Index 3 is taken, so move to next index 4 which is free

Step 5: Insert 24 at index 3 (24 % 7 = 3), collision with 10, try 4 (17), try 5 free

Index: 0   1   2   3   4   5   6
Table: [ ] [ ] [30] [10] [17] [24] [20]

Why: Indexes 3 and 4 are taken, so move to next free index 5

Result:

Index: 0   1   2   3   4   5   6
Table: [ ] [ ] [30] [10] [17] [24] [20]

Annotated Code

DSA Rust

struct HashTable {
    size: usize,
    table: Vec<Option<i32>>,
}

impl HashTable {
    fn new(size: usize) -> Self {
        Self {
            size,
            table: vec![None; size],
        }
    }

    fn hash(&self, key: i32) -> usize {
        (key as usize) % self.size
    }

    fn insert(&mut self, key: i32) {
        let mut index = self.hash(key);
        // try to find empty slot using linear probing
        while self.table[index].is_some() {
            index = (index + 1) % self.size; // move to next index
        }
        self.table[index] = Some(key); // insert key
    }

    fn display(&self) {
        for (i, val) in self.table.iter().enumerate() {
            match val {
                Some(k) => print!("[{}] ", k),
                None => print!("[ ] "),
            }
        }
        println!();
    }
}

fn main() {
    let mut ht = HashTable::new(7);
    let keys = vec![10, 20, 30, 17, 24];
    for key in keys {
        ht.insert(key);
    }
    ht.display();
}

let mut index = self.hash(key);

calculate initial hash index for the key

while self.table[index].is_some() {

check if current index is occupied to handle collision

index = (index + 1) % self.size;

move to next index in circular manner for linear probing

self.table[index] = Some(key);

insert key at found empty slot

Output

[ ] [ ] [30] [10] [17] [24] [20] 

Complexity Analysis

Time: O(n) in worst case because we may check every slot if many collisions happen

Space: O(n) because we store up to n keys in the table

vs Alternative: Compared to chaining which uses linked lists, linear probing keeps all keys in one array but may cause clustering and slower searches

Edge Cases

Inserting into a full table

The insert loop cycles through all slots and finds no empty slot, so insertion fails or loops infinitely if not handled

DSA Rust

while self.table[index].is_some() {

Inserting duplicate keys

Duplicates are inserted as separate entries in different slots

DSA Rust

while self.table[index].is_some() {

Empty table insertion

First insert goes directly to hashed index

DSA Rust

self.table[index] = Some(key);

When to Use This Pattern

When you see a hash table with collisions and need to store all keys in one array, use linear probing to find next free slot by checking sequentially.

Common Mistakes

Mistake: Not wrapping index back to start when reaching end of table
Fix: Use modulo operation to wrap index: index = (index + 1) % size

Mistake: Stopping insertion on first collision without probing next slots
Fix: Continue probing until an empty slot is found

Summary

It stores keys in a fixed-size array and handles collisions by checking next slots one by one.

Use it when you want a simple collision handling method without extra data structures.

The key insight is to keep moving forward in the array until you find an empty spot.

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