Implement a hashmap without using any libraries.

To implement a hashmap without libraries, you'll need a data structure to store key-value pairs and a hashing function. A common approach is to use an array of linked lists (or other collision resolution structures like open addressing).

1. Hashing Function: This function takes a key and converts it into an array index. A good hash function distributes keys evenly across the array to minimize collisions.
2. Array (Buckets): An array where each element (bucket) can hold multiple key-value pairs. The size of this array is the capacity.
3. Collision Handling: When two different keys hash to the same index, a collision occurs. This can be handled using:
   • Separate Chaining: Each bucket points to a linked list (or another data structure) containing all key-value pairs that hash to that index. When adding or retrieving, you traverse the list.
   • Open Addressing: If a bucket is full, you probe for the next available bucket according to a specific strategy (e.g., linear probing, quadratic probing).
4. Load Factor and Rehashing: The load factor is the ratio of the number of elements to the capacity. When this exceeds a certain threshold (e.g., 0.75), the array is resized (rehashed) to a larger capacity, and all existing elements are re-inserted into the new, larger array to maintain performance.

Core Operations:

• put(key, value): Hash the key to find the bucket. If the key already exists, update its value. Otherwise, add a new key-value pair to the bucket (handling collisions). If the load factor is exceeded, rehash.
• get(key): Hash the key to find the bucket. Traverse the linked list (or probe) to find the key and return its value. Return null if not found.
• remove(key): Hash the key, find the bucket, and remove the key-value pair. Adjust size accordingly.
• containsKey(key): Similar to get, but returns a boolean indicating presence.