705. Design HashSet

Problem 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

Examples:

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⁶
• At most 10⁴ calls will be made to add, remove, and contains

Python Solution

class MyHashSet:
    def __init__(self):
        self.size = 1000
        self.buckets = [[] for _ in range(self.size)]
    
    def _hash(self, key):
        return key % self.size
    
    def add(self, key: int) -> None:
        bucket = self.buckets[self._hash(key)]
        if key not in bucket:
            bucket.append(key)
    
    def remove(self, key: int) -> None:
        bucket = self.buckets[self._hash(key)]
        if key in bucket:
            bucket.remove(key)
    
    def contains(self, key: int) -> bool:
        bucket = self.buckets[self._hash(key)]
        return key in bucket

Implementation Notes:

• Uses chaining with linked lists for collision resolution
• Time complexity: O(1) average case, O(n) worst case
• Space complexity: O(n) where n is the number of elements

Java Solution

class MyHashSet {
    private static final int SIZE = 1000;
    private List[] buckets;
    
    public MyHashSet() {
        buckets = new List[SIZE];
        for (int i = 0; i < SIZE; i++) {
            buckets[i] = new ArrayList<>();
        }
    }
    
    private int hash(int key) {
        return key % SIZE;
    }
    
    public void add(int key) {
        int index = hash(key);
        if (!buckets[index].contains(key)) {
            buckets[index].add(key);
        }
    }
    
    public void remove(int key) {
        int index = hash(key);
        buckets[index].remove(Integer.valueOf(key));
    }
    
    public boolean contains(int key) {
        int index = hash(key);
        return buckets[index].contains(key);
    }
}

C++ Solution

class MyHashSet {
private:
    static const int SIZE = 1000;
    vector> buckets;
    
    int hash(int key) {
        return key % SIZE;
    }
    
public:
    MyHashSet() : buckets(SIZE) {}
    
    void add(int key) {
        int index = hash(key);
        if (find(buckets[index].begin(), buckets[index].end(), key) == buckets[index].end()) {
            buckets[index].push_back(key);
        }
    }
    
    void remove(int key) {
        int index = hash(key);
        buckets[index].remove(key);
    }
    
    bool contains(int key) {
        int index = hash(key);
        return find(buckets[index].begin(), buckets[index].end(), key) != buckets[index].end();
    }
};

JavaScript Solution

class MyHashSet {
    constructor() {
        this.size = 1000;
        this.buckets = Array(this.size).fill().map(() => []);
    }
    
    hash(key) {
        return key % this.size;
    }
    
    add(key) {
        const bucket = this.buckets[this.hash(key)];
        if (!bucket.includes(key)) {
            bucket.push(key);
        }
    }
    
    remove(key) {
        const bucket = this.buckets[this.hash(key)];
        const index = bucket.indexOf(key);
        if (index !== -1) {
            bucket.splice(index, 1);
        }
    }
    
    contains(key) {
        return this.buckets[this.hash(key)].includes(key);
    }
}

C# Solution

public class MyHashSet {
    private const int SIZE = 1000;
    private List[] buckets;
    
    public MyHashSet() {
        buckets = new List[SIZE];
        for (int i = 0; i < SIZE; i++) {
            buckets[i] = new List();
        }
    }
    
    private int Hash(int key) {
        return key % SIZE;
    }
    
    public void Add(int key) {
        int index = Hash(key);
        if (!buckets[index].Contains(key)) {
            buckets[index].Add(key);
        }
    }
    
    public void Remove(int key) {
        int index = Hash(key);
        buckets[index].Remove(key);
    }
    
    public bool Contains(int key) {
        int index = Hash(key);
        return buckets[index].Contains(key);
    }
}

Implementation Notes:

• Uses chaining with lists for collision resolution
• Simple modulo-based hash function
• Time complexity: O(1) average case, O(n) worst case
• Space complexity: O(n) where n is the number of elements