Design HashMap
Design a HashMap without using any built-in hash table libraries. The HashMap should have the following functions: put(key: number, value: number): void, get(key: number): number, remove(key: number): void. The HashMap should be able to store and retrieve values based on the given key.
Constraints:
- 1 <= key <= 10^6
- 0 <= value <= 10^6
- At most 10^6 operations will be performed
Examples:
Input: ["put", "put", "get", "get", "remove", "get"] [[1, 1], [2, 2], [1], [3], [2], [2]]
Output: [null, null, 1, -1, null, -1]
Explanation: The HashMap is initialized. The put function is used to store the key-value pairs (1, 1) and (2, 2). The get function is used to retrieve the values for keys 1 and 3. The remove function is used to remove the key-value pair (2, 2). Finally, the get function is used again to retrieve the value for key 2, which returns -1 because the key has been removed.
Solutions
Separate Chaining
The solution uses separate chaining to handle collisions. Each bucket is an array of key-value pairs. The put function checks if the key already exists in the bucket and updates the value if it does. If the key does not exist, it adds a new key-value pair to the bucket. The get function checks if the key exists in the bucket and returns the value if it does. If the key does not exist, it returns -1. The remove function checks if the key exists in the bucket and removes the key-value pair if it does.
class MyHashMap:
def __init__(self):
self.size = 1000
self.buckets = [[] for _ in range(self.size)]
def put(self, key:
int, value:
int) -> None:
index = key % self.size
for i, (k, v) in enumerate(self.buckets[index]):
if k == key:
self.buckets[index][i] = (key, value)
return
self.buckets[index].append((key, value))
def get(self, key:
int) -> int:
index = key % self.size
for k, v in self.buckets[index]:
if k == key:
return v
return -1
def remove(self, key:
int) -> None:
index = key % self.size
for i, (k, v) in enumerate(self.buckets[index]):
if k == key:
self.buckets[index].pop(i)
returnFollow-up:
How would you optimize the solution for a large number of operations?
