Design Hashset Problem
Problem
Design a HashSet without using any built-in hash table libraries.
Implement MyHashSet
class:
void add(key)
Inserts the valuekey
into the HashSet.bool contains(key)
Returns whether the valuekey
exists in the HashSet or not.void remove(key)
Removes the valuekey
in the HashSet. Ifkey
does not exist in the HashSet, do nothing.
Examples
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 <= 10^6
- At most
10^4
calls will be made toadd
,remove
, andcontains
.
Solution
Method 1 - Using Simple Array
class MyHashSet {
private int[] arr;
/** Initialize your data structure here. */
public MyHashSet() {
arr = new int[1000001];
}
public void add(int key) {
arr[key] = key + 1;
}
public void remove(int key) {
arr[key] = 0; // handle the case key=0
}
/** Returns true if this set contains the specified element */
public boolean contains(int key) {
return (arr[key] != 0);
}
}