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 <= 106104 calls will be made to put, get, and remove.The key idea behind #706 Design HashMap is to implement a simplified version of a hash table without using built‑in libraries. A common approach is to use an array of buckets where each bucket stores key–value pairs that hash to the same index. A hash function (often key % size) maps each key to a bucket index.
To handle collisions, the most straightforward method is separate chaining. Each bucket can store a small linked list (or dynamic list) of pairs. When inserting (put), you either update an existing key or append a new pair. For retrieval (get), traverse the bucket to find the matching key. For deletion (remove), locate and remove the node from the bucket list.
With a well-distributed hash function and enough buckets, operations run in average O(1) time. However, in the worst case where many keys collide, performance can degrade to O(n). Space complexity depends on the number of buckets and stored elements.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Table with Separate Chaining | O(1) average for put/get/remove, O(n) worst case | O(n) |
Ashish Pratap Singh
This method employs an array of linked lists (chaining) to handle collisions. Each index represents a hash code, and if multiple keys hash to the same index, we store them in a linked list at that index. This helps us efficiently manage key collisions.
Time Complexity: For each operation (put, get, remove), it is O(n) in the worst case, where n is the number of keys stored at a particular index.
Space Complexity: O(N) where N is the number of distinct keys inserted into the hash map.
1import java.util.LinkedList;
2
3class MyHashMap {
4
5 private class Pair {
6 int key, value
This Java implementation uses an array of linked lists to store pairs of keys and values. Each bucket in the map is a linked list to handle potential collisions.
Pair class holds the key-value entries.put updates an entry if the key exists; otherwise, it adds a new entry.get looks through the linked list at the computed index to find the key.remove deletes the key-value pair if it exists in the map.Double hashing avoids the clustering problem by calculating two hash functions. If a collision occurs, a second hash determines the step size for probing.
Time Complexity: O(1) on average for put, get, and remove due to effective hashing; O(n) in worst-case.
Space Complexity: O(N) for storing entries with keys and values.
1class
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, hash table design questions like Design HashMap are common in coding interviews at large tech companies. They test understanding of hashing, collision handling, and data structure design. Candidates are often expected to discuss both average and worst-case complexities.
The optimal approach is to implement a hash table using an array of buckets and a hash function to map keys to indices. Collisions can be handled using separate chaining with linked lists or dynamic lists. This allows average O(1) time for insertion, lookup, and deletion.
A hash table built with an array and linked lists is the most common structure. Each array index acts as a bucket that stores multiple key-value pairs when collisions occur. This structure efficiently supports constant-time operations on average.
Collisions occur when multiple keys map to the same index. A common solution is separate chaining, where each bucket stores a linked list of key-value pairs. During operations, the algorithm scans only that bucket's list to find or update the correct key.
In JavaScript's setup, judicious double hashing governs open addressing policy, augmenting efficiency usually diminished by collision instances.