Editorial
Core insight
Design HashMap · Design Patterns
Core Insight for Design HashMap
The transition from the brute force linear search to an optimal solution relies on Hashing. Instead of searching a single large list, we can divide the data into many smaller lists (buckets) based on the key.
The fundamental insight is Collision Resolution via Separate Chaining.
- Hash Function: We need a way to map a large range of integer keys ( to ) to a smaller set of indices (buckets). A simple modulo operator (
key % M) serves as an effective hash function, whereMis the number of buckets. - Buckets: We create a fixed-size array of "buckets". Each bucket is responsible for a subset of the keys.
- Separate Chaining: Since multiple keys might map to the same bucket (a collision), each bucket acts as the head of a Linked List. All keys hashing to index
iare stored in the Linked List atbuckets[i].
Visual Description: Imagine a vertical array of size 1000. This is the "backbone" of the HashMap.
- When we insert
key = 1, it maps to index1 % 1000 = 1. We place a node[1, val]at index 1. - When we insert
key = 1001, it also maps to index1001 % 1000 = 1. This is a collision. We do not overwrite the existing node. Instead, we append a new node[1001, val]to the linked list starting at index 1. - The structure looks like an array where some slots branch out horizontally into chains of nodes.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 706: Design HashMap Solution & Explanation
Problem Overview
TL;DR: The optimal solution implements a hash table using an array of buckets, where each bucket is a linked list (Separate Chaining) to handle collisions, allowing for average time complexity for all operations.
The LeetCode 706 problem asks us to design a HashMap data structure from scratch without using any built-in hash table libraries (like Java's HashMap, C++'s std::unordered_map, or Python's dict). We need to support three primary operations:
- Put: Insert a key-value pair or update the value if the key already exists.
- Get: Retrieve the value associated with a key, or return -1 if the key does not exist.
- Remove: Delete the key-value pair if it exists.
This is a classic "Design" problem often used in interviews to test a candidate's understanding of data structure internals, specifically hashing mechanisms and collision resolution.
Brute Force Approach for Design HashMap
The naive approach to solving this problem is to ignore the hashing mechanism entirely and store all key-value pairs in a single linear data structure, such as a resizable array (ArrayList) or a singular Linked List.
Naive Algorithm
- Initialize an empty list to store pairs
(key, value). - Put: Iterate through the entire list. If the key is found, update its value. If the end is reached without finding the key, append the new pair.
- Get: Iterate through the entire list. If the key is found, return the value. If not found, return -1.
- Remove: Iterate through the list. If the key is found, remove that element from the list.
Pseudo-code
List storage
function put(key, value):
for pair in storage:
if pair.key == key:
pair.value = value
return
storage.add((key, value))
function get(key):
for pair in storage:
if pair.key == key:
return pair.value
return -1Why this fails
The time complexity for this approach is for every operation, where is the number of entries currently in the map. As the number of entries grows, the performance degrades linearly. While the constraints of LeetCode 706 ( calls) might allow this to pass without a Time Limit Exceeded (TLE) depending on the test cases, it fails the interview requirement of designing an efficient data structure. A proper HashMap must offer average time complexity.
Algorithm Strategy: Design Patterns
We will implement the Separate Chaining strategy.
- Initialization: Create an array of pointers (or references) to
Nodeobjects. The size of this array (modulus) is a design choice; a prime number or a sufficiently large number (e.g., 1000 or 2069) helps distribute keys uniformly. - Node Structure: Define a simple
Nodeclass containingkey,value, and anextpointer. - Hash Function: Define a helper method
hash(key)that returnskey % size_of_array. - Operations:
- Put: Calculate the hash index. Traverse the linked list at that index. If the key exists, update the value. If not, create a new node and append it to the list (or insert at the head).
- Get: Calculate the hash index. Traverse the linked list. If the key is found, return the value. If the traversal ends, return -1.
- Remove: Calculate the hash index. Traverse the linked list to find the key. If found, adjust the pointers to bypass (remove) the node.
This strategy enforces the constraint that get and put operations only traverse a very small fraction of the total data (the length of one specific chain), resulting in constant time complexity on average.
Execution Flow
Let's trace the execution for put(1, 1), put(2, 2), and put(2, 1) with a bucket size of 10.
- Initialize: An array
bucketsof size 10 is created. All indices arenull. put(1, 1):- Hash:
1 % 10 = 1. - Check
buckets[1]. It isnull. - Create a new Node
(1, 1). - Set
buckets[1]to point to this new Node.
- Hash:
put(2, 2):- Hash:
2 % 10 = 2. - Check
buckets[2]. It isnull. - Create a new Node
(2, 2). - Set
buckets[2]to point to this new Node.
- Hash:
put(2, 1)(Update):- Hash:
2 % 10 = 2. - Traverse the list at
buckets[2]. - First node is
(2, 2). The key2matches the input key. - Update the value of this node to
1. - The list at
buckets[2]is now(2, 1).
- Hash:
get(1):- Hash:
1 % 10 = 1. - Traverse
buckets[1]. Found node(1, 1). - Return
1.
- Hash:
Proof of Correctness
The correctness of this design relies on two properties:
- Deterministic Hashing: The hash function
key % Mis deterministic. The same key will always map to the same bucket index. This guarantees that if weputa key, we will look in the exact same place togetorremoveit. - List Integrity: By using a Linked List for collisions, we ensure no data is lost when two keys map to the same index. The traversal logic linearly scans the chain, guaranteeing that we find the specific key if it exists. Since keys are unique (we update values if a key repeats), there is no ambiguity during retrieval.
Pattern Reuse Notes
The Design pattern and the specific sub-pattern of managing internal state via buckets or auxiliary structures appear in several other popular interview questions:
- LeetCode 146: LRU Cache - Requires combining a Hash Map with a Doubly Linked List to manage eviction policies efficiently.
- LeetCode 155: Min Stack - Involves designing a stack that retrieves the minimum element in time, often by maintaining a parallel stack for state.
- LeetCode 225: Implement Stack using Queues - Focuses on manipulating one data structure to behave like another, enforcing constraints on operation order.
- LeetCode 232: Implement Queue using Stacks - Similar to 225, this tests the ability to invert operation logic using limited standard operations.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 706
1class MyHashMap {
2private:
3 struct Node {
4 int key;
5 int val;
6 Node* next;
7 Node(int k, int v) : key(k), val(v), next(nullptr) {}
8 };
9
10 // Use a fixed size for buckets.
11 // 1000 is chosen based on the constraint of 10^4 calls.
12 const static int SIZE = 1000;
13 vector<Node*> buckets;
14
15 int hash(int key) {
16 return key % SIZE;
17 }
18
19public:
20 MyHashMap() {
21 buckets.resize(SIZE, nullptr);
22 }
23
24 void put(int key, int value) {
25 int i = hash(key);
26 Node* curr = buckets[i];
27
28 // If bucket is empty, insert new node
29 if (curr == nullptr) {
30 buckets[i] = new Node(key, value);
31 return;
32 }
33
34 // If key matches head, update
35 if (curr->key == key) {
36 curr->val = value;
37 return;
38 }
39
40 // Traverse the chain
41 while (curr->next != nullptr) {
42 if (curr->next->key == key) {
43 curr->next->val = value;
44 return;
45 }
46 curr = curr->next;
47 }
48
49 // Key not found, append to end
50 curr->next = new Node(key, value);
51 }
52
53 int get(int key) {
54 int i = hash(key);
55 Node* curr = buckets[i];
56
57 while (curr != nullptr) {
58 if (curr->key == key) {
59 return curr->val;
60 }
61 curr = curr->next;
62 }
63 return -1;
64 }
65
66 void remove(int key) {
67 int i = hash(key);
68 Node* curr = buckets[i];
69
70 if (curr == nullptr) return;
71
72 // Special case: removing head
73 if (curr->key == key) {
74 buckets[i] = curr->next;
75 delete curr; // Good practice in C++
76 return;
77 }
78
79 while (curr->next != nullptr) {
80 if (curr->next->key == key) {
81 Node* temp = curr->next;
82 curr->next = temp->next;
83 delete temp;
84 return;
85 }
86 curr = curr->next;
87 }
88 }
89};Java Solution for LeetCode 706
1class MyHashMap {
2
3 private class Node {
4 int key, val;
5 Node next;
6
7 Node(int key, int val) {
8 this.key = key;
9 this.val = val;
10 }
11 }
12
13 private static final int SIZE = 1000;
14 private Node[] buckets;
15
16 public MyHashMap() {
17 buckets = new Node[SIZE];
18 }
19
20 private int hash(int key) {
21 return key % SIZE;
22 }
23
24 public void put(int key, int value) {
25 int index = hash(key);
26 Node curr = buckets[index];
27
28 if (curr == null) {
29 buckets[index] = new Node(key, value);
30 return;
31 }
32
33 // Check head
34 if (curr.key == key) {
35 curr.val = value;
36 return;
37 }
38
39 while (curr.next != null) {
40 if (curr.next.key == key) {
41 curr.next.val = value;
42 return;
43 }
44 curr = curr.next;
45 }
46
47 curr.next = new Node(key, value);
48 }
49
50 public int get(int key) {
51 int index = hash(key);
52 Node curr = buckets[index];
53
54 while (curr != null) {
55 if (curr.key == key) {
56 return curr.val;
57 }
58 curr = curr.next;
59 }
60 return -1;
61 }
62
63 public void remove(int key) {
64 int index = hash(key);
65 Node curr = buckets[index];
66
67 if (curr == null) return;
68
69 if (curr.key == key) {
70 buckets[index] = curr.next;
71 return;
72 }
73
74 while (curr.next != null) {
75 if (curr.next.key == key) {
76 curr.next = curr.next.next;
77 return;
78 }
79 curr = curr.next;
80 }
81 }
82}Python Solution for LeetCode 706
1class Node:
2 def __init__(self, key, val):
3 self.key = key
4 self.val = val
5 self.next = None
6
7class MyHashMap:
8
9 def __init__(self):
10 self.size = 1000
11 self.buckets = [None] * self.size
12
13 def _hash(self, key):
14 return key % self.size
15
16 def put(self, key: int, value: int) -> None:
17 idx = self._hash(key)
18
19 if self.buckets[idx] is None:
20 self.buckets[idx] = Node(key, value)
21 return
22
23 curr = self.buckets[idx]
24 while True:
25 if curr.key == key:
26 curr.val = value
27 return
28 if curr.next is None:
29 break
30 curr = curr.next
31
32 curr.next = Node(key, value)
33
34 def get(self, key: int) -> int:
35 idx = self._hash(key)
36 curr = self.buckets[idx]
37
38 while curr:
39 if curr.key == key:
40 return curr.val
41 curr = curr.next
42
43 return -1
44
45 def remove(self, key: int) -> None:
46 idx = self._hash(key)
47 curr = self.buckets[idx]
48
49 if curr is None:
50 return
51
52 if curr.key == key:
53 self.buckets[idx] = curr.next
54 return
55
56 while curr.next:
57 if curr.next.key == key:
58 curr.next = curr.next.next
59 return
60 curr = curr.next