Implementing a Basic HashMap in Rust

This challenge asks you to implement a simplified HashMap data structure in Rust. HashMaps are fundamental for efficient key-value storage and retrieval, and understanding their underlying mechanics is crucial for any serious programmer. This exercise will solidify your understanding of Rust's ownership, borrowing, and hashing concepts.

Problem Description

You are to implement a basic HashMap struct in Rust. This HashMap should support the following operations:

• insert(key: K, value: V): Inserts a key-value pair into the HashMap. If the key already exists, the old value should be overwritten.
• get(key: &K): Retrieves the value associated with the given key. Returns Some(&V) if the key exists, and None otherwise.
• remove(key: &K): Removes the key-value pair associated with the given key. Returns Some(V) if the key existed and was removed, and None otherwise.
• len(): Returns the number of key-value pairs currently stored in the HashMap.

The HashMap should use a fixed-size array as its underlying storage (a "bucket array"). A simple modulo hashing function should be used to determine the bucket index for a given key. Handle collisions using separate chaining (each bucket will be a Vec of key-value pairs).

Key Requirements:

• The HashMap should be generic over key type K and value type V.
• The key type K must implement the Eq and Hash traits.
• The bucket array size should be a compile-time constant.
• Implement the Drop trait to ensure all allocated memory is freed when the HashMap goes out of scope.
• Handle potential panics gracefully (e.g., when the bucket array is full).

Expected Behavior:

The HashMap should behave as expected for standard insertion, retrieval, and deletion operations. It should correctly handle collisions and overwrite existing values when inserting duplicate keys. The len() function should accurately reflect the number of elements stored.

Edge Cases to Consider:

• Empty HashMap: Ensure all operations work correctly when the HashMap is empty.
• Duplicate Keys: Insertion of duplicate keys should overwrite the existing value.
• Key Not Found: get() and remove() should return None when the key is not present.
• Hashing Collisions: The separate chaining strategy should correctly handle multiple keys hashing to the same bucket.
• Memory Management: Ensure that memory is properly allocated and deallocated to prevent leaks.

Examples

Example 1:

Input:
let mut map: HashMap<String, i32> = HashMap::new();
map.insert("one".to_string(), 1);
map.insert("two".to_string(), 2);
map.insert("three".to_string(), 3);

let value1 = map.get("two");
let value2 = map.get("four");

Output:
value1: Some(&2)
value2: None

Explanation: The HashMap is initialized and populated with three key-value pairs. Retrieving the value associated with "two" returns Some(&2), while retrieving the value associated with "four" (which doesn't exist) returns None.

Example 2:

Input:
let mut map: HashMap<i32, String> = HashMap::new();
map.insert(1, "one".to_string());
map.insert(2, "two".to_string());
map.insert(1, "new_one".to_string()); // Overwrite existing key

let value1 = map.get(&1);
let value2 = map.get(&3);

Output:
value1: Some(&"new_one")
value2: None

Explanation: Inserting a duplicate key (1) overwrites the existing value. Retrieving the value associated with key 1 now returns Some(&"new_one".

Example 3:

Input:
let mut map: HashMap<String, i32> = HashMap::new();
map.insert("a".to_string(), 10);
let removed_value = map.remove("a");
let value = map.get("a");

Output:
removed_value: Some(10)
value: None

Explanation: Removing the key "a" returns the associated value (10), and subsequent attempts to retrieve the value associated with "a" return None.

Constraints

• Bucket Array Size: The bucket array size must be a compile-time constant, e.g., const BUCKET_SIZE: usize = 16;.
• Key Type: The key type K must implement Eq and Hash.
• Value Type: The value type V can be any type.
• No External Crates: You are not allowed to use external crates (e.g., std::collections::HashMap). You must implement the HashMap from scratch.
• Performance: While not a primary focus, strive for reasonable performance. Avoid unnecessary allocations or copies. The hash function should be reasonably efficient.

Notes

• Start by defining the HashMap struct and the bucket array.
• Implement the Hash trait for your key type if it's not already implemented. A simple identity hash function is sufficient for this exercise.
• Consider using a Vec to represent each bucket in the bucket array.
• Pay close attention to ownership and borrowing rules when inserting, retrieving, and removing elements.
• The Drop trait implementation is crucial for preventing memory leaks. Make sure to iterate through the bucket array and drop any remaining values.
• Test your implementation thoroughly with various scenarios, including edge cases.
• Remember to handle collisions using separate chaining.