706. Design HashMap
Model: qwen2.5-coder:14b
Topics: Hash Table,Design
FAANG asked: 1
Acceptance rate: 64.1%
Problem Breakdown
We need to design a simple HashMap without using any built-in hash table libraries. The MyHashMap class should support three operations: put, get, and remove.
-
Inputs:
- For
put(int key, int value): A key-value pair. - For
get(int key)andremove(key): A single key.
- For
-
Outputs:
- For
putandremove: No output (void). - For
get: An integer value or-1if the key is not found.
- For
-
Implicit Constraints:
- Keys and values are non-negative integers.
- The maximum number of operations (
put,get,remove) is 10,000.
Intuition
A brute-force approach would be to use a list or array where each element represents a key-value pair. However, this approach would have a time complexity of O(n) for all operations due to the need to search through the entire list.
The key insight is to use an array (or list) of fixed size and employ a simple hash function to map keys to indices in this array. This allows us to achieve average O(1) time complexity for put, get, and remove operations.
Approach
We will implement the MyHashMap class using an array where each index corresponds to a key. To handle collisions (multiple keys hashing to the same index), we’ll use chaining with linked lists. Each element in the array will be a list that stores all key-value pairs that hash to the same index.
- Initialization: Create an array of size
10^6 + 1(to cover the range of possible keys) where each element is initialized as an empty list. - Put Operation:
- Compute the hash index using the modulo operation (
key % len(self.map)). - Check if the key already exists in the linked list at that index. If it does, update its value. Otherwise, append the new key-value pair to the list.
- Compute the hash index using the modulo operation (
- Get Operation:
- Compute the hash index.
- Traverse the linked list at that index to find the key. If found, return its value; otherwise, return
-1.
- Remove Operation:
- Compute the hash index.
- Traverse the linked list at that index to find and remove the key-value pair if it exists.
Complexity Analysis
-
Time Complexity:
put,get, andremoveoperations have an average time complexity of O(1) due to the use of a hash function. In the worst case (all keys hashing to the same index), these operations can degrade to O(n).
-
Space Complexity:
- The space complexity is O(m + n), where m is the size of the array and n is the number of key-value pairs stored in the map.
Solution
class MyHashMap:
def __init__(self):
# Initialize an array of size 10^6 + 1 with empty lists for chaining
self.map = [[] for _ in range(10**6 + 1)]
def put(self, key: int, value: int) -> None:
# Compute the hash index
idx = key % len(self.map)
# Check if the key already exists and update its value
for i, (k, v) in enumerate(self.map[idx]):
if k == key:
self.map[idx][i] = (key, value)
return
# If the key does not exist, append the new key-value pair
self.map[idx].append((key, value))
def get(self, key: int) -> int:
# Compute the hash index
idx = key % len(self.map)
# Traverse the linked list to find the key and return its value
for k, v in self.map[idx]:
if k == key:
return v
# If the key is not found, return -1
return -1
def remove(self, key: int) -> None:
# Compute the hash index
idx = key % len(self.map)
# Traverse the linked list to find and remove the key-value pair
for i, (k, v) in enumerate(self.map[idx]):
if k == key:
del self.map[idx][i]
return
Edge Cases Handled
- Key Already Exists: The
putmethod updates the value if the key already exists. - Key Not Found: The
getandremovemethods handle keys that are not present in the map by returning-1or doing nothing, respectively. - Empty Map: All operations work correctly even when the map is initially empty.