Collision Handling Using Chaining in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new empty hash table with chaining.

DSA Rust

let mut table: Vec<Vec<i32>> = Vec::new();
table.[1](Vec::new());

Drag options to blanks, or click blank then click option'

Aremove

Bpop

Cinsert

Dpush

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop instead of push removes elements instead of adding.

Using remove or insert requires an index and is not suitable here.

We use push to add a new empty vector (chain) to the hash table vector.

2fill in blank

medium

Complete the code to compute the hash index for a key.

DSA Rust

let index = (key as usize) [1] table.len();

Drag options to blanks, or click blank then click option'

A%

B/

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using division (/) returns a quotient, not an index.

Using multiplication (*) or addition (+) can go out of bounds.

The modulo operator % gives the remainder, which fits the key into the table size.

3fill in blank

hard

Fix the error in adding a key to the chain at the computed index.

DSA Rust

table[index].[1](key);

Drag options to blanks, or click blank then click option'

Apush

Bpop

Cremove

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using remove or pop removes elements instead of adding.

Using insert requires an index and is more complex here.

push adds the key to the end of the chain vector at the index.

4fill in blank

hard

Fill both blanks to check if a key exists in the chain at the index.

DSA Rust

if table[index].[1](|&x| x == key) [2] None {
    println!("Key found");
}

Drag options to blanks, or click blank then click option'

Aiter().position

Bcontains

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using contains returns a bool directly instead of Option.

Using == None checks if key is NOT found.

iter().position(|&x| x == key) returns an Option which is Some(position) if the key is found, so != None confirms the key exists.

5fill in blank

hard

Fill all three blanks to remove a key from the chain if it exists.

DSA Rust

if let Some(pos) = table[index].[1](|&x| x == key) {
    table[index].[2](pos);
    println!("Removed key: {}", [3]);
}

Drag options to blanks, or click blank then click option'

Aiter().position

Bremove

Ckey

Dpop

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop removes the last element, not the key.

Using contains instead of position does not give index.

iter().position finds the position of key; remove(pos) deletes it; printing key shows which key was removed.

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