705. Design HashSet

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]

Bucket of BTreeSets:

#![allow(unused)]
fn main() {
#[allow(dead_code)]
struct MyHashSet {
    buckets: Vec<BTreeSet<i32>>,
    size: usize,
}

#[allow(dead_code)]
impl MyHashSet {
    // time O(1), space O(n)
    pub fn new() -> Self {
        Self {
            buckets: (0..10_000).map(|_| BTreeSet::new()).collect(),
            size: 10_000,
        }
    }

    fn hash(&self, key: i32) -> usize {
        key as usize % self.size
    }

    // time O(log k), space O(1)
    pub fn add(&mut self, key: i32) {
        let idx = self.hash(key);
        self.buckets[idx].insert(key);
    }

    // time O(log k), space O(1)
    pub fn remove(&mut self, key: i32) {
        let idx = self.hash(key);
        self.buckets[idx].remove(&key);
    }

    // time O(log k), space O(1)
    pub fn contains(&self, key: i32) -> bool {
        let idx = self.hash(key);
        self.buckets[idx].contains(&key)
}

Bucket of Vecs (naive linear scan):

#![allow(unused)]
fn main() {
 */

#[allow(dead_code)]
struct MyHashSetLinkedList {
    buckets: Vec<Vec<i32>>,
}

#[allow(dead_code)]
impl MyHashSetLinkedList {
    // time O(1), space O(n)
    pub fn new() -> Self {
        Self {
            buckets: vec![Vec::new(); 10_000],
        }
    }

    fn hash(key: i32) -> usize {
        key as usize % 10_000
    }

    // time O(k), space O(1)
    pub fn add(&mut self, key: i32) {
        let idx = Self::hash(key);
        if !self.buckets[idx].contains(&key) {
            self.buckets[idx].push(key);
        }
    }

    // time O(k), space O(1)
    pub fn remove(&mut self, key: i32) {
        let idx = Self::hash(key);
        if let Some(i) = self.buckets[idx].iter().position(|&x| x == key) {
            self.buckets[idx].remove(i);
        }
    }

    // time O(k), space O(1)
    pub fn contains(&self, key: i32) -> bool {
        let idx = Self::hash(key);
}

Bitset (not viable for arbitrary i32 — assumes non-negative keys within a fixed upper bound):

#![allow(unused)]
fn main() {
        self.buckets[idx].contains(&key)
    }
}

#[allow(dead_code)]
struct MyHashSetBitset {
    set: Vec<u32>,
}

#[allow(dead_code)]
impl MyHashSetBitset {
    // time O(1), space O(n)
    pub fn new() -> Self {
        Self {
            set: vec![0; 31251],
        }
    }

    fn get_mask(key: i32) -> u32 {
        1 << (key % 32)
    }

    // time O(1), space O(1)
    pub fn add(&mut self, key: i32) {
        self.set[key as usize / 32] |= Self::get_mask(key);
    }

    // time O(1), space O(1)
    pub fn remove(&mut self, key: i32) {
        if self.contains(key) {
            self.set[key as usize / 32] ^= Self::get_mask(key);
        }
    }
}