Solution: Design HashMap

Statement

Design a HashMap data structure that supports the following operations:

• Constructor(): Initializes the hash map object with an empty map to store the key-value pairs.

• Put(key, value): Inserts a key-value pair into the hash map. If the specified key is already present in the hash map, the associated value is updated. Otherwise, the key-value pair is added to the hash map.

• Get(key): Returns the value associated with the specified key if the key exists in the hash map. Otherwise, it returns $-1$, indicating the absence of a mapping for the key.

• Remove(key): Removes the entry for the specified key from the hash map, effectively removing both the key and its associated value. This elimination only takes place when the key exists in the hash map.

Note: Your implementation should not utilize the built-in hash table libraries.

Constraints:

• $0$ $\le$ key $\le$ $10^6$
• $0$ $\le$ value $\le$ $10^6$
• At most, $10^4$ calls can be made to the Put, Get, and Remove functions.

Solution

A hash map is a fundamental data structure found in various programming languages. Its key feature is facilitating fast access to a value associated with a given key. Designing an efficient hash map involves addressing two main challenges:

1. Hash function design: The hash function serves to map a key to a location in the storage space. A good hash function ensures that keys are evenly distributed across the storage space, preventing the clustering of keys in certain locations. This even distribution helps maintain efficient access to stored values.

2. Collision handling: Despite efforts to evenly distribute keys, collisions—where two distinct keys map to the same storage location—are inevitable due to the finite nature of the storage space compared to the potentially infinite key space. Effective collision-handling strategies are crucial to ensure data integrity and efficient retrieval. To deal with collisions, we can use methods like chaining, where we link multiple values together at that location, or open addressing, where we find another empty location for the key.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

The first step is to design a hash function using the modulo operator, particularly suitable for integer-type keys. The modulo operator, denoted by $\%$, is a mathematical operation that returns the remainder of dividing one number by another. When selecting a modulo base, it’s advisable to choose a prime number. This is because choosing a prime number as the modulo base helps minimize collisions. Since prime numbers offer better distribution of hash codes, reducing the likelihood of collisions (where two different keys hash to the same value).

Here’s the implementation of a hash function using a prime number, $2069$, as the modulo base. This particular prime number is likely chosen because it is relatively large, offering a wide range of possible hash codes and reducing the chance of collisions.