Implementing a Basic HashMap in Rust

This challenge will test your understanding of fundamental data structures and Rust's ownership and borrowing system. You will implement a simplified HashMap data structure from scratch. This exercise is crucial for grasping how key-value stores work internally and how to manage memory and data efficiently in Rust.

Problem Description

Your task is to create a generic HashMap<K, V> struct in Rust. This HashMap should store key-value pairs, where K represents the key type and V represents the value type. You need to implement the core functionalities of a hash map: insert, get, and remove.

Key Requirements:

• Generic Types: The HashMap should be generic over key type K and value type V.
• Hashing: Keys must be hashable. You should leverage Rust's std::hash::Hash and std::cmp::Eq traits for keys.
• Bucket-based Storage: Internally, the HashMap should use a vector of buckets (e.g., Vec<Vec<(K, V)>>) to handle collisions using separate chaining.
• insert(key: K, value: V): Inserts a key-value pair into the map. If the key already exists, update the value and return the old value.
• get(key: &K) -> Option<&V>: Returns an immutable reference to the value associated with the key. Returns None if the key is not found.
• remove(key: &K) -> Option<V>: Removes the key-value pair associated with the key and returns the removed value. Returns None if the key is not found.
• Handling Collisions: Implement a strategy for handling hash collisions, such as separate chaining (storing entries with the same hash in a list within a bucket).
• Initial Capacity: Allow for an initial capacity when creating the HashMap.

Expected Behavior:

• When inserting a new key, it should be added to the appropriate bucket.
• When inserting a key that already exists, its value should be updated, and the old value returned.
• When getting a value for an existing key, a reference to the value should be returned.
• When getting a value for a non-existent key, None should be returned.
• When removing an existing key, the key-value pair should be removed, and the value returned.
• When removing a non-existent key, None should be returned.

Edge Cases to Consider:

• Empty HashMap.
• Inserting duplicate keys.
• Getting/removing from an empty HashMap.
• Keys that hash to the same bucket.
• Using different types for keys and values.

Examples

Example 1: Basic Insert and Get

// Assume HashMap is implemented
let mut map: HashMap<String, i32> = HashMap::with_capacity(10);

map.insert("apple".to_string(), 5);
map.insert("banana".to_string(), 10);

// Expected: Some(&5)
println!("{:?}", map.get(&"apple".to_string()));
// Expected: Some(&10)
println!("{:?}", map.get(&"banana".to_string()));
// Expected: None
println!("{:?}", map.get(&"cherry".to_string()));

Output:

Some(5)
Some(10)
None

Explanation: The keys "apple" and "banana" are inserted with their respective values. get successfully retrieves the values for existing keys and returns None for a non-existent key.

Example 2: Updating Values and Removing

// Assume HashMap is implemented
let mut map: HashMap<String, i32> = HashMap::with_capacity(10);

map.insert("apple".to_string(), 5);
// Expected: Some(5)
println!("{:?}", map.insert("apple".to_string(), 7));
// Expected: Some(&7)
println!("{:?}", map.get(&"apple".to_string()));

// Expected: Some(7)
println!("{:?}", map.remove(&"apple".to_string()));
// Expected: None
println!("{:?}", map.get(&"apple".to_string()));
// Expected: None
println!("{:?}", map.remove(&"banana".to_string()));

Output:

Some(5)
Some(7)
Some(7)
None
None

Explanation: Inserting "apple" again updates its value from 5 to 7, returning the old value (5). After removing "apple", get and remove return None. Attempting to remove a non-existent key also returns None.

Example 3: Handling Collisions (Conceptual)

Imagine a simplified hash function that maps "cat" and "dog" to the same bucket index.

// Assume HashMap is implemented with a small capacity and a colliding hash function for demonstration
let mut map: HashMap<&str, i32> = HashMap::with_capacity(2); // Small capacity to increase collision likelihood

// Let's assume "cat" and "dog" hash to the same bucket index
map.insert("cat", 1);
map.insert("dog", 2);

// Expected: Some(&1)
println!("{:?}", map.get(&"cat"));
// Expected: Some(&2)
println!("{:?}", map.get(&"dog"));

// Expected: Some(2)
println!("{:?}", map.remove(&"dog"));
// Expected: Some(&1)
println!("{:?}", map.get(&"cat"));
// Expected: None
println!("{:?}", map.get(&"dog"));

Output:

Some(1)
Some(2)
Some(2)
Some(1)
None

Explanation: Even though "cat" and "dog" might hash to the same bucket, the separate chaining mechanism allows both to be stored and retrieved correctly. Removing one does not affect the other.

Constraints

• The key type K must implement std::hash::Hash and std::cmp::Eq.
• The value type V can be any type.
• The HashMap should have a reasonable number of buckets (e.g., start with a default size or a user-specified capacity). You do not need to implement resizing for this basic version.
• The insert, get, and remove operations should aim for an average time complexity of O(1), assuming a good hash function and a low load factor. In the worst-case scenario (many collisions), it can degrade to O(n).

Notes

• To calculate the bucket index for a given key, you'll need to use the Hash trait to get a hash value and then use the modulo operator (%) with the number of buckets.
• Consider how you will store the key-value pairs within each bucket to handle multiple entries mapping to the same index. A Vec<(K, V)> for each bucket is a common approach.
• Pay close attention to Rust's ownership and borrowing rules when implementing get and remove. You'll need to return references and handle ownership transfers appropriately.
• You are not required to implement Debug or Clone for the HashMap itself, but you will likely need Debug on your internal data structures if you want to print them for debugging.
• Feel free to use std::collections::hash_map::DefaultHasher for generating hash values.