Collision Handling Using Chaining in DSA Rust - Time & Space Complexity

Time Complexity: Collision Handling Using Chaining

O(n/k)

Understanding Time Complexity

When we use chaining to handle collisions in a hash table, we want to know how fast operations like insert or search run.

We ask: How does the time to find or add an item grow as the table gets more items?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Node {
    key: i32,
    next: Option>,
}

fn search(head: &Option>, key: i32) -> bool {
    let mut current = head.as_ref();
    while let Some(node) = current {
        if node.key == key {
            return true;
        }
        current = node.next.as_ref();
    }
    false
}
    

This code searches for a key in a linked list used in chaining to handle collisions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Traversing the linked list nodes one by one.
• How many times: Up to the length of the chain (number of nodes in the list).

How Execution Grows With Input

As more items hash to the same slot, the linked list grows longer, so searching takes more steps.

Input Size (n)	Approx. Operations
10	About 1 to 2 steps (if spread well)
100	About 10 steps in worst case (longer chains)
1000	About 100 steps if many collide in one chain

Pattern observation: The time grows roughly in proportion to the chain length, which depends on how many items collide.

Final Time Complexity

Time Complexity: O(n/k) where k is the number of buckets.

This means the time grows with the average number of items per bucket, so if buckets grow, search slows down linearly.

Common Mistake

[X] Wrong: "Searching in chaining is always O(1) because hash tables are fast."

[OK] Correct: If many keys collide, the linked list grows, making search take longer, so it is not always constant time.

Interview Connect

Understanding how chaining affects time helps you explain hash table performance clearly and shows you know how collisions impact speed.

Self-Check

"What if we used balanced trees instead of linked lists for chaining? How would the time complexity change?"

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