705. Design HashSet
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.
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 toadd
,remove
, andcontains
.
Follow up: Could you solve the problem without using the built-in HashSet library?
Rust Solution
#[derive(Default)]
struct MyHashSet {
table: Vec<bool>,
}
impl MyHashSet {
fn new() -> Self {
MyHashSet {
table: vec![false; 1_000_000],
}
}
fn add(&mut self, key: i32) {
self.table[key as usize] = true;
}
fn remove(&mut self, key: i32) {
self.table[key as usize] = false;
}
fn contains(&self, key: i32) -> bool {
self.table[key as usize]
}
}
#[test]
fn test() {
let mut hs = MyHashSet::new();
hs.add(1);
hs.add(2);
assert_eq!(hs.contains(1), true);
assert_eq!(hs.contains(3), false);
hs.add(2);
assert_eq!(hs.contains(2), true);
hs.remove(2);
assert_eq!(hs.contains(2), false);
}
Having problems with this solution? Click here to submit an issue on github.