Collision Handling Using Chaining in DSA Rust

Mental Model

When two keys want the same spot in a table, we keep them in a small linked list at that spot.

Analogy: Imagine a mailbox with several slots. If two letters come for the same slot, you put them in a small pile inside that slot instead of losing one.

Hash Table:
[0] -> 25 -> 15 -> null
[1] -> null
[2] -> null
[3] -> 33 -> null
[4] -> null

Dry Run Walkthrough

Input: Insert keys 15, 25, 33 into a hash table of size 5 using chaining

Goal: Show how collisions are handled by adding nodes to linked lists at the same index

Step 1: Insert 15: compute index 15 % 5 = 0, add 15 at index 0

[0] -> 15 -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: We place 15 in the slot found by the hash function

Step 2: Insert 25: compute index 25 % 5 = 0, collision at index 0, add 25 at front of list

[0] -> 25 -> 15 -> null
[1] -> null
[2] -> null
[3] -> null
[4] -> null

Why: We add 25 to the linked list at index 0 to handle collision

Step 3: Insert 33: compute index 33 % 5 = 3, add 33 at index 3

[0] -> 25 -> 15 -> null
[1] -> null
[2] -> null
[3] -> 33 -> null
[4] -> null

Why: 33 goes to an empty slot, no collision

Result:

[0] -> 25 -> 15 -> null
[1] -> null
[2] -> null
[3] -> 33 -> null
[4] -> null

Annotated Code

DSA Rust

use std::collections::LinkedList;

struct HashTable {
    buckets: Vec<LinkedList<i32>>,
    size: usize,
}

impl HashTable {
    fn new(size: usize) -> Self {
        let mut buckets = Vec::with_capacity(size);
        for _ in 0..size {
            buckets.push(LinkedList::new());
        }
        HashTable { buckets, size }
    }

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

    fn insert(&mut self, key: i32) {
        let index = self.hash(key); // compute index
        self.buckets[index].push_front(key); // add key to front of linked list
    }

    fn display(&self) {
        for (i, bucket) in self.buckets.iter().enumerate() {
            print!("[{}] -> ", i);
            for val in bucket {
                print!("{} -> ", val);
            }
            println!("null");
        }
    }
}

fn main() {
    let mut table = HashTable::new(5);
    table.insert(15);
    table.insert(25);
    table.insert(33);
    table.display();
}

let index = self.hash(key);

compute bucket index using hash function

self.buckets[index].push_front(key);

insert key at front of linked list to handle collision

for (i, bucket) in self.buckets.iter().enumerate() {

iterate over all buckets to display their contents

Output

[0] -> 25 -> 15 -> null

[1] -> null

[2] -> null

[3] -> 33 -> null

[4] -> null

Complexity Analysis

Time: O(1) for insert because we add at front of linked list (constant time); worst O(n) for search if many collisions in one bucket

Space: O(n) for storing all keys in linked lists inside the table

vs Alternative: Compared to open addressing, chaining uses extra space for linked lists but avoids clustering and is simpler to implement

Edge Cases

Inserting into an empty hash table

Key is added to an empty linked list at computed index

DSA Rust

self.buckets[index].push_front(key);

Multiple keys hashing to same index

Keys are stored in linked list at that index, preserving all keys

DSA Rust

self.buckets[index].push_front(key);

Hash table size is 0 (invalid)

Program may panic or behave unexpectedly; no guard in code

DSA Rust

None (not handled)

When to Use This Pattern

When you see a hash table problem with collisions, think of chaining to store multiple keys in a linked list at the same index to keep all data safe.

Common Mistakes

Mistake: Overwriting existing key in bucket instead of adding to linked list
Fix: Always add new keys to the linked list at the bucket instead of replacing

Mistake: Not computing index with modulo, causing out-of-bounds errors
Fix: Use modulo operation with table size to find correct bucket index

Summary

It stores multiple keys that hash to the same index in a linked list at that index.

Use it when your hash function causes collisions and you want to keep all keys safely.

The key insight is to keep a small chain of keys at each bucket instead of losing data.

Practice

1. What is the main idea behind collision handling using chaining in a hash table?

easy

A. Resize the hash table when a collision occurs

B. Store all elements that hash to the same index in a linked list at that index

C. Use a second hash function to find a new index

D. Ignore collisions and overwrite existing values

Solution

1. Step 1: Understand collision in hash tables

   When two keys hash to the same index, a collision occurs.

2. Step 2: How chaining handles collisions

   Chaining stores all collided elements in a linked list at that index to keep them separate.

3. Final Answer:

   Store all elements that hash to the same index in a linked list at that index -> Option B

4. Quick Check:

   Chaining = linked list at index [OK]

Hint: Chaining means linked lists at each hash index [OK]

Common Mistakes:

• Thinking chaining resizes the table
• Confusing chaining with open addressing
• Assuming collisions are ignored

2. Which of the following Rust code snippets correctly declares a hash table using chaining with vectors of linked lists?

easy

A. let mut table: Vec> = vec![None; 10];

B. let mut table: Vec<i32> = vec![0; 10];

C. let mut table: HashMap = HashMap::new();

D. let mut table: Vec = vec![Vec::new(); 10];

Solution

1. Step 1: Identify chaining structure in Rust

   Chaining uses a vector where each element is a linked list (starting with Option) holding collided keys.

2. Step 2: Check each option

   A declares Vec> for vector of linked list heads, correct for chaining with linked lists. B is simple Vec<i32>, no chaining. C is HashMap, built-in not manual. D is Vec, chaining with dynamic arrays not linked lists.

3. Final Answer:

   let mut table: Vec> = vec![None; 10]; -> Option A

4. Quick Check:

   Chaining = Vec of Option [OK]

Hint: Chaining with linked lists uses Vec> for buckets in Rust [OK]

Common Mistakes:

• Using HashMap instead of manual vector of linked lists
• Using simple Vec<i32> without chaining structure
• Confusing Vec dynamic arrays with linked lists

3. Given the following Rust code using chaining for collision handling, what will be printed?

let mut table: Vec = vec![Vec::new(); 3];
let keys = [1, 4, 7];
for &key in &keys {
    let index = key % 3;
    table[index].push(key);
}
print!("{:?}", table);

medium

A. [[], [], [1, 4, 7]]

B. [[1, 4, 7], [], []]

C. [[1], [4], [7]]

D. [[], [1, 4, 7], []]

Solution

1. Step 1: Calculate indices for each key

   1 % 3 = 1, 4 % 3 = 1, 7 % 3 = 1, so all keys go to index 1.

2. Step 2: Check table after insertion

   table[0] = [], table[1] = [1, 4, 7], table[2] = []

3. Final Answer:

   [[], [1, 4, 7], []] -> Option D

4. Quick Check:

   All keys at index 1 [OK]

Hint: Calculate key % table size to find bucket [OK]

Common Mistakes:

• Assuming keys distribute evenly
• Mixing up modulo results
• Printing table before insertion

4. Identify the bug in this Rust code snippet for inserting keys into a hash table using chaining:

let mut table: Vec = vec![Vec::new(); 5];
let keys = [2, 7, 25];
for key in keys {
    let index = key / 5;
    table[index].push(key);
}

medium

A. Keys array should be mutable to insert

B. The vector initialization is incorrect; should use Vec::with_capacity

C. Using division instead of modulo for index calculation causes out-of-bounds error

D. The push method is used incorrectly on the vector

Solution

1. Step 1: Analyze index calculation

   Index is calculated as key / 5: 2/5=0, 7/5=1, 25/5=5 which is out-of-bounds (table indices 0-4).

2. Step 2: Check vector size and index range

   Table size is 5, division can produce index >=5 causing panic. Use modulo % instead.

3. Final Answer:

   Using division instead of modulo for index calculation causes out-of-bounds error -> Option C

4. Quick Check:

   Index must be key % size [OK]

Hint: Use modulo (%) for index, not division (/) [OK]

Common Mistakes:

• Using division instead of modulo
• Ignoring vector size limits
• Assuming keys array must be mutable

5. You want to implement a hash table with chaining in Rust that supports inserting keys and searching for a key. Which approach correctly handles collisions and allows efficient search?

hard

A. Use a Vec where each inner Vec stores keys hashed to that bucket; search by hashing key and scanning inner Vec

B. Use a single Vec<i32> and linear search for keys; ignore collisions

C. Use a HashMap and store keys as values; collisions handled internally

D. Use a Vec and replace existing keys on collision

Solution

1. Step 1: Understand chaining for collision handling

   Chaining stores collided keys in a list at each bucket, allowing multiple keys per index.

2. Step 2: Search method in chaining

   To search, hash the key to find the bucket, then scan the list for the key.

3. Final Answer:

   Use a Vec where each inner Vec stores keys hashed to that bucket; search by hashing key and scanning inner Vec -> Option A

4. Quick Check:

   Chaining = Vec of Vec + scan search [OK]

Hint: Chaining stores collisions in lists; search by bucket then scan [OK]

Common Mistakes:

• Ignoring collisions and overwriting keys
• Using linear search without hashing
• Confusing HashMap with manual chaining