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.
1using System;
2using System.Collections.Generic;
3
4public class MyHashMap {
5
6 private class Pair {
7 public int Key;
8 public int Value;
9 public Pair(int key, int value) {
10 Key = key;
11 Value = value;
12 }
13 }
14
private const int size = 1000;
private List<Pair>[] map;
public MyHashMap() {
map = new List<Pair>[size];
for (int i = 0; i < size; i++) {
map[i] = new List<Pair>();
}
}
private int Hash(int key) {
return key % size;
}
public void Put(int key, int value) {
int hashKey = Hash(key);
foreach (Pair pair in map[hashKey]) {
if (pair.Key == key) {
pair.Value = value;
return;
}
}
map[hashKey].Add(new Pair(key, value));
}
public int Get(int key) {
int hashKey = Hash(key);
foreach (Pair pair in map[hashKey]) {
if (pair.Key == key) {
return pair.Value;
}
}
return -1;
}
public void Remove(int key) {
int hashKey = Hash(key);
Pair toRemove = null;
foreach (Pair pair in map[hashKey]) {
if (pair.Key == key) {
toRemove = pair;
break;
}
}
if (toRemove != null) {
map[hashKey].Remove(toRemove);
}
}
}The C# solution uses arrays of lists to implement the hash map. Each list handles collisions for a specific index of the map.
Pair class for storing key-value data is used.Put method looks for a key in its bucket and updates the value or adds a new pair if the key wasn't found.Get retrieves values by key, returning -1 if the key doesn't exist.Remove deletes the key-value pair.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.
1using System;
2
public class MyHashMap {
private int[][] map;
private bool[] occupied;
private const int size = 1000;
public MyHashMap() {
map = new int[size][];
occupied = new bool[size];
for (int i = 0; i < size; i++) {
map[i] = new int[] { -1, -1 };
}
}
private int PrimaryHash(int key) {
return key % size;
}
private int SecondaryHash(int key) {
return 1 + (key % (size - 1));
}
public void Put(int key, int value) {
int index = PrimaryHash(key);
int step = SecondaryHash(key);
while (true) {
if (!occupied[index] || map[index][0] == key) {
map[index][0] = key;
map[index][1] = value;
occupied[index] = true;
return;
}
index = (index + step) % size;
}
}
public int Get(int key) {
int index = PrimaryHash(key);
int step = SecondaryHash(key);
while (true) {
if (!occupied[index]) return -1;
if (map[index][0] == key) return map[index][1];
index = (index + step) % size;
}
}
public void Remove(int key) {
int index = PrimaryHash(key);
int step = SecondaryHash(key);
while (true) {
if (occupied[index] && map[index][0] == key) {
occupied[index] = false;
map[index][0] = -1;
return;
}
index = (index + step) % size;
}
}
}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.
Throughout this C# double hashing model, dual hashes streamline practicality across core MyHashMap operations, mandatory for double duty within clustered settings.