Hash Table Concept and Hash Functions in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new empty hash map in Rust.

DSA Rust

let mut map = std::collections::HashMap::[1]();

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

Aremove

Binsert

Cnew

Dclear

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'insert' instead of 'new' to create the map.

Trying to remove or clear before creating the map.

The method 'new' creates an empty HashMap in Rust.

2fill in blank

medium

Complete the code to insert a key-value pair into the hash map.

DSA Rust

map.[1]("apple", 3);

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

Acontains_key

Bget

Cremove

Dinsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'get' which only reads values.

Using 'remove' which deletes entries.

The 'insert' method adds a key-value pair to the hash map.

3fill in blank

hard

Fix the error in the code to check if a key exists in the hash map.

DSA Rust

if map.[1]("banana") {
    println!("Found banana");
}

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

Acontains_key

Binsert

Cget_mut

Dremove

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'insert' which adds keys instead of checking.

Using 'get_mut' which returns a mutable reference.

The 'contains_key' method returns true if the key exists in the map.

4fill in blank

hard

Fill both blanks to compute a simple hash value for a string key.

DSA Rust

fn simple_hash(key: &str) -> usize {
    key.bytes().[1](0, |acc, b| acc [2] b as usize)
}

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

Afold

B+

C*

Dmap

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'map' instead of 'fold' which does not reduce.

Using '*' which multiplies and can overflow easily.

The 'fold' method accumulates values, and '+' sums the bytes for a simple hash.

5fill in blank

hard

Fill all three blanks to create a hash map from a list of keys with their lengths as values.

DSA Rust

let keys = vec!["cat", "dog", "bird"];
let map: std::collections::HashMap<_, _> = keys.into_iter().map(|[1]| ([2], [3])).collect();

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

Akey

Ckey.len()

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'value' which is undefined here.

Using 'key' inconsistently in the tuple.

We name the iterator variable 'key', then map it to a tuple of (key, key.len()) to store lengths.

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