Collision Handling Using Chaining in DSA Rust - Build from Scratch

Collision Handling Using Chaining

📖 Scenario: Imagine you are building a simple phone book app. You want to store names and phone numbers efficiently. Sometimes, two names might hash to the same spot. To handle this, you will use chaining, which means storing multiple entries in a list at the same spot.

🎯 Goal: You will create a hash table using chaining to handle collisions. You will add entries and then print the hash table's contents showing how collisions are handled.

📋 What You'll Learn

Create a hash table with 5 buckets represented as a vector of vectors

Add a hash function to find the bucket index for a given name

Insert name and phone number pairs into the hash table using chaining

Print the hash table showing each bucket and its entries

💡 Why This Matters

🌍 Real World

Hash tables with chaining are used in many applications like databases, caches, and phone books to store and retrieve data efficiently even when collisions happen.

💼 Career

Understanding collision handling is important for software engineers working on data storage, search engines, and performance-critical applications.

1

Create the hash table buckets

Create a variable called hash_table as a Vec> with 5 empty buckets.

DSA Rust

# Your code here

Hint

Use vec![vec![]; 5] to create 5 empty buckets inside the main vector.

2

Add a hash function

Add a function called hash that takes a &str called key and returns a usize. The function should sum the bytes of key and return the sum modulo 5.

DSA Rust

fn main() {
    let mut hash_table: Vec> = vec![vec![]; 5];
}

// Your code here

Hint

Use key.bytes() to get bytes, sum them, then use modulo 5 to get bucket index.

3

Insert entries using chaining

Inside main, insert these entries into hash_table using the hash function: ("Alice", "123"), ("Bob", "456"), ("Charlie", "789"), ("David", "101"), ("Eve", "112"). Use hash(name) to find the bucket index and push the tuple into that bucket.

DSA Rust

fn main() {
    let mut hash_table: Vec> = vec![vec![]; 5];
    // Your code here
}

fn hash(key: &str) -> usize {
    key.bytes().sum::() % 5
}

Hint

Loop over entries, compute bucket index with hash(name), then push the tuple into hash_table[index].

4

Print the hash table contents

Add code inside main to print each bucket index and its entries in the format: Bucket 0: (Name, Number) -> (Name, Number) -> null. Use a for loop with enumerate() over hash_table. For each bucket, print all entries separated by -> and end with null.

DSA Rust

fn main() {
    let mut hash_table: Vec> = vec![vec![]; 5];
    let entries = vec![
        ("Alice", "123"),
        ("Bob", "456"),
        ("Charlie", "789"),
        ("David", "101"),
        ("Eve", "112"),
    ];
    for (name, number) in entries {
        let index = hash(name);
        hash_table[index].push((name.to_string(), number.to_string()));
    }
    for (i, bucket) in hash_table.iter().enumerate() {
        // Your code here
    }
}

fn hash(key: &str) -> usize {
    key.bytes().sum::() % 5
}

Hint

Use for (i, bucket) in hash_table.iter().enumerate() to loop buckets. Print each entry as (Name, Number) -> and end with null.

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