Design HashMap
Design HashMap is a easy design data structures problem solved with the pre-processing + tradeoffs pattern.
The best approach, optimal (separate chaining), runs in O(1) average per operation time and O(B + n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (one list of pairs) up.
Problem
Build your own key-value map, MyHashMap, for integer keys and values without using any built-in hash table.
put(key, value) stores the pair, replacing the old value if key is already present. get(key) returns the value stored for key, or -1 if there is none. remove(key) deletes key and its value if it is present, and does nothing otherwise.
Examples
Example 1
- Input
put(7, 70), put(12, 5), get(7), get(3), put(7, 11), get(7), remove(12), get(12)- Output
70, -1, 11, -1- Why
- Key 3 was never stored, putting 7 again overwrites 70 with 11, and 12 is gone after remove.
Example 2
- Input
put(0, 0), get(0), remove(0), remove(0), get(0)- Output
0, -1- Why
- A value of 0 is a real value, not "missing". Removing an absent key does nothing.
Constraints
0 <= key, value <= 10^6- At most
10^4calls in total toput,getandremove. - Do not use a built-in hash table library.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (one list of pairs) | O(n) per operation | O(n) |
| Optimal (separate chaining) | O(1) average per operation | O(B + n) |
1Brute force (one list of pairs)
O(n) per operationEvery operation may look at all n stored pairs.O(n)One pair per stored key.Keep every stored (key, value) pair in a single list. Each operation scans the list for the key.
- put: scan for the key; overwrite its value if found, otherwise append a new pair.
- get: scan for the key and return its value, or -1.
- remove: scan for the key and delete that pair if found.
class MyHashMap {
private final List<int[]> pairs = new ArrayList<>();
public MyHashMap() {}
public void put(int key, int value) {
for (int[] p : pairs) {
if (p[0] == key) { p[1] = value; return; }
}
pairs.add(new int[] { key, value });
}
public int get(int key) {
for (int[] p : pairs) if (p[0] == key) return p[1];
return -1;
}
public void remove(int key) {
for (int i = 0; i < pairs.size(); i++) {
if (pairs.get(i)[0] == key) { pairs.remove(i); return; }
}
}
}class MyHashMap:
def __init__(self):
self.pairs = []
def put(self, key: int, value: int) -> None:
for p in self.pairs:
if p[0] == key:
p[1] = value
return
self.pairs.append([key, value])
def get(self, key: int) -> int:
for k, v in self.pairs:
if k == key:
return v
return -1
def remove(self, key: int) -> None:
for i, p in enumerate(self.pairs):
if p[0] == key:
self.pairs.pop(i)
returnclass MyHashMap {
vector<pair<int, int>> pairs;
public:
MyHashMap() {}
void put(int key, int value) {
for (auto& p : pairs) {
if (p.first == key) { p.second = value; return; }
}
pairs.push_back({key, value});
}
int get(int key) {
for (auto& p : pairs) if (p.first == key) return p.second;
return -1;
}
void remove(int key) {
for (size_t i = 0; i < pairs.size(); i++) {
if (pairs[i].first == key) { pairs.erase(pairs.begin() + i); return; }
}
}
};class MyHashMap {
constructor() {
this.pairs = [];
}
put(key, value) {
for (const p of this.pairs) {
if (p[0] === key) { p[1] = value; return; }
}
this.pairs.push([key, value]);
}
get(key) {
for (const [k, v] of this.pairs) if (k === key) return v;
return -1;
}
remove(key) {
const i = this.pairs.findIndex((p) => p[0] === key);
if (i !== -1) this.pairs.splice(i, 1);
}
}2Optimal (separate chaining)
O(1) average per operationEach bucket holds about n / B pairs; with B larger than the number of keys that is O(1) on average.O(B + n)B bucket lists plus one pair per stored key.Use a fixed array of B buckets (a prime such as 10007 spreads keys well). Key k always lives in bucket k % B, which holds a short list of (key, value) pairs. With n keys spread over B buckets, each bucket holds about n / B pairs, so every operation only scans a handful of entries.
- Create B empty buckets.
- put: find bucket
key % B; overwrite the pair with this key, or append a new pair. - get: scan only bucket
key % B; return the value or -1. - remove: scan only bucket
key % Band delete the matching pair.
class MyHashMap {
private static final int B = 10007;
private final List<List<int[]>> buckets = new ArrayList<>();
public MyHashMap() {
for (int i = 0; i < B; i++) buckets.add(new ArrayList<>());
}
public void put(int key, int value) {
List<int[]> bucket = buckets.get(key % B);
for (int[] p : bucket) {
if (p[0] == key) { p[1] = value; return; }
}
bucket.add(new int[] { key, value });
}
public int get(int key) {
for (int[] p : buckets.get(key % B)) if (p[0] == key) return p[1];
return -1;
}
public void remove(int key) {
List<int[]> bucket = buckets.get(key % B);
for (int i = 0; i < bucket.size(); i++) {
if (bucket.get(i)[0] == key) { bucket.remove(i); return; }
}
}
}class MyHashMap:
B = 10007
def __init__(self):
self.buckets = [[] for _ in range(self.B)]
def put(self, key: int, value: int) -> None:
bucket = self.buckets[key % self.B]
for p in bucket:
if p[0] == key:
p[1] = value
return
bucket.append([key, value])
def get(self, key: int) -> int:
for k, v in self.buckets[key % self.B]:
if k == key:
return v
return -1
def remove(self, key: int) -> None:
bucket = self.buckets[key % self.B]
for i, p in enumerate(bucket):
if p[0] == key:
bucket.pop(i)
returnclass MyHashMap {
static const int B = 10007;
vector<vector<pair<int, int>>> buckets;
public:
MyHashMap() : buckets(B) {}
void put(int key, int value) {
auto& bucket = buckets[key % B];
for (auto& p : bucket) {
if (p.first == key) { p.second = value; return; }
}
bucket.push_back({key, value});
}
int get(int key) {
for (auto& p : buckets[key % B]) if (p.first == key) return p.second;
return -1;
}
void remove(int key) {
auto& bucket = buckets[key % B];
for (size_t i = 0; i < bucket.size(); i++) {
if (bucket[i].first == key) { bucket.erase(bucket.begin() + i); return; }
}
}
};class MyHashMap {
constructor() {
this.B = 10007;
this.buckets = Array.from({ length: this.B }, () => []);
}
put(key, value) {
const bucket = this.buckets[key % this.B];
for (const p of bucket) {
if (p[0] === key) { p[1] = value; return; }
}
bucket.push([key, value]);
}
get(key) {
for (const [k, v] of this.buckets[key % this.B]) if (k === key) return v;
return -1;
}
remove(key) {
const bucket = this.buckets[key % this.B];
const i = bucket.findIndex((p) => p[0] === key);
if (i !== -1) bucket.splice(i, 1);
}
}Edge cases to test
- Overwriting the value of a key that already exists
- Removing a key that is not present
- Storing the value 0, which must not be confused with "absent"
- Several keys that land in the same bucket (for example keys that differ by the bucket count)
- Re-inserting a key after removing it
Hints
Hint 1
The simplest correct map is a list of (key, value) pairs that you scan. What does each operation cost?
Hint 2
Split the pairs into many small lists (buckets) and choose the bucket from the key, e.g. key % B. Only that bucket needs to be scanned.
FAQ
What is the best time complexity for Design HashMap?
Optimal (separate chaining) runs in O(1) average per operation time and O(B + n) extra space. Each bucket holds about n / B pairs; with B larger than the number of keys that is O(1) on average.
Which pattern does Design HashMap use?
It is a design data structures problem that uses the pre-processing + tradeoffs pattern. Other problems with the same pattern: Design Neighbor Sum Service, Simple Bank System, Design File System.
Is there a brute force solution for Design HashMap?
Yes. Brute force (one list of pairs) takes O(n) per operation time and O(n) space. Keep every stored (key, value) pair in a single list.
Which edge cases should I test for Design HashMap?
Overwriting the value of a key that already exists; Removing a key that is not present; Storing the value 0, which must not be confused with "absent"; Several keys that land in the same bucket (for example keys that differ by the bucket count); Re-inserting a key after removing it.