Problem Statement:

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]

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.

Solution:

Here we use modulo operator as the hashing function and M is chosen to be a big enough prime.

 
class Node {
    public:
    int val;
    Node *next;
    Node(int v, Node *n){val=v;next=n;}
};
class MyHashSet {
public:
    vector<Node *>nodes;
    int N;
    MyHashSet(int n=99991) {
        nodes = vector<Node *>(n,NULL);
        N = n;
    }
    
    void add(int key) {
        if (contains(key)) return;
        int h = key%N;
        if (nodes[h]==NULL) nodes[h]=new Node(key,NULL);
        else
        {
            Node *curr=nodes[h];
            while (curr->next!=NULL) curr=curr->next;
            curr->next=new Node(key,NULL);
        }
    }
    
    void remove(int key) {
        if (!contains(key)) return;
        int h=key%N;
        if (nodes[h]->val==key) 
        {
            nodes[h]=nodes[h]->next;
            return;
        }
        Node *curr=nodes[h];
        while (curr->next!=NULL && curr->next->val!=key) curr=curr->next;
        curr->next = curr->next->next;
    }
    
    bool contains(int key) {
        int h=key%N;
        if (nodes[h]==NULL) return false;
        Node *curr=nodes[h];
        while (curr!=NULL) 
        {
            if (curr->val==key) return true;
            curr=curr->next;
        }
        return false;
    }
};

/**
 * Your MyHashSet object will be instantiated and called as such:
 * MyHashSet* obj = new MyHashSet();
 * obj->add(key);
 * obj->remove(key);
 * bool param_3 = obj->contains(key);
 */