[link](https://leetcode.com/problems/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]

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 <= 106
- At most 104 calls will be made to add, remove, and contains.
---

The ListNode class represents a node in a linked list. Each node has a key attribute that stores the integer value and a next attribute that points to the next node in the list.

The MyHashSet class is the main implementation of the hash set. It initializes a list of fixed size (10^4 in this case) with ListNode objects. The size of the list is chosen to balance the trade-off between memory usage and collision avoidance.

The add method adds an element to the hash set. It calculates the hash value of the key by taking the modulus of the key with the size of the set. It then traverses the linked list at the calculated index and checks if the key already exists. If the key is found, the method returns without making any changes. If the key is not found, it creates a new ListNode with the key and appends it to the end of the linked list.

The remove method removes an element from the hash set. Similar to the add method, it calculates the hash value of the key and traverses the linked list at the calculated index. If the key is found, it adjusts the pointers to skip the node containing the key, effectively removing it from the list.

The contains method checks if an element exists in the hash set. It calculates the hash value of the key and traverses the linked list at the calculated index. If the key is found, it returns True; otherwise, it returns False.

#### Solution 1

class ListNode:
    def __init__(self, key):
        self.key = key
        self.next = None
        
        
class MyHashSet:
    # No need to rehashing for this quesiton
    def __init__(self):
        self.set = [ListNode(0) for i in range(10 ** 4)]
        

    def add(self, key: int) -> None:
        index = key % len(self.set)
        cur = self.set[index]
        while cur.next:
            if cur.next.key == key:
                return
            cur = cur.next
        cur.next = ListNode(key)

    def remove(self, key: int) -> None:
        index = key % len(self.set)
        cur = self.set[index]
        while cur.next:
            if cur.next.key == key:
                cur.next = cur.next.next
                return
            cur = cur.next
            
        
    def contains(self, key: int) -> bool:
        index = key % len(self.set)
        cur = self.set[index]
        while cur.next:
            if cur.next.key == key:
                return True
            cur = cur.next

        return False


# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)
        

O(T): O(1)
O(S): O(N)