Collision Handling Using Chaining in DSA Rust - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is collision handling in hash tables?

Collision handling is the method used to resolve situations when two keys hash to the same index in a hash table.

beginner

Explain chaining as a collision handling technique.

Chaining handles collisions by storing all elements that hash to the same index in a linked list or another data structure at that index.

beginner

In chaining, what happens when multiple keys hash to the same bucket?

All keys are stored in a linked list at that bucket, allowing multiple elements to coexist at the same index.

intermediate

What is the average time complexity for search in a hash table using chaining?

The average time complexity is O(1 + α), where α is the load factor (number of elements divided by number of buckets).

intermediate

Why is chaining considered a simple and effective collision handling method?

Because it allows unlimited elements per bucket using linked lists, avoids clustering, and is easy to implement.

What data structure is commonly used in chaining to handle collisions?

A Linked list

B Array

C Stack

D Queue

Chaining uses linked lists to store multiple elements at the same hash index.

If two keys hash to the same index in chaining, what happens?

A Both keys are stored in a linked list at that index

B One key overwrites the other

C The table resizes immediately

D The second key is discarded

Chaining stores all colliding keys in a linked list at the same index.

What is the load factor in a hash table?

A Number of collisions

B Number of buckets divided by number of elements

C Number of elements divided by number of buckets

D Size of linked list

Load factor is the ratio of elements to buckets, affecting performance.

Which of these is a benefit of chaining over open addressing?

A No extra memory needed

B No linked lists required

C Faster worst-case search

D Handles unlimited collisions per bucket

Chaining can store unlimited elements per bucket using linked lists.

What is the worst-case time complexity for search in chaining?

A O(1)

B O(n)

C O(n log n)

D O(log n)

In the worst case, all elements are in one bucket, making search O(n).

Describe how chaining handles collisions in a hash table.

Think about how multiple items can share the same spot.

Explain the impact of load factor on the performance of chaining.

Consider how crowded the buckets get.

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