Leetcode 706. Design HashMap
2 min readJun 20, 2022
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 thekey
already exists in the map, update the correspondingvalue
.int get(int key)
returns thevalue
to which the specifiedkey
is mapped, or-1
if this map contains no mapping for thekey
.void remove(key)
removes thekey
and its correspondingvalue
if 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
104
calls will be made toput
,get
, andremove
.
class MyHashMap {
public:
vector<list<pair<int,int>>> data;
size_t size = 10000;
MyHashMap() {
data.resize(size);
}
void put(int key, int value) {
for (auto& e: data[key%size]) {
if (e.first == key) {
e.second = value;
return;
}
}
data[key % size].push_back(make_pair(key, value));
}
int get(int key) {
for (auto& e: data[key%size]) {
if (e.first == key) {
return e.second;
}
}
return -1;
}
void remove(int key) {
list<pair<int, int>>::iterator itr = data[key%size].begin();
for (; itr != data[key%size].end(); itr++) {
if (itr->first == key) {
itr = data[key%size].erase(itr);
return;
}
}
}
};
Runtime: 134 ms, faster than 90.58% of C++ online submissions for Design HashMap.
Memory Usage: 62.1 MB, less than 59.69% of C++ online submissions for Design HashMap.