Design HashMap solution and explanation
Google
9 more videos on this problem
Design Hashmap - Leetcode 706 - PythonNeetCodeIO · 14:30 · 73K views
Design HashMap | Live Coding with Explanation | Leetcode - 706Algorithms Made Easy · 12:17 · 27K views
Design HashMap | LeetCode 706 | C++, Java, PythonKnowledge Center · 13:41 · 18K views
Design HashMap | Brute Force | Optimal | META | GOOGLE | NETFLIX | Leetcode - 706codestorywithMIK · 23:51 · 13K views
Design HashMap - LeetCode #706 | Python, JavaScript, Java, C++CodingNinja · 11:39 · 3K views
Design HashMap | leetcode 706Coding Decoded · 6:50 · 1K views
Design HashMap - Leetcode 706Algorial · 11:32 · 978 views
706 design hashmap | 706 design hashmap leetcodeRuntime Error · 9:56 · 812 views
Leetcode | Easy | 706. Design HashMap | JavascriptSoftware Interviews Prep · 3:56 · 430 views
Design Hash Map - LeetCode 706 - PythonAlpha-Code · 16:46 · 207 views
The problem
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.
Approach overview
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 1: Approach 1: Array with Separate Chaining
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.
class MyHashMap:
def __init__(self):
self.size = 1000
self.map = [[] for _ in range(self.size)]
def put(self, key: int, value: int) -> None:
index = key % self.size
for kv in self.map[index]:
if kv[0] == key:
kv[1] = value
return
self.map[index].append([key, value])
def get(self, key: int) -> int:
index = key % self.size
for kv in self.map[index]:
if kv[0] == key:
return kv[1]
return -1
def remove(self, key: int) -> None:
index = key % self.size
for i, kv in enumerate(self.map[index]):
if kv[0] == key:
del self.map[index][i]
returnimport java.util.LinkedList;
class MyHashMap {
private class Pair {
int key, value;
Pair(int k, int v) {
key = k;
value = v;
}
}
private static final int SIZE = 1000;
private LinkedList<Pair>[] map;
public MyHashMap() {
map = new LinkedList[SIZE];
}
public void put(int key, int value) {
int index = key % SIZE;
if (map[index] == null) {
map[index] = new LinkedList<Pair>();
map[index].add(new Pair(key, value));
} else {
for (Pair p : map[index]) {
if (p.key == key) {
p.value = value;
return;
}
}
map[index].add(new Pair(key, value));
}
}
public int get(int key) {
int index = key % SIZE;
if (map[index] != null) {
for (Pair p : map[index]) {
if (p.key == key) {
return p.value;
}
}
}
return -1;
}
public void remove(int key) {
int index = key % SIZE;
if (map[index] != null) {
Pair toRemove = null;
for (Pair p : map[index]) {
if (p.key == key) {
toRemove = p;
}
}
if (toRemove != null) map[index].remove(toRemove);
}
}
}#include <vector>
#include <list>
using namespace std;
class MyHashMap {
private:
static const int size = 1000;
vector<list<pair<int, int>>> map;
int hash(int key) {
return key % size;
}
public:
MyHashMap() {
map.resize(size);
}
void put(int key, int value) {
int idx = hash(key);
for (auto &it : map[idx]) {
if (it.first == key) {
it.second = value;
return;
}
}
map[idx].emplace_back(key, value);
}
int get(int key) {
int idx = hash(key);
for (const auto &it : map[idx]) {
if (it.first == key) {
return it.second;
}
}
return -1;
}
void remove(int key) {
int idx = hash(key);
map[idx].remove_if([key](const pair<int, int> &it) { return it.first == key; });
}
};class MyHashMap {
constructor() {
this.size = 1000;
this.map = Array.from({ length: this.size }, () => []);
}
put(key, value) {
const index = key % this.size;
for (let pair of this.map[index]) {
if (pair[0] === key) {
pair[1] = value;
return;
}
}
this.map[index].push([key, value]);
}
get(key) {
const index = key % this.size;
for (let pair of this.map[index]) {
if (pair[0] === key) {
return pair[1];
}
}
return -1;
}
remove(key) {
const index = key % this.size;
this.map[index] = this.map[index].filter(pair => pair[0] !== key);
}
}#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 1000
typedef struct Node {
int key, value;
struct Node* next;
} Node;
Node* hashMap[MAX_SIZE];
unsigned int hashFunction(int key) {
return key % MAX_SIZE;
}
Node* createNode(int key, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->value = value;
newNode->next = NULL;
return newNode;
}
void myHashMapPut(int key, int value) {
int hash = hashFunction(key);
Node* current = hashMap[hash];
while (current != NULL) {
if (current->key == key) {
current->value = value;
return;
}
current = current->next;
}
Node* newNode = createNode(key, value);
newNode->next = hashMap[hash];
hashMap[hash] = newNode;
}
int myHashMapGet(int key) {
int hash = hashFunction(key);
Node* current = hashMap[hash];
while (current != NULL) {
if (current->key == key) {
return current->value;
}
current = current->next;
}
return -1;
}
void myHashMapRemove(int key) {
int hash = hashFunction(key);
Node* current = hashMap[hash];
Node* prev = NULL;
while (current != NULL) {
if (current->key == key) {
if (prev != NULL) {
prev->next = current->next;
} else {
hashMap[hash] = current->next;
}
free(current);
return;
}
prev = current;
current = current->next;
}
}using System;
using System.Collections.Generic;
public class MyHashMap {
private class Pair {
public int Key;
public int Value;
public Pair(int key, int value) {
Key = key;
Value = value;
}
}
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 Python version uses an array of lists to implement separate chaining for achieving collision resolution in the hash map.
- The
putmethod updates or inserts a key-value pair. - The
getmethod searches for a key at the calculated index. - The
removemethod deletes the key-value pair if present.
Time Complexity: O(1) on average for put, get, and remove, though may increase with serious hash collisions.
Space Complexity: O(N) where N is the number of stored key-value pairs.
Approach 2: Approach 2: Double Hashing
Double hashing avoids the clustering problem by calculating two hash functions. If a collision occurs, a second hash determines the step size for probing.
class MyHashMap:
def __init__(self):
self.size = 1000
self.map = [[-1, -1] for _ in range(self.size)]
self.occupied = [False] * self.size
def primaryHash(self, key):
return key % self.size
def secondaryHash(self, key):
return 1 + (key % (self.size - 1))
def put(self, key: int, value: int) -> None:
index = self.primaryHash(key)
step = self.secondaryHash(key)
while True:
if not self.occupied[index] or self.map[index][0] == key:
self.map[index] = [key, value]
self.occupied[index] = True
return
index = (index + step) % self.size
def get(self, key: int) -> int:
index = self.primaryHash(key)
step = self.secondaryHash(key)
while True:
if not self.occupied[index]:
return -1
if self.map[index][0] == key:
return self.map[index][1]
index = (index + step) % self.size
def remove(self, key: int) -> None:
index = self.primaryHash(key)
step = self.secondaryHash(key)
while True:
if self.occupied[index] and self.map[index][0] == key:
self.occupied[index] = False
self.map[index][0] = -1
return
index = (index + step) % self.sizeimport java.util.Arrays;
class MyHashMap {
private int[][] map;
private boolean[] occupied;
static final int SIZE = 1000;
public MyHashMap() {
map = new int[SIZE][2];
occupied = new boolean[SIZE];
for (int[] entry : map) {
Arrays.fill(entry, -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 primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
while (true) {
if (!occupied[index] || map[index][0] == key) {
map[index][0] = key;
map[index][1] = value;
occupied[index] = true;
return;
}
index = (index + secondary) % SIZE;
}
}
public int get(int key) {
int primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
while (true) {
if (!occupied[index]) return -1;
if (map[index][0] == key) return map[index][1];
index = (index + secondary) % SIZE;
}
}
public void remove(int key) {
int primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
while (true) {
if (occupied[index] && map[index][0] == key) {
occupied[index] = false;
map[index][0] = -1;
return;
}
index = (index + secondary) % SIZE;
}
}
}#include <vector>
#include <utility>
using namespace std;
class MyHashMap {
private:
static const int size = 1000;
vector<pair<int, int>> map;
vector<bool> occupied;
int primaryHash(int key) {
return key % size;
}
int secondaryHash(int key) {
return 1 + (key % (size - 1));
}
public:
MyHashMap(): map(size, make_pair(-1, -1)), occupied(size, false) {}
void put(int key, int value) {
int primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
for (int i = 0; i < size; ++i) {
if (!occupied[index] || map[index].first == key) {
map[index] = {key, value};
occupied[index] = true;
return;
}
index = (index + secondary) % size;
}
}
int get(int key) {
int primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
for (int i = 0; i < size; ++i) {
if (!occupied[index]) {
return -1;
}
if (map[index].first == key) {
return map[index].second;
}
index = (index + secondary) % size;
}
return -1;
}
void remove(int key) {
int primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
for (int i = 0; i < size; ++i) {
if (occupied[index] && map[index].first == key) {
occupied[index] = false;
return;
}
index = (index + secondary) % size;
}
}
};class MyHashMap {
constructor() {
this.size = 1000;
this.map = Array.from({length: this.size}, () => [-1, -1]);
this.occupied = Array(this.size).fill(false);
}
primaryHash(key) {
return key % this.size;
}
secondaryHash(key) {
return 1 + (key % (this.size - 1));
}
put(key, value) {
let index = this.primaryHash(key);
const step = this.secondaryHash(key);
while (true) {
if (!this.occupied[index] || this.map[index][0] === key) {
this.map[index] = [key, value];
this.occupied[index] = true;
return;
}
index = (index + step) % this.size;
}
}
get(key) {
let index = this.primaryHash(key);
const step = this.secondaryHash(key);
while (true) {
if (!this.occupied[index]) return -1;
if (this.map[index][0] === key) return this.map[index][1];
index = (index + step) % this.size;
}
}
remove(key) {
let index = this.primaryHash(key);
const step = this.secondaryHash(key);
while (true) {
if (this.occupied[index] && this.map[index][0] === key) {
this.occupied[index] = false;
this.map[index][0] = -1;
return;
}
index = (index + step) % this.size;
}
}
}#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 1000
typedef struct {
int key;
int value;
int isOccupied;
} Entry;
Entry hashMap[MAX_SIZE];
unsigned int primaryHash(int key) {
return key % MAX_SIZE;
}
unsigned int secondaryHash(int key) {
return 1 + (key % (MAX_SIZE - 1));
}
void myHashMapPut(int key, int value) {
int primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
for (int i = 0; i < MAX_SIZE; ++i) {
if (!hashMap[index].isOccupied || hashMap[index].key == key) {
hashMap[index].key = key;
hashMap[index].value = value;
hashMap[index].isOccupied = 1;
return;
}
index = (index + secondary) % MAX_SIZE;
}
}
int myHashMapGet(int key) {
int primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
for (int i = 0; i < MAX_SIZE; ++i) {
if (!hashMap[index].isOccupied) {
return -1;
}
if (hashMap[index].key == key) {
return hashMap[index].value;
}
index = (index + secondary) % MAX_SIZE;
}
return -1;
}
void myHashMapRemove(int key) {
int primary = primaryHash(key);
int secondary = secondaryHash(key);
int index = primary;
for (int i = 0; i < MAX_SIZE; ++i) {
if (hashMap[index].isOccupied && hashMap[index].key == key) {
hashMap[index].isOccupied = 0;
return;
}
index = (index + secondary) % MAX_SIZE;
}
}using System;
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;
}
}
}In Python, double hashing enhances open addressing with twin hashing functions to direct behaviors in stable or conflict scenarios.
- Setup grants initial key-positioning parameters.
- Processes convert dynamic assignment and retrieval into approachable iterations.
- Index recalibration grounds fundamental hash navigations.
Time Complexity: Tends toward O(1) consistently thanks to split hashing. Resize-demand contexts may impose heavier loads.
Space Complexity: O(N) in flexibility to accommodate input scopes.
Approach 3: Default Approach
class MyHashMap {
data: Array<number>;
constructor() {
this.data = new Array(10 ** 6 + 1).fill(-1);
}
put(key: number, value: number): void {
this.data[key] = value;
}
get(key: number): number {
return this.data[key];
}
remove(key: number): void {
this.data[key] = -1;
}
}
/**
* Your MyHashMap object will be instantiated and called as such:
* var obj = new MyHashMap()
* obj.put(key,value)
* var param_2 = obj.get(key)
* obj.remove(key)
*/type MyHashMap struct {
data []int
}
func Constructor() MyHashMap {
data := make([]int, 1000010)
for i := range data {
data[i] = -1
}
return MyHashMap{data}
}
func (this *MyHashMap) Put(key int, value int) {
this.data[key] = value
}
func (this *MyHashMap) Get(key int) int {
return this.data[key]
}
func (this *MyHashMap) Remove(key int) {
this.data[key] = -1
}
/**
* Your MyHashMap object will be instantiated and called as such:
* obj := Constructor();
* obj.Put(key,value);
* param_2 := obj.Get(key);
* obj.Remove(key);
*/Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Array with Separate Chaining | Time Complexity: O(1) on average for put, get, and remove, though may increase with serious hash collisions. |
| Approach 2: Double Hashing | Time Complexity: Tends toward O(1) consistently thanks to split hashing. Resize-demand contexts may impose heavier loads. |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Design HashMap easy or hard?
Design HashMap is labeled Easy on LeetCode but still tests core hash table concepts such as hashing, collision handling, and bucket management. The logic is straightforward once you understand how arrays and linked lists combine to implement a hash table.
How to solve Design HashMap in O(1)?
Use a hash table with a deterministic hash function such as key % bucketCount. Map the key to a bucket and handle collisions using either a linked list (separate chaining) or probing (double hashing). Each operation becomes constant-time on average because only a small portion of the structure is accessed.
What is the best approach for Design HashMap?
Separate chaining with an array of buckets is the most common approach. Each bucket stores a linked list of key–value pairs, and a simple hash function maps keys to indices. With a good distribution, put, get, and remove run in O(1) average time and O(n) space for stored elements.
Is Design HashMap asked at Google/Amazon/Meta?
Hash table design problems appear frequently in interviews at companies like Amazon, Google, and Meta because they test understanding of hashing, collision handling, and data structure design. Variants of this question are common in system design and data structure rounds.
What data structure is used in Design HashMap?
The implementation typically uses an array as the primary storage structure combined with either linked lists for separate chaining or probing techniques for open addressing. These structures support fast key indexing and efficient collision resolution.
What is the time complexity of Design HashMap?
Both separate chaining and double hashing provide O(1) average time complexity for put, get, and remove operations. In worst-case scenarios with many collisions, operations can degrade to O(n), but proper hashing and bucket sizing keep this rare in practice.
Design HashMap Python or Java solution approach?
The standard approach in Python or Java uses an array of buckets and stores key–value pairs in linked lists for collisions. Each operation computes the bucket index using a hash function, scans the bucket for the key, and inserts, retrieves, or deletes accordingly in O(1) average time.