Watch 10 video solutions for Design HashMap, a easy level problem involving Array, Hash Table, Linked List. This walkthrough by NeetCodeIO has 67,621 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: Design a HashMap from scratch that supports put(key, value), get(key), and remove(key) without using built-in hash table libraries. Keys are integers, so you control the hashing strategy, collision handling, and storage structure.
Approach 1: Array with Separate Chaining (Average O(1) time, O(n) space)
This design uses a fixed-size array as the main bucket table. A simple hash function (for example key % size) maps each key to a bucket index. Each bucket stores a small linked list of key–value pairs. When two keys hash to the same bucket, the pair is appended to the list instead of overwriting existing data.
Operations are straightforward. For put, compute the index, iterate through the bucket’s list, and update the value if the key already exists; otherwise append a new node. For get or remove, traverse the linked list and match the key. With a well-distributed hash function and enough buckets, the average bucket length stays small, giving O(1) average time per operation and O(n) space for stored elements.
This approach directly combines an array for indexing and a linked list for collision handling. It is the most common educational implementation of a hash map and mirrors how many real hash tables handle collisions internally.
Approach 2: Double Hashing (Average O(1) time, O(n) space)
Double hashing uses open addressing instead of linked structures. The table is a single array where each slot stores one key–value pair. When a collision occurs, a second hash function calculates the step size used to probe the next index. The probing sequence typically follows index = (hash1(key) + i * hash2(key)) % size.
Insertion probes until an empty slot appears. Lookup follows the same probe sequence until the key is found or an unused slot stops the search. Deletion marks a slot as deleted so probing chains remain intact. With good hash functions and a low load factor, the expected complexity remains O(1) average time for put, get, and remove, while space stays O(n).
This approach avoids pointer overhead and keeps memory contiguous, which can improve cache performance. However, it requires careful handling of deleted slots and load factor limits to prevent clustering.
Recommended for interviews: Separate chaining is usually the safest explanation. It is easier to implement, clearly demonstrates collision handling, and maps directly to how production hash tables work. Mentioning double hashing shows deeper understanding of hash table design and probing strategies, which interviewers appreciate for system-level discussions.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Array with Separate Chaining | O(1) average, O(n) worst | O(n) | Most common design for hash maps; easy to implement and explain in interviews |
| Double Hashing (Open Addressing) | O(1) average, O(n) worst | O(n) | When you want a contiguous array structure without linked lists and controlled probing |