Design HashMap
EasyPrompt
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 thekeyalready exists in the map, update the correspondingvalue.int get(int key)returns thevalueto which the specifiedkeyis mapped, or-1if this map contains no mapping for thekey.void remove(key)removes thekeyand its correspondingvalueif the map contains the mapping for thekey.
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
104calls will be made toput,get, andremove.
Approaches
3 approaches with complexity analysis and trade-offs.
This is a straightforward but inefficient approach. We can use a dynamic array (like ArrayList in Java) to store the key-value pairs. For each operation (put, get, remove), we would need to iterate through the list to find the relevant key.
Algorithm
- Initialize an empty list,
map, to store(key, value)pairs. put(key, value):- Iterate through
map. - If an entry with
entry.key == keyexists, updateentry.value = valueand return. - If not found, add a new pair
(key, value)tomap.
- Iterate through
get(key):- Iterate through
map. - If an entry with
entry.key == keyexists, returnentry.value. - If the loop finishes, return
-1.
- Iterate through
remove(key):- Iterate through
mapwith an index. - If an entry with
entry.key == keyis found at indexi, remove the element at indexiand return.
- Iterate through
Walkthrough
We maintain a list of custom objects or pairs, where each object holds a key and its corresponding value.
- For the
put(key, value)operation, we first scan the entire list. If we find an entry with the same key, we update its value. If we traverse the whole list without finding the key, we append a new(key, value)pair to the end of the list. - For the
get(key)operation, we perform a linear scan of the list. If we find an entry with the matching key, we return its value. If the key is not found after checking all entries, we return-1. - For the
remove(key)operation, we again scan the list. If we find the key, we remove that entry from the list. This might involve shifting subsequent elements if anArrayListis used.
import java.util.ArrayList;import java.util.List; class MyHashMap { private List<int[]> map; public MyHashMap() { map = new ArrayList<>(); } public void put(int key, int value) { for (int[] pair : map) { if (pair[0] == key) { pair[1] = value; return; } } map.add(new int[]{key, value}); } public int get(int key) { for (int[] pair : map) { if (pair[0] == key) { return pair[1]; } } return -1; } public void remove(int key) { for (int i = 0; i < map.size(); i++) { if (map.get(i)[0] == key) { map.remove(i); return; } } }}Complexity
Time
O(k) for all operations (`put`, `get`, `remove`), where `k` is the number of keys in the HashMap. Each operation requires a linear scan of the list.
Space
O(k), where `k` is the number of keys stored in the HashMap. We only store the key-value pairs that are actually inserted.
Trade-offs
Pros
Simple to implement.
Space-efficient, as it only uses space for the elements inserted.
Cons
Very slow. The time complexity for all operations is linear, which is not acceptable for a HashMap implementation, especially with a large number of entries. It will likely result in a 'Time Limit Exceeded' error for larger test cases.
Given that the keys are non-negative integers within a known range (0 to 10^6), we can use a simple array as a direct address table. The key itself serves as the index into the array. This approach trades significant space for constant-time operations.
Algorithm
- Initialize an integer array
dataof size10^6 + 1. - Fill the entire
dataarray with-1to act as a sentinel value indicating an empty slot. put(key, value): Setdata[key] = value.get(key): Returndata[key].remove(key): Setdata[key] = -1.
Walkthrough
We declare an integer array, let's call it data, with a size large enough to accommodate the maximum possible key value. Since keys are up to 10^6, the array size will be 10^6 + 1.
We need a way to indicate whether a key is present or not. Since the problem states that get should return -1 for a non-existent key and values are non-negative (0 <= value <= 10^6), we can use -1 as a sentinel value. We initialize the entire array with -1.
put(key, value): This operation becomes a simple array assignment:data[key] = value.get(key): This is a direct lookup:return data[key]. If the key was never inserted, the value will be the initial-1.remove(key): To remove a key, we simply reset the value at that index back to our sentinel value:data[key] = -1.
import java.util.Arrays; class MyHashMap { int[] data; public MyHashMap() { data = new int[1000001]; // Initialize all values to -1 to indicate that no key is present. Arrays.fill(data, -1); } public void put(int key, int value) { data[key] = value; } public int get(int key) { return data[key]; } public void remove(int key) { data[key] = -1; }}Complexity
Time
O(1) for `put`, `get`, and `remove`. All operations are constant time as they involve direct array access.
Space
O(M), where `M` is the maximum possible value of a key (`10^6 + 1`). This approach pre-allocates memory for all possible keys, regardless of how many are actually used.
Trade-offs
Pros
Extremely fast with
O(1)time complexity for all operations.Very simple to implement.
Cons
Highly inefficient in terms of space. It allocates a very large array, which can be wasteful if the number of actual keys is small compared to the range of possible keys. In this problem, we have at most
10^4keys but a range of10^6, so we use100times more space than necessary.
This is the classic and most practical approach to implementing a HashMap. It combines an array with linked lists to handle collisions efficiently, balancing the trade-offs between time and space. This method is known as separate chaining.
Algorithm
- Define a
ListNodeclass to storekey,value, and anextpointer. - Initialize an array of
ListNodecalledbucketsof a chosen prime size (e.g.,10007). - Define a hash function,
hash(key) = key % SIZE. put(key, value):- Get
index = hash(key). - Traverse the linked list at
buckets[index]. - If a node with the same key is found, update its value and return.
- Otherwise, create a new
ListNode(key, value)and add it to the front of the list atbuckets[index].
- Get
get(key):- Get
index = hash(key). - Traverse the linked list at
buckets[index]. - If a node with the same key is found, return its value.
- If the list is fully traversed, return
-1.
- Get
remove(key):- Get
index = hash(key). - Find the node with the given key in the list at
buckets[index], keeping track of the previous node. - Once found, update the
nextpointer of the previous node to skip the current node. Handle the case where the node to be removed is the head of the list separately.
- Get
Walkthrough
The core idea is to use a hash function to map a key to an index in an array of 'buckets'. Since multiple keys can map to the same index (a 'collision'), each bucket stores a data structure to hold all the key-value pairs that hash to it. A linked list is a common choice for this.
- We start by creating an array of a fixed size. This size should ideally be a prime number to help distribute keys more evenly. A size of around
10000is reasonable given the constraints. Let's choose10007. This array will store the heads of linked lists. - The hash function will be
key % array_size. - For
put(key, value): Calculate the bucket index, then traverse the linked list at that index. If the key exists, update the value. Otherwise, add a new node to the front of the list. - For
get(key): Calculate the bucket index, then traverse the list to find the key and return its value. If not found, return-1. - For
remove(key): Calculate the bucket index, find the node in the list, and remove it by adjusting thenextpointers.
class MyHashMap { class ListNode { int key, val; ListNode next; ListNode(int key, int val) { this.key = key; this.val = val; } } final int SIZE = 10007; // A prime number ListNode[] buckets; public MyHashMap() { buckets = new ListNode[SIZE]; } private int hash(int key) { return key % SIZE; } public void put(int key, int value) { int index = hash(key); ListNode head = buckets[index]; ListNode current = head; while (current != null) { if (current.key == key) { current.val = value; return; } current = current.next; } ListNode newNode = new ListNode(key, value); newNode.next = head; buckets[index] = newNode; } public int get(int key) { int index = hash(key); ListNode current = buckets[index]; while (current != null) { if (current.key == key) { return current.val; } current = current.next; } return -1; } public void remove(int key) { int index = hash(key); ListNode head = buckets[index]; if (head == null) return; if (head.key == key) { buckets[index] = head.next; return; } ListNode prev = head; ListNode current = head.next; while (current != null) { if (current.key == key) { prev.next = current.next; return; } prev = current; current = current.next; } }}Complexity
Time
Average case is `O(1)` for all operations, assuming a good hash function and a reasonable load factor. The load factor `λ` is `k/N` (number of keys / number of buckets). The complexity is more precisely `O(1 + λ)`. In the worst case, where all keys hash to the same bucket, the complexity degrades to `O(k)`.
Space
O(N + k), where `N` is the number of buckets and `k` is the number of keys stored. This is efficient as it scales with the number of items stored, plus a fixed overhead for the bucket array.
Trade-offs
Pros
Provides a good balance between time and space complexity.
Average
O(1)performance makes it very fast for typical use cases.Space usage is proportional to the number of elements, making it much more efficient than direct addressing for sparse key sets.
Cons
More complex to implement than the other two approaches.
Performance can degrade to
O(k)in the worst-case scenario of many hash collisions, wherekis the number of keys.
Solutions
Solution
class MyHashMap { private int [] data = new int [ 1000001 ]; public MyHashMap () { Arrays . fill ( data , - 1 ); } public void put ( int key , int value ) { data [ key ] = value ; } public int get ( int key ) { return data [ key ]; } public void remove ( int key ) { data [ key ] = - 1 ; } } /** * Your MyHashMap object will be instantiated and called as such: * MyHashMap obj = new MyHashMap(); * obj.put(key,value); * int param_2 = obj.get(key); * obj.remove(key); */class MyHashMap { public: int data [ 1000001 ]; MyHashMap () { memset ( data , - 1 , sizeof data ); } void put ( int key , int value ) { data [ key ] = value ; } int get ( int key ) { return data [ key ]; } void remove ( int key ) { data [ key ] = - 1 ; } }; /** * Your MyHashMap object will be instantiated and called as such: * MyHashMap* obj = new MyHashMap(); * obj->put(key,value); * int param_2 = obj->get(key); * obj->remove(key); */class MyHashMap : def __init__ ( self ): self . data = [ - 1 ] * 1000001 def put ( self , key : int , value : int ) -> None : self . data [ key ] = value def get ( self , key : int ) -> int : return self . data [ key ] def remove ( self , key : int ) -> None : self . data [ key ] = - 1 # Your MyHashMap object will be instantiated and called as such: # obj = MyHashMap() # obj.put(key,value) # param_2 = obj.get(key) # obj.remove(key) ############# class MyHashMap : # hash to bucket def __init__ ( self ): """ Initialize your data structure here. """ self . size = 1000 self . buckets = [[] for _ in range ( self . size )] def _hash ( self , key : int ) -> int : """ Generate a hash for a given key. """ return key % self . size def put ( self , key : int , value : int ) -> None : """ Value will always be non-negative. """ hash_key = self . _hash ( key ) for i , ( k , v ) in enumerate ( self . buckets [ hash_key ]): if k == key : self . buckets [ hash_key ][ i ] = ( key , value ) return self . buckets [ hash_key ]. append (( key , value )) def get ( self , key : int ) -> int : """ Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key. """ hash_key = self . _hash ( key ) for k , v in self . buckets [ hash_key ]: if k == key : return v return - 1 def remove ( self , key : int ) -> None : """ Removes the mapping of the specified value key if this map contains a mapping for the key. """ hash_key = self . _hash ( key ) for i , ( k , v ) in enumerate ( self . buckets [ hash_key ]): if k == key : del self . buckets [ hash_key ][ i ] return ############### class MyHashMap : # open addressing with linear probing def __init__ ( self ): self . capacity = 10000 self . data = [ None ] * self . capacity self . DELETED = ( None , None ) # Marker for deleted entries def _hash ( self , key ): return key % self . capacity def put ( self , key : int , value : int ) -> None : idx = self . _hash ( key ) while self . data [ idx ] not in ( None , self . DELETED , key ): idx = ( idx + 1 ) % self . capacity self . data [ idx ] = ( key , value ) def get ( self , key : int ) -> int : idx , found_key = self . _find ( key ) if found_key : return self . data [ idx ][ 1 ] return - 1 def remove ( self , key : int ) -> None : idx , found_key = self . _find ( key ) if found_key : self . data [ idx ] = self . DELETED def _find ( self , key ): original_idx = idx = self . _hash ( key ) while self . data [ idx ] is not None : if self . data [ idx ] != self . DELETED and self . data [ idx ][ 0 ] == key : return idx , True idx = ( idx + 1 ) % self . capacity if idx == original_idx : # Came full circle break return original_idx , FalseVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.