[LeetCode] Design HashSet

Problem: 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:

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)

Approach: We will approach this problem same as we approached our previous problem of designing HashMap. We just will take array of LinkedList of int instead of LinkedList of Key, Value pair as here we just need to store an integer Rest of the things remains same.

Implementation in C#:

public class MyHashSet 

{

    public MyHashSet() 

    {

        this.size = 2069;

        this.buckets = new LinkedList<int>[2069];

    }

    

    public void Add(int key) 

    {

        int index = key % this.size;

        if (this.buckets[index] == null)

        {

            this.buckets[index] = new LinkedList<int>();

        }

        LinkedListNode<int> node = this.buckets[index].First;

        while(node != null)

        {

            if (node.Value == key)

            {

                return;

            }

            node = node.Next;

        }    

        this.buckets[index].AddFirst(key);

    }

    

    public void Remove(int key) 

    {

        int index = key % this.size;

        if (this.buckets[index] == null)

        {

            return;

        }

        LinkedListNode<int> node = this.buckets[index].First;

        while(node != null)

        {

            if (node.Value == key)

            {

                this.buckets[index].Remove(node);

                return;

            }

            node = node.Next;

        }

    }

    

    public bool Contains(int key) 

    {

        int index = key % this.size;

        if (this.buckets[index] == null)

        {

            return false;

        }        

        LinkedListNode<int> node = this.buckets[index].First;

        while(node != null)

        {

            if (node.Value == key)

            {

                return true;

            }

            node = node.Next;

        }

        return false;

    }

    

    LinkedList<int>[] buckets;

    int size;

}

Complexity: O(1) for all the operations.