Description#
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
["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"]
[[], [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(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // return True
myHashSet.contains(3); // return False, (not found)
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 <= 106- At most
104 calls will be made to add, remove, and contains.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class MyHashSet:
def __init__(self):
self.data = [False] * 1000001
def add(self, key: int) -> None:
self.data[key] = True
def remove(self, key: int) -> None:
self.data[key] = False
def contains(self, key: int) -> bool:
return self.data[key]
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class MyHashSet {
private boolean[] data = new boolean[1000001];
public MyHashSet() {
}
public void add(int key) {
data[key] = true;
}
public void remove(int key) {
data[key] = false;
}
public boolean contains(int key) {
return data[key];
}
}
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet obj = new MyHashSet();
* obj.add(key);
* obj.remove(key);
* boolean param_3 = obj.contains(key);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class MyHashSet {
public:
bool data[1000001];
MyHashSet() {
memset(data, false, sizeof data);
}
void add(int key) {
data[key] = true;
}
void remove(int key) {
data[key] = false;
}
bool contains(int key) {
return data[key];
}
};
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet* obj = new MyHashSet();
* obj->add(key);
* obj->remove(key);
* bool param_3 = obj->contains(key);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| type MyHashSet struct {
data []bool
}
func Constructor() MyHashSet {
data := make([]bool, 1000010)
return MyHashSet{data}
}
func (this *MyHashSet) Add(key int) {
this.data[key] = true
}
func (this *MyHashSet) Remove(key int) {
this.data[key] = false
}
func (this *MyHashSet) Contains(key int) bool {
return this.data[key]
}
/**
* Your MyHashSet object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(key);
* obj.Remove(key);
* param_3 := obj.Contains(key);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class MyHashSet {
data: Array<boolean>;
constructor() {
this.data = new Array(10 ** 6 + 1).fill(false);
}
add(key: number): void {
this.data[key] = true;
}
remove(key: number): void {
this.data[key] = false;
}
contains(key: number): boolean {
return this.data[key];
}
}
/**
* Your MyHashSet object will be instantiated and called as such:
* var obj = new MyHashSet()
* obj.add(key)
* obj.remove(key)
* var param_3 = obj.contains(key)
*/
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class MyHashSet:
def __init__(self):
self.size = 1000
self.data = [[] for _ in range(self.size)]
def add(self, key: int) -> None:
if self.contains(key):
return
idx = self.hash(key)
self.data[idx].append(key)
def remove(self, key: int) -> None:
if not self.contains(key):
return
idx = self.hash(key)
self.data[idx].remove(key)
def contains(self, key: int) -> bool:
idx = self.hash(key)
return any(v == key for v in self.data[idx])
def hash(self, key) -> int:
return key % self.size
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| class MyHashSet {
private static final int SIZE = 1000;
private LinkedList[] data;
public MyHashSet() {
data = new LinkedList[SIZE];
for (int i = 0; i < SIZE; ++i) {
data[i] = new LinkedList<Integer>();
}
}
public void add(int key) {
if (contains(key)) {
return;
}
int idx = hash(key);
data[idx].addFirst(key);
}
public void remove(int key) {
if (!contains(key)) {
return;
}
int idx = hash(key);
data[idx].remove(Integer.valueOf(key));
}
public boolean contains(int key) {
int idx = hash(key);
Iterator<Integer> it = data[idx].iterator();
while (it.hasNext()) {
Integer e = it.next();
if (e == key) {
return true;
}
}
return false;
}
private int hash(int key) {
return key % SIZE;
}
}
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet obj = new MyHashSet();
* obj.add(key);
* obj.remove(key);
* boolean param_3 = obj.contains(key);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| class MyHashSet {
private:
int size = 1000;
vector<list<int>> data;
public:
MyHashSet()
: data(size) {
}
void add(int key) {
if (contains(key)) {
return;
}
int idx = hash(key);
data[idx].push_back(key);
}
void remove(int key) {
if (!contains(key)) {
return;
}
int idx = hash(key);
data[idx].remove(key);
}
bool contains(int key) {
int idx = hash(key);
for (auto it = data[idx].begin(); it != data[idx].end(); it++) {
if ((*it) == key) {
return true;
}
}
return false;
}
int hash(int key) {
return key % size;
}
};
/**
* Your MyHashSet object will be instantiated and called as such:
* MyHashSet* obj = new MyHashSet();
* obj->add(key);
* obj->remove(key);
* bool param_3 = obj->contains(key);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| type MyHashSet struct {
data []list.List
}
func Constructor() MyHashSet {
return MyHashSet{make([]list.List, 1000)}
}
func (this *MyHashSet) Add(key int) {
if this.Contains(key) {
return
}
idx := this.hash(key)
this.data[idx].PushBack(key)
}
func (this *MyHashSet) Remove(key int) {
idx := this.hash(key)
for e := this.data[idx].Front(); e != nil; e = e.Next() {
if e.Value.(int) == key {
this.data[idx].Remove(e)
}
}
}
func (this *MyHashSet) Contains(key int) bool {
idx := this.hash(key)
for e := this.data[idx].Front(); e != nil; e = e.Next() {
if e.Value.(int) == key {
return true
}
}
return false
}
func (this *MyHashSet) hash(key int) int {
return key % len(this.data)
}
/**
* Your MyHashSet object will be instantiated and called as such:
* obj := Constructor();
* obj.Add(key);
* obj.Remove(key);
* param_3 := obj.Contains(key);
*/
|
