Hash Table Concept and Hash Functions in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Rust code using a hash map?

Consider the following Rust code that inserts key-value pairs into a hash map and then prints the value for key 2. What will it print?

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert(1, "apple");
    map.insert(2, "banana");
    map.insert(3, "cherry");
    println!("{}", map.get(&2).unwrap());
}

A apple

B banana

C cherry

D None

💡 Hint

Look at the key used in the get method and what value was inserted for that key.

The code inserts three key-value pairs. The key 2 is associated with "banana", so printing map.get(&2).unwrap() outputs "banana".

🧠 Conceptual

intermediate

What is the main purpose of a hash function in a hash table?

Choose the best description of what a hash function does in a hash table.

A It converts a key into an index to store or find the value quickly.

B It sorts the keys in alphabetical order.

C It encrypts the data stored in the hash table.

D It compresses the values to save memory.

💡 Hint

Think about how hash tables find values fast using keys.

A hash function takes a key and converts it into an index where the value is stored, enabling fast access.

❓ Predict Output

advanced

What error does this Rust code produce when inserting duplicate keys in a hash map?

Analyze the following Rust code. What will happen when it runs?

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("key", 10);
    map.insert("key", 20);
    println!("{}", map.get(&"key").unwrap());
}

A It prints 20

B It prints 10

C It causes a compile-time error

D It causes a runtime panic

💡 Hint

Think about what happens when you insert a value with a key that already exists.

In Rust's HashMap, inserting a value with an existing key replaces the old value. So the value for "key" becomes 20.

🔧 Debug

advanced

Why does this Rust code cause a compile-time error?

Look at this Rust code that tries to use a custom struct as a key in a hash map. Why does it fail to compile?

DSA Rust

use std::collections::HashMap;

#[derive(Debug)]
struct Point {
    x: i32,
    y: i32,
}

fn main() {
    let mut map = HashMap::new();
    let p = Point { x: 1, y: 2 };
    map.insert(p, "origin");
}

A The map variable is immutable and cannot be changed.

B The Point struct is missing a constructor.

C The insert method is called with wrong argument types.

D Point does not implement the Eq and Hash traits required for keys.

💡 Hint

HashMap keys must implement certain traits to be used as keys.

Rust requires keys in HashMap to implement Eq and Hash traits. The Point struct only derives Debug, so it cannot be used as a key.

🚀 Application

expert

How many items are in the hash map after this Rust code runs?

Given the following Rust code, how many key-value pairs does the hash map contain at the end?

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    for i in 0..5 {
        map.insert(i % 3, i);
    }
    println!("{}", map.len());
}

A 2

B 5

C 3

D 4

💡 Hint

Consider how keys repeat when using i % 3 and how insert replaces values.

Keys are 0,1,2 repeated. Each insert with the same key replaces the old value. So only keys 0,1,2 remain, total 3 items.

Practice

1. What is the main purpose of a hash function in a hash table?

easy

A. To sort the keys in ascending order

B. To convert a key into an index for storing values

C. To encrypt the data stored in the table

D. To count the number of elements in the table

Solution

1. Step 1: Understand the role of a hash function

   A hash function takes a key and converts it into a number that can be used as an index in the hash table.

2. Step 2: Identify the correct purpose

   This index helps to quickly find where the value related to the key is stored.

3. Final Answer:

   To convert a key into an index for storing values -> Option B

4. Quick Check:

   Hash function = key to index [OK]

Hint: Hash function maps keys to indexes fast [OK]

Common Mistakes:

• Thinking hash functions sort keys
• Confusing hashing with encryption
• Believing hash functions count elements

2. Which of the following is the correct way to declare a hash map in Rust?

easy

A. let mut map = HashMap::new();

B. let map = new HashMap();

C. HashMap map = new HashMap();

D. var map = HashMap();

Solution

1. Step 1: Recall Rust syntax for hash maps

   In Rust, hash maps are created using HashMap::new() and usually declared mutable with let mut.

2. Step 2: Check each option

   let mut map = HashMap::new(); uses correct Rust syntax. Options A, B, and C use syntax from other languages or incorrect Rust syntax.

3. Final Answer:

   let mut map = HashMap::new(); -> Option A

4. Quick Check:

   Rust hash map creation = let mut map = HashMap::new() [OK]

Hint: Rust uses HashMap::new() with let mut [OK]

Common Mistakes:

• Using syntax from other languages like Java or JavaScript
• Forgetting to make the map mutable
• Missing the HashMap:: prefix

3. What will be the output of the following Rust code?

use std::collections::HashMap;

fn main() {
    let mut map = HashMap::new();
    map.insert("apple", 3);
    map.insert("banana", 2);
    map.insert("apple", 5);
    println!("{:?}", map.get("apple"));
}

medium

A. Error: duplicate key

B. Some(3)

C. None

D. Some(5)

Solution

1. Step 1: Understand insert behavior in HashMap

   In Rust's HashMap, inserting a value with an existing key replaces the old value.

2. Step 2: Trace the inserts and get

   First insert: "apple" -> 3, second insert: "banana" -> 2, third insert: "apple" -> 5 replaces 3. So map.get("apple") returns Some(5).

3. Final Answer:

   Some(5) -> Option D

4. Quick Check:

   Last insert replaces value = Some(5) [OK]

Hint: Last insert with same key overwrites value [OK]

Common Mistakes:

• Assuming duplicate keys cause error
• Thinking old value remains after insert
• Expecting None for existing key

4. Identify the error in this Rust code snippet using a hash map:

use std::collections::HashMap;

fn main() {
    let map = HashMap::new();
    map.insert("key", 10);
    println!("{:?}", map.get("key"));
}

medium

A. HashMap is not imported

B. get method does not exist

C. map is immutable but insert is called

D. Missing semicolon after insert

Solution

1. Step 1: Check mutability of map

   The map is declared with let (immutable) but insert tries to modify it.

2. Step 2: Identify the error cause

   In Rust, to modify a HashMap, it must be declared mutable with let mut.

3. Final Answer:

   map is immutable but insert is called -> Option C

4. Quick Check:

   Insert needs mutable map [OK]

Hint: Use let mut for hash maps you modify [OK]

Common Mistakes:

• Forgetting to import HashMap
• Assuming get method is missing
• Thinking semicolon is missing

5. You want to create a hash function for strings that sums the ASCII values of characters and then takes modulo with table size. Which of these Rust functions correctly implements this?

hard

A. fn hash(key: &str, size: usize) -> usize { key.bytes().map(|b| b as usize).sum::<usize>() % size }

B. fn hash(key: &str, size: usize) -> usize { key.len() % size }

C. fn hash(key: &str, size: usize) -> usize { key.chars().count() % size }

D. fn hash(key: &str, size: usize) -> usize { key.as_bytes().len() % size }

Solution

1. Step 1: Understand the required hash function

   The function must sum ASCII values of all characters and then take modulo with size.

2. Step 2: Analyze each option

   fn hash(key: &str, size: usize) -> usize { key.bytes().map(|b| b as usize).sum::<usize>() % size } sums bytes (ASCII values) and mods by size correctly. Options A, B, and D only use length or count, not sum of ASCII values.

3. Final Answer:

   fn hash(key: &str, size: usize) -> usize { key.bytes().map(|b| b as usize).sum::<usize>() % size } -> Option A

4. Quick Check:

   Sum ASCII bytes then mod size = fn hash(key: &str, size: usize) -> usize { key.bytes().map(|b| b as usize).sum::<usize>() % size } [OK]

Hint: Sum bytes, then modulo table size for hash [OK]

Common Mistakes:

• Using length instead of sum of ASCII values
• Using chars count instead of bytes
• Forgetting to modulo by table size