# 705. Design HashSet

## An implementation for a simple hash set

·

### Problem statement

Design a HashSet without using any built-in hash table libraries.

Implement `MyHashSet` class:

• `void add(key)` Inserts the value `key` into the HashSet.

• `bool contains(key)` Returns whether the value `key` exists in the HashSet or not.

• `void remove(key)` Removes the value `key` in the HashSet. If `key` does not exist in the HashSet, do nothing.

#### Example 1

``````Input
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
Output
[null, null, null, true, false, null, true, null, false]

Explanation
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.add(2);      // set = [1, 2]
myHashSet.contains(2); // return True
myHashSet.remove(2);   // set = [1]
myHashSet.contains(2); // return False, (already removed)
``````

#### Constraints

• `0 <= key <= 10^6`.

• At most `10^4` calls will be made to `add`, `remove`, and `contains`.

### Solution 1: Store the keys

The simplest way is using a container to store the keys so you can identify if a key belongs to the HashSet or not.

#### Code

``````#include <iostream>
#include <vector>
using namespace std;
class MyHashSet {
vector<int> _v;
public:
MyHashSet() {
}
if (!contains(key)) {
_v.push_back(key);
}
}
void remove(int key) {
auto it = _v.begin();
while (it != _v.end()) {
if (*it == key) {
_v.erase(it);
return;
} else {
it++;
}
}
}
bool contains(int key) {
for (int a : _v) {
if (a == key) {
return true;
}
}
return false;
}
};
int main() {
MyHashSet m;
cout << m.contains(1) << endl;
cout << m.contains(3) << endl;
cout << m.contains(2) << endl;
m.remove(2);
cout << m.contains(2) << endl;
}
``````
``````Output:
1
0
1
0
``````

#### Complexity

• Runtime: `O(N)` for all methods, where `N` is the number of values in the HashSet.

• Extra space: `O(N)`.

### Solution 2: Marking the keys

In this problem, the HashSet does not have anything other than methods `add`, `remove` and `contains`, which only check whether a `key` exists in it or not.

With this purpose you can simply mark the keys without storing them.

#### Code

``````#include <iostream>
#include <vector>
using namespace std;
class MyHashSet {
vector<bool> _v;
public:
MyHashSet() : _v(1000001, false){
}
_v[key] = true;
}
void remove(int key) {
_v[key] = false;
}
bool contains(int key) {
return _v[key];
}
};
int main() {
MyHashSet m;
cout << m.contains(1) << endl;
cout << m.contains(3) << endl;
cout << m.contains(2) << endl;
m.remove(2);
cout << m.contains(2) << endl;
}
``````
``````Output:
1
0
1
0
``````

#### Complexity

• Runtime: `O(1)`.

• Extra space: `O(1)`.

### References

Thanks for reading. Feel free to share your thought about my content and check out my FREE book “10 Classic Coding Challenges”.