{x}
blog image

Design HashMap

Design a HashMap without using any built-in hash table libraries.

Implement the MyHashMap class:

  • MyHashMap() initializes the object with an empty map.
  • void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
  • int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
  • void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

 

Example 1:

Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]

 

Constraints:

  • 0 <= key, value <= 106
  • At most 104 calls will be made to put, get, and remove.

Solution Explanation for Design HashMap

This problem requires implementing a HashMap data structure without using built-in hash table libraries. The provided solutions utilize a simple array-based approach, leveraging the constraint that keys and values are within the range of 0 to 106.

Approach

The core idea is to use an array where the index represents the key and the value at that index represents the corresponding value in the HashMap. Since the keys are within a known range, we can directly use the key as the array index. This eliminates the need for complex hash functions and collision handling.

Data Structure: A simple array (or equivalent data structure in different languages) of size 1000001 is used to store the key-value pairs. The array is initialized with -1 to indicate an empty slot.

Operations:

  • put(key, value): This operation sets the element at index key to value. If the key already exists, its value is updated.
  • get(key): This operation returns the element at index key. If the element is -1, it means the key is not present, so -1 is returned.
  • remove(key): This operation sets the element at index key to -1, effectively removing the key-value pair.

Code Explanation (Python Example)

class MyHashMap:
    def __init__(self):
        self.data = [-1] * 1000001  # Initialize array with -1 (empty)
 
    def put(self, key: int, value: int) -> None:
        self.data[key] = value      # Direct assignment using key as index
 
    def get(self, key: int) -> int:
        return self.data[key]       # Return value at key index, or -1 if empty
 
    def remove(self, key: int) -> None:
        self.data[key] = -1         # Set value to -1 to indicate removal

The other language examples follow the same logic, adapting the array initialization and operations to their respective syntax.

Time and Space Complexity Analysis

  • Time Complexity:

    • put(key, value): O(1) - Direct array access is constant time.
    • get(key): O(1) - Direct array access is constant time.
    • remove(key): O(1) - Direct array access is constant time.

  • Space Complexity: O(106) - The space used is fixed and determined by the maximum possible key value (106 +1). This is considered constant space in the context of the problem, as it doesn't scale with the number of operations. However, note that this is a significant constant space requirement. If the key range were significantly larger or dynamic, this approach would become impractical.

Limitations

This solution is highly efficient for the given constraints. However, it's important to note its limitations:

  • Fixed Size: The array size is fixed, limiting the range of keys that can be stored.
  • Sparse Data: If only a small fraction of the key range is used, a significant amount of memory will be wasted.
  • Not Scalable: For a much larger or dynamic key range, a more sophisticated hash table implementation with collision handling would be necessary. This solution is not space-efficient for large or sparse key spaces.

This simple array-based implementation provides a clear and efficient solution within the specified constraints of the problem but is not a general-purpose HashMap implementation.