Log inSign up
easyLeetCodeNot Started

Design HashMap

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on LeetCode
Lesson

Problem Statement

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 · Example 1: Basic Operations:

Input: put(1, 1), put(2, 2), get(1), get(3), put(2, 1), get(2), remove(2), get(2)
Output: [null, null, 1, -1, null, 1, null, -1]
Explanation: - put(1, 1), put(2, 2)\n- get(1) -> 1\n- get(3) -> -1 (not found)\n- put(2, 1) updates key 2\n- get(2) -> 1\n- remove(2) removes key 2\n- get(2) -> -1.

Constraints:

  • 0 <= key, value <= 106
  • At most 104 calls will be made to put, get, and remove.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand hash functions and collision resolution strategies.
  • Compare separate chaining versus open addressing.
  • Implement an idiomatic hash table from scratch in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Design foundational key-value data structure.
  • Prohibit built-in library usage.
  • High volume of insert/lookup/delete calls.

Algorithmic Decision Tree:

  • Use modulo arithmetic for index hashing.
  • Implement separate chaining for collision resolution.

Connected Patterns:

Design HashSetLRU CacheLFU Cache

1. Direct Access Array

Intuition

Initialize an array of size 1000001 with all entries set to -1. Put sets arr[key] = value, get returns arr[key], and remove sets arr[key] = -1.

When to apply: When memory is unconstrained and key domain is strictly bounded small integers.

Algorithm

  1. Step 1: In constructor, allocate array of size 1000001 filled with -1.
  2. Step 2: put(key, val): arr[key] = val.
  3. Step 3: get(key): return arr[key].
  4. Step 4: remove(key): arr[key] = -1.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class MyHashMap {
7 vector<int> data;
8public:
9 MyHashMap() : data(1000001, -1) {}
10
11 void put(int key, int value) {
12 data[key] = value;
13 }
14
15 int get(int key) {
16 return data[key];
17 }
18
19 void remove(int key) {
20 data[key] = -1;
21 }
22};
23
24int main() {
25 MyHashMap myMap;
26 myMap.put(1, 1);
27 myMap.put(2, 2);
28 cout << "get(1): " << myMap.get(1) << endl; // 1
29 cout << "get(3): " << myMap.get(3) << endl; // -1
30 myMap.put(2, 1);
31 cout << "get(2): " << myMap.get(2) << endl; // 1
32 myMap.remove(2);
33 cout << "get(2): " << myMap.get(2) << endl; // -1
34 return 0;
35}

Time & Space Complexity

  • Time complexity: O(1) for all operations
  • Space complexity: O(M) where M = 10^6

2. Open Addressing with Linear Probing

Intuition

Store keys and values in parallel flat arrays of fixed prime capacity (e.g., 20011). When a collision occurs, check (index + 1) % capacity. On deletion, place a tombstone marker so subsequent linear probing does not terminate prematurely.

When to apply: When memory footprint must be contiguous without pointer indirection.

Algorithm

  1. Step 1: Initialize keys array with -1 and values array with -1.
  2. Step 2: put(key, val): hash key = key % cap; if occupied by another key, step forward until key or empty slot found.
  3. Step 3: get(key): hash key = key % cap; probe forward until key matches or empty slot encountered.
  4. Step 4: remove(key): probe until found, then mark key with tombstone (-2).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class MyHashMap {
7 static const int CAP = 20011;
8 vector<int> keys;
9 vector<int> vals;
10public:
11 MyHashMap() : keys(CAP, -1), vals(CAP, -1) {}
12
13 void put(int key, int value) {
14 int idx = key % CAP;
15 while (keys[idx] != -1 && keys[idx] != -2 && keys[idx] != key) {
16 idx = (idx + 1) % CAP;
17 }
18 keys[idx] = key;
19 vals[idx] = value;
20 }
21
22 int get(int key) {
23 int idx = key % CAP;
24 int start = idx;
25 while (keys[idx] != -1) {
26 if (keys[idx] == key) return vals[idx];
27 idx = (idx + 1) % CAP;
28 if (idx == start) break;
29 }
30 return -1;
31 }
32
33 void remove(int key) {
34 int idx = key % CAP;
35 int start = idx;
36 while (keys[idx] != -1) {
37 if (keys[idx] == key) {
38 keys[idx] = -2; // tombstone
39 vals[idx] = -1;
40 return;
41 }
42 idx = (idx + 1) % CAP;
43 if (idx == start) break;
44 }
45 }
46};
47
48int main() {
49 MyHashMap myMap;
50 myMap.put(1, 1);
51 myMap.put(2, 2);
52 cout << "get(1): " << myMap.get(1) << endl;
53 cout << "get(3): " << myMap.get(3) << endl;
54 myMap.put(2, 1);
55 cout << "get(2): " << myMap.get(2) << endl;
56 myMap.remove(2);
57 cout << "get(2): " << myMap.get(2) << endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(1) average, O(Capacity) worst case
  • Space complexity: O(Capacity)

3. Separate Chaining with Prime Modulo Buckets

Intuition

Select a prime number of buckets (e.g. 769). For any key, its bucket index is key % 769. Each bucket holds a collection of key-value pairs. Inside a bucket, scan to update or retrieve. Because 769 distributes keys uniformly, the expected chain length is O(N / 769) ≈ O(1) average time.

When to apply: Standard production design for hash tables.

Algorithm

  1. Step 1: Initialize array of 769 empty buckets.
  2. Step 2: put(key, val): hash to bucket = key % 769. Scan bucket: if key found, update val. If not found, append [key, val].
  3. Step 3: get(key): hash to bucket. Scan: if key matches, return val. Else return -1.
  4. Step 4: remove(key): hash to bucket. Scan: if key matches, erase from bucket.

Interactive Trace for MyHashMap

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: put(1, 1)
Visual state
Values and pointers at this exact step
pointers
S
empty
(1, 1)
0
1
↑ hashIndex
Check / comparison
1 % 769 = 1
Decision / next transition
Bucket 1: [(1, 1)].
Why this step matters

Step 1: put(1, 1). Hash: 1 % 769 = 1. Insert (1, 1) into Bucket 1.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <list>
4#include <utility>
5
6using namespace std;
7
8class MyHashMap {
9 static const int BUCKETS = 769;
10 vector<list<pair<int, int>>> table;
11
12 int hash(int key) {
13 return key % BUCKETS;
14 }
15
16public:
17 MyHashMap() : table(BUCKETS) {}
18
19 void put(int key, int value) {
20 int idx = hash(key);
21 for (auto& item : table[idx]) {
22 if (item.first == key) {
23 item.second = value;
24 return;
25 }
26 }
27 table[idx].push_back({key, value});
28 }
29
30 int get(int key) {
31 int idx = hash(key);
32 for (const auto& item : table[idx]) {
33 if (item.first == key) {
34 return item.second;
35 }
36 }
37 return -1;
38 }
39
40 void remove(int key) {
41 int idx = hash(key);
42 for (auto it = table[idx].begin(); it != table[idx].end(); ++it) {
43 if (it->first == key) {
44 table[idx].erase(it);
45 return;
46 }
47 }
48 }
49};
50
51int main() {
52 MyHashMap myMap;
53 myMap.put(1, 1);
54 myMap.put(2, 2);
55 cout << "get(1): " << myMap.get(1) << endl; // 1
56 cout << "get(3): " << myMap.get(3) << endl; // -1
57 myMap.put(2, 1);
58 cout << "get(2): " << myMap.get(2) << endl; // 1
59 myMap.remove(2);
60 cout << "get(2): " << myMap.get(2) << endl; // -1
61 return 0;
62}

Time & Space Complexity

  • Time complexity: O(1) average, O(N/B) worst case
  • Space complexity: O(B + N) where B = 769

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Direct Access ArrayO(1) strictly for all operationsO(M) where M = 10^6Allocate a fixed array of size 1,000,001 initialized to -1. Index directly with the key.Excessive memory allocation upfront.
2.Better — Open Addressing / Linear ProbingO(1) average, O(N) worst case under clusteringO(Capacity)Maintain a flat array with load factor tracking. On collision, probe subsequent array indices sequentially.Primary clustering during high load.
3.Optimal — Bucket Array with Separate ChainingOptimalO(1) average, O(N/B) worst caseO(B + N) where B is prime bucket countUse a prime number of buckets (e.g. 769). Each bucket contains a linked list of key-value pairs.Bucket linked list traversal.

Common Pitfalls & Crucial Edge Cases

Allocating a flat array of size 10^6

While it passes on small constraints, interviewers reject huge flat arrays because it defeats the purpose of designing a true hash table with collision resolution.

Inserting duplicate key entries on `put`

Failing to check whether the key already exists in the bucket list causes memory growth and incorrect get behavior.

Not handling removal of the head node in a linked list

Must update bucket head pointer when removing the first element.

Crucial Edge Cases to Validate:

  • Key does not exist — get(key) returns -1.
  • Updating an existing key — put(key, val) updates the existing value without inserting duplicate entries.
  • Removing a non-existent key — remove(key) should do nothing without throwing an error.
  • Extreme keys (key = 0 or key = 10^6) — Bucket modulo handles boundary values safely.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Discuss both collision resolution strategies: Separate Chaining vs Open Addressing (Linear/Quadratic Probing).
  2. Mention the load factor (N / capacity) and when a production hash map triggers dynamic rehashing (resizing).
  3. Explain how modern Java HashMap converts linked list buckets to red-black trees when bucket size exceeds 8 (TREEIFY_THRESHOLD).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How does the separate chaining technique resolve hash collisions in Design HashMap?

2.Why is a prime number (e.g. 769, 10007) commonly chosen as the bucket array size?

3.What should get(key) return if the key is not present in the map?

Back to DSA Sheet