Collision Handling Using Chaining in DSA Rust - Execution Trace

Concept Flow - Collision Handling Using Chaining

Compute hash index

↓

Check bucket at index

↓

Bucket empty?

No→Add new node at bucket's linked list head

Yes↓

Create new linked list with node

↓

Done

This flow shows how a key is hashed to an index, then inserted into a linked list at that bucket to handle collisions.

Execution Sample

DSA Rust

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

fn insert(head: &mut Option<Box<Node>>, key: i32) {
    let new_node = Box::new(Node { key, next: head.take() });
    *head = Some(new_node);
}

This code inserts a key at the head of a linked list to handle collisions in a hash table bucket.

Execution Table

Step	Operation	Bucket Index	Bucket State Before	Pointer Changes	Bucket State After	Visual State
1	Compute hash for key=10	0	[]	None	[]	[]
2	Insert key=10 at bucket 0	0	[]	head -> new_node	[10]	[10 -> null]
3	Compute hash for key=20	0	[10]	None	[10]	[10 -> null]
4	Insert key=20 at bucket 0	0	[10]	head -> new_node	[20 -> 10]	[20 -> 10 -> null]
5	Compute hash for key=15	1	[]	None	[]	[]
6	Insert key=15 at bucket 1	1	[]	head -> new_node	[15]	[15 -> null]
7	Compute hash for key=25	1	[15]	None	[15]	[15 -> null]
8	Insert key=25 at bucket 1	1	[15]	head -> new_node	[25 -> 15]	[25 -> 15 -> null]
9	Compute hash for key=30	2	[]	None	[]	[]
10	Insert key=30 at bucket 2	2	[]	head -> new_node	[30]	[30 -> null]
11	End of insertions	-	[20 -> 10]	None	[20 -> 10]	[Bucket 0: 20 -> 10 -> null, Bucket 1: 25 -> 15 -> null, Bucket 2: 30 -> null]

💡 All keys inserted; chaining linked lists built at each bucket to handle collisions.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	Final
bucket[0]	[]	[10]	[20 -> 10]	[20 -> 10]	[20 -> 10]	[20 -> 10]	[20 -> 10]
bucket[1]	[]	[]	[]	[15]	[25 -> 15]	[25 -> 15]	[25 -> 15]
bucket[2]	[]	[]	[]	[]	[]	[30]	[30]

Key Moments - 3 Insights

Why do we insert the new node at the head of the linked list instead of the tail?

Inserting at the head is simpler and faster because we only change the head pointer (see steps 2, 4, 6, 8, 10 in execution_table). No need to traverse the list.

What happens if two keys hash to the same bucket?

They form a linked list at that bucket (chaining). For example, keys 10 and 20 both hash to bucket 0 and are linked as 20 -> 10 (steps 2 and 4).

Why do we use Option<Box<Node>> for the linked list?

Option<Box<Node>> allows us to represent either a node (Some) or the end of the list (None), enabling safe linked list construction and traversal.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the visual state of bucket 0?

A [10 -> null]

B [20 -> 10 -> null]

C [20 -> null]

D []

💡 Hint

Check the 'Visual State' column at step 4 in execution_table.

At which step does bucket 1 first get a node inserted?

A Step 6

B Step 5

C Step 7

D Step 8

💡 Hint

Look at the 'Operation' and 'Bucket State After' columns for bucket 1 in execution_table.

If we insert a new key that hashes to bucket 2, where will it be placed in the linked list?

A At the tail of the list

B In the middle of the list

C At the head of the list

D It replaces the existing node

💡 Hint

Refer to the insertion pattern shown in execution_table steps 10 and 11.

Concept Snapshot

Collision Handling Using Chaining:
- Use a hash function to find bucket index.
- Each bucket holds a linked list of nodes.
- Insert new nodes at the head of the list.
- Handles collisions by chaining keys in the same bucket.
- Linked list nodes use Option<Box<Node>> for safe pointers.

Full Transcript

Collision handling using chaining means when two keys hash to the same bucket, we store them in a linked list at that bucket. We compute the hash index, then check the bucket. If empty, we create a new linked list with the node. If not, we insert the new node at the head of the existing list. This way, collisions are handled by chaining nodes together. The Rust code uses Option<Box<Node>> to represent linked list nodes safely. The execution table shows step-by-step insertion of keys 10, 20, 15, 25, and 30 into buckets 0, 1, and 2, building linked lists at each bucket. Variable tracker shows how bucket states change after each insertion. Key moments clarify why insertion is at the head, how collisions form chains, and why Option<Box<Node>> is used. Visual quiz questions test understanding of bucket states and insertion positions.

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