Implementing a Simple Hash Map in Rust

This challenge asks you to implement a basic hash map data structure in Rust. Hash maps are fundamental for efficient key-value storage and retrieval, and understanding their implementation provides valuable insights into data structures and algorithms. Your implementation should focus on core functionality and demonstrate a good understanding of Rust's ownership and borrowing rules.

Problem Description

You are to implement a generic hash map (SimpleHashMap) in Rust. This hash map should support the following operations:

• insert(key: K, value: V): Inserts a key-value pair into the hash map. If the key already exists, the old value should be overwritten with the new value.
• 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 in the hash map.
• is_empty(): Returns true if the hash map is empty, false otherwise.

The hash map should use a fixed-size array as its underlying storage (a "bucket array"). Handle collisions using separate chaining, where each bucket in the array holds a linked list of key-value pairs. You can use std::collections::LinkedList for the linked lists within each bucket.

Key Requirements:

• The hash map must be generic, accepting any key type K that implements the Eq and Hash traits, and any value type V.
• The hash map should handle collisions gracefully using separate chaining.
• The implementation should be memory-safe and adhere to Rust's ownership and borrowing rules.
• The bucket array size should be a compile-time constant defined as CAPACITY.

Expected Behavior:

The hash map should behave as expected for all supported operations. get should return the correct value for existing keys, insert should overwrite existing values, and remove should correctly remove key-value pairs. len and is_empty should accurately reflect the current state of the hash map.

Edge Cases to Consider:

• Empty hash map.
• Inserting duplicate keys.
• Retrieving a non-existent key.
• Removing a non-existent key.
• Hash collisions.
• Key types that produce the same hash value (though unlikely, it's good to handle).

Examples

Example 1:

Input:
let mut map = SimpleHashMap::new();
map.insert("apple", 1);
map.insert("banana", 2);
let value = map.get("apple");

Output:
Some(&1)
Explanation: The key "apple" exists in the map, and its value is 1.

Example 2:

Input:
let mut map = SimpleHashMap::new();
map.insert("apple", 1);
map.remove("apple");
let value = map.get("apple");

Output:
None
Explanation: The key "apple" was removed from the map, so get returns None.

Example 3: (Collision Scenario)

Input:
let mut map = SimpleHashMap::new();
map.insert("abc", 1);
map.insert("acb", 2); // Assuming "abc" and "acb" hash to the same bucket
let value1 = map.get("abc");
let value2 = map.get("acb");

Output:
Some(&1)
Some(&2)
Explanation: Both keys hash to the same bucket, but the linked list handles the collision correctly, allowing retrieval of both values.

Constraints

• CAPACITY must be a compile-time constant, and should be a reasonable size (e.g., 16, 32, 64).
• The key type K must implement the Eq and Hash traits.
• The value type V can be any type.
• The implementation should be reasonably efficient, avoiding unnecessary allocations or computations. While perfect performance isn't required, avoid obvious inefficiencies.
• The code should compile without warnings.

Notes

• You'll need to use the std::collections::hash_map::DefaultHasher to calculate hash values.
• Consider using a macro to simplify the hashing process.
• Remember to handle ownership and borrowing correctly to avoid common Rust errors.
• Focus on clarity and correctness over extreme optimization. A well-structured and understandable implementation is more valuable than a slightly faster but harder-to-read one.
• The LinkedList from std::collections is provided for collision resolution. You are not required to implement your own linked list.
• This is a simplified hash map implementation. Real-world hash maps often use more sophisticated techniques for resizing and collision resolution.