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
.For example:
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 <= 10^6
10^4
calls will be made to put
, get
, and remove
.When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:
Imagine a simple phone book where you want to store names and phone numbers. The most basic way to do this is to keep a simple list of name-number pairs. To find a number, we just check each pair one by one until we find the right name.
Here's how the algorithm would work step-by-step:
class MyHashMap:
def __init__(self):
self.key_value_pairs = []
def put(self, key: int, value: int) -> None:
# Iterate through existing pairs to check for key
for index, pair in enumerate(self.key_value_pairs):
if pair[0] == key:
self.key_value_pairs[index] = (key, value)
return
self.key_value_pairs.append((key, value))
def get(self, key: int) -> int:
# Iterate through pairs to find matching key.
for pair in self.key_value_pairs:
if pair[0] == key:
return pair[1]
return -1
def remove(self, key: int) -> None:
# Iterate to find the key to be removed
for index, pair in enumerate(self.key_value_pairs):
if pair[0] == key:
del self.key_value_pairs[index]
# Exit after removing the pair.
return
Imagine a set of labeled bins where we can store values. Instead of searching every bin to find a value, we use a clever trick to quickly locate the right bin based on the label. This avoids a lot of unnecessary searching and makes finding and storing things much faster.
Here's how the algorithm would work step-by-step:
class MyHashMap:
def __init__(self):
self.capacity = 1000 #Initial size
self.data = [[] for _ in range(self.capacity)]
def put(self, key: int, value: int) -> None:
index = key % self.capacity
# Handle collisions by adding new k-v pairs to the bucket
for i, (current_key, _) in enumerate(self.data[index]):
if current_key == key:
self.data[index][i] = (key, value)
return
self.data[index].append((key, value))
def get(self, key: int) -> int:
index = key % self.capacity
# Search the bucket for the key and return the value
for current_key, current_value in self.data[index]:
if current_key == key:
return current_value
return -1
def remove(self, key: int) -> None:
index = key % self.capacity
#Locate key within bucket to remove if present
for i, (current_key, _) in enumerate(self.data[index]):
if current_key == key:
#This is how we remove from the list when found
del self.data[index][i]
return
Case | How to Handle |
---|---|
Null or undefined key input | Reject null keys and throw an IllegalArgumentException, or use a sentinel value if null keys are allowed. |
Integer key overflows when hashing | Use a bitwise AND operation with the size of the underlying array during hash calculation to prevent index out of bounds. |
Extremely high collision rate in the hash function, leading to O(n) lookup time in buckets | Implement separate chaining with balanced trees or probing with rehashing to maintain O(1) average case lookup. |
Deleting a non-existent key | The delete operation should gracefully handle non-existent keys without errors, potentially doing nothing or returning a flag indicating failure. |
Inserting a large number of key-value pairs causing the underlying array to reach its maximum capacity | Dynamically resize the underlying array (e.g., doubling) when the load factor exceeds a threshold, rehashing all existing keys. |
Using mutable objects as keys that change after insertion, corrupting the hash and lookup | The hashmap should either copy the object, create an immutable wrapper, or prohibit mutable objects as keys. |
Negative integer keys | Ensure the hash function handles negative integers correctly, avoiding negative indices or bitwise shifting issues. |
Zero key | Treat zero as a valid key, hashing it appropriately just like any other integer key. |