https://leetcode.com/problems/design-hashset/

Approach

Use single array (the troll way). Create a table one more than the MAX_INPUT for the key and use a simple key % TABLE_SIZE to hash the key.

Solution

1class MyHashSet {
2public:
3    bool *hashtable;
4    int SIZE = 1000001;
5    /** Initialize your data structure here. */
6    MyHashSet() {
7        hashtable = new bool[SIZE];
8        fill(hashtable, hashtable + SIZE, false);
9    }
10    
11    void add(int key) {
12        hashtable[key%SIZE] = true;
13    }
14    
15    void remove(int key) {
16        hashtable[key%SIZE] = false;
17    }
18    
19    /** Returns true if this set contains the specified element */
20    bool contains(int key) {
21        return hashtable[key%SIZE];
22    }
23};

Time Complexity

O(1)

Space Complexity

O(N)

Better design?

Using a single array is perfectly fine from a CP programmer view in my opinion, but if you're tackling this question as for preparing a coding interview, then you might need to comp up with a better solution.

1. BST solution - https://leetcode.com/problems/design-hashset/discuss/179164/C%2B%2B-97.97-without-a-massive-array-or-using-a-map-BST
2. 3 different approaches - https://leetcode.com/problems/design-hashset/discuss/773006/C%2B%2B-3-Approaches

Basic Hash Implementation

1class MyHashSet {
2private:
3    int prime;
4    vector<list<int>> table;
5    
6    int hash(int key) {
7        return key % prime;
8    }
9    
10    list<int>::iterator search(int key) {
11        int h = hash(key);
12        return find(table[h].begin(), table[h].end(), key);
13    }
14    
15public:
16    /** Initialize your data structure here. */
17    MyHashSet() : prime(10007), table(prime) {}
18    
19    void add(int key) {
20        int h = hash(key);
21        if(!contains(key))
22            table[h].push_back(key);
23    }
24    
25    void remove(int key) {
26        int h = hash(key);
27        auto it = search(key);
28        if (it != table[h].end())
29            table[h].erase(it);
30    }
31    
32    /** Returns true if this set contains the specified element */
33    bool contains(int key) {
34        int h = hash(key);
35        return search(key) != table[h].end();
36    }
37};

Time Complexity

O(N), average O

Space Complexity

O(N)