Implement a Hash Map in Rust

This challenge requires you to build a fundamental data structure, a hash map, from scratch in Rust. Hash maps are incredibly useful for efficiently storing and retrieving data using key-value pairs. Implementing one will deepen your understanding of data structures, memory management, and Rust's ownership and borrowing system.

Problem Description

You need to implement a generic hash map data structure in Rust. This hash map should be able to store key-value pairs, where both keys and values can be of any type. You will be responsible for handling the internal storage, collision resolution, and the core operations of a hash map.

Key Requirements:

• Generic Types: The hash map should be generic over K (key type) and V (value type).
• HashMap<K, V> struct: You will define a struct named HashMap to encapsulate your hash map.
• new() function: A public associated function new() to create an empty HashMap.
• insert(key: K, value: V): A public method to insert a key-value pair.
  • If the key already exists, its corresponding value should be updated.
• get(&key: &K) -> Option<&V>: A public method to retrieve a reference to the value associated with a given key. Returns None if the key is not found.
• remove(&key: &K) -> Option<V>: A public method to remove a key-value pair and return its value. Returns None if the key is not found.
• Hashing: You need to implement a hashing mechanism for keys. Keys must implement the Hash and Eq traits (provided by Rust's standard library).
• Collision Resolution: Implement a strategy to handle hash collisions (e.g., separate chaining or open addressing).
• Capacity: The hash map should have an internal capacity that determines the number of "buckets" or slots available.
• Resizing (Optional but Recommended): For a more robust implementation, consider automatically resizing the hash map when it reaches a certain load factor to maintain performance.

Expected Behavior:

• Inserting new key-value pairs.
• Retrieving values by their keys.
• Updating values for existing keys.
• Removing key-value pairs.
• Handling cases where keys are not present during retrieval or removal.

Edge Cases to Consider:

• Empty hash map.
• Inserting duplicate keys.
• Retrieving or removing keys that don't exist.
• Hash collisions.
• Keys and values of different primitive types and custom types.

Examples

Example 1: Basic Insertion and Retrieval

let mut map = HashMap::new();
map.insert("apple", 1);
map.insert("banana", 2);

assert_eq!(map.get(&"apple"), Some(&1));
assert_eq!(map.get(&"banana"), Some(&2));
assert_eq!(map.get(&"cherry"), None);

Explanation: This demonstrates creating a hash map, inserting two key-value pairs, and then retrieving their associated values. It also shows that retrieving a non-existent key returns None.

Example 2: Updating a Value and Removal

let mut map = HashMap::new();
map.insert("apple", 1);
map.insert("apple", 10); // Update the value
assert_eq!(map.get(&"apple"), Some(&10));

let removed_value = map.remove(&"apple");
assert_eq!(removed_value, Some(10));
assert_eq!(map.get(&"apple"), None);

let removed_non_existent = map.remove(&"banana");
assert_eq!(removed_non_existent, None);

Explanation: This shows how inserting a key that already exists updates its value. It also demonstrates removing an existing key and then attempting to remove a non-existent key.

Example 3: Handling Collisions (Conceptual, actual collision depends on hash function and capacity)

Imagine a scenario where "cat" and "dog" hash to the same bucket.

let mut map: HashMap<&str, i32> = HashMap::new(); // Assume a small capacity for demonstration
map.insert("cat", 5);
map.insert("dog", 7); // This might hash to the same bucket as "cat"

assert_eq!(map.get(&"cat"), Some(&5));
assert_eq!(map.get(&"dog"), Some(&7));

Explanation: This example highlights the need for collision resolution. Even if two different keys hash to the same internal slot, both should be retrievable and manageable. Your implementation must correctly distinguish between them.

Constraints

• Keys must implement std::hash::Hash and std::cmp::Eq.
• The initial capacity of the hash map can be a reasonable fixed number (e.g., 16).
• For simplicity, you can assume integer keys for the hashing function if you are struggling with generic hashing initially, but a full generic implementation is the goal.
• Focus on correctness and clarity over extreme performance optimizations in the first iteration.

Notes

• You'll likely want to use a Vec or an array to represent your buckets internally.
• Consider how to handle the lifetime of borrowed keys when using get and remove.
• The standard library's std::collections::hash_map::DefaultHasher can be helpful for hashing, but you can also implement your own simple hashing function for educational purposes.
• Think about how to handle the ownership of keys and values when they are inserted, retrieved, and removed.
• For collision resolution, separate chaining (where each bucket holds a list or vector of key-value pairs) is often a good starting point.