Follow

Follow

Nhut Nguyen
Â·Apr 22, 2022Â·

# 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

``````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 <= 10^6`.
• At most `10^4` calls will be made to `put`, `get`, and `remove`.

# Solution 1: Store all keys' values

## Code

``````#include <iostream>
#include <vector>
using namespace std;
class MyHashMap {
vector<int> _v;
public:
MyHashMap() : _v(1000001, -1) {

}
void put(int key, int value) {
_v[key] = value;
}
int get(int key) {
return _v[key];
}
void remove(int key) {
_v[key] = -1;
}
};
int main() {
MyHashMap m;
m.put(1, 1);
m.put(2, 2);
cout << m.get(1) << endl;
cout << m.get(3) << endl;
m.put(2, 1);
cout << m.get(2) << endl;
m.remove(2);
cout << m.get(2) << endl;
}
``````
``````Output:
1
-1
1
-1
``````

## Complexity

• Runtime: `O(1)`.
• Extra space: `KEY_MAX`, which is `10^6` in this problem.

# Solution 2: Store only real keys

## Code

``````#include <iostream>
#include <vector>
using namespace std;
class MyHashMap {
vector<pair<int, int> > _v;
public:
MyHashMap() {

}
void put(int key, int value) {
for (auto& p : _v) {
if (p.first == key) {
p.second = value;
return;
}
}
_v.push_back(make_pair(key, value));
}
int get(int key) {
for (auto& p : _v) {
if (p.first == key) {
return p.second;
}
}
return -1;
}
void remove(int key) {
auto it = _v.begin();
while (it != _v.end()) {
if (it->first == key) {
_v.erase(it);
return;
} else {
it++;
}
}
}
};
int main() {
MyHashMap m;
m.put(1, 1);
m.put(2, 2);
cout << m.get(1) << endl;
cout << m.get(3) << endl;
m.put(2, 1);
cout << m.get(2) << endl;
m.remove(2);
cout << m.get(2) << endl;
}
``````
``````Output:
1
-1
1
-1
``````

## Complexity

• Runtime: `O(N)`, where `N` is the number of keys.
• Extra space: `O(2N)`.