Java | Simple Solution | Linked List
Intuition\nUsing a simple array for storing the elements with thier value as index would be space inefficient. Therefore, we are using array of linked list. The
# Intuition\nUsing a simple array for storing the elements with thier value as index would be space inefficient. Therefore, we are using `array of linked list`. The basic idea behind using separate chaining is to store elements in an array, where each element is a linked list. This approach allows us to handle `collisions` by storing multiple elements that hash to the same index in the array. This reduces space complexity but at cost of time complexity.\n\n# Approach\nThe HashSet is implemented using an array of linked lists. Each index in the array represents a `hash bucket`, and each `linked list` in the bucket represents the `elements that hash to the same index`.\n\n### Add function\nWhen adding an integer, the code calculates the hash value of the `key modulo the size of the array` to determine the bucket index. If the bucket is empty, a new node is created and added to the bucket. If the bucket is not empty, the code traverses the linked list to check if the key already exists in the set. If not, a new node is added to the end of the linked list. \n\n### Remove function\nWhen removing an integer, the code traverses the linked list in the corresponding bucket to find the node with the matching key and removes it. \n\n### Contains function\nTo check if an integer is present, the code calculates the hash value of the key modulo the size of the array and traverses the linked list in the corresponding bucket to find the node with the matching key.\n\n---\n\n# Complexity\n### Space Compexity\nThe `space complexity` of the HashSet is $$O(hashsize)$$.\n\n### Time complexity\nThe `time complexity` of the Hashet is $$O({{N}\\over{hashsize}})$$ where `N is the range of the input`. Each bucket will have $${{N}\\over{hashsize}}$$ elements.\n\n# Code\n```\nclass MyHashSet {\n\n    class Node{\n        int val = 0;\n        Node next = null;\n        Node(int v, Node n){\n            val = v;\n            next = n;\n        }\n    }\n    int hash = 500;\n    Node[] set = new Node[hash];\n    MyHashSet() {\n        \n    }\n    \n    void add(int key) {\n        if(set[key%hash]==null)set[key%hash]=new Node(key,null);\n        else{\n            Node temp = set[key%hash];\n            if(temp.val==key)return;\n            while(temp.next!=null){\n                if(temp.val==key || temp.next.val==key)return;\n                temp=temp.next;\n            }\n            temp.next = new Node(key,null);\n        }\n    }\n    \n    void remove(int key) {\n        if(set[key%hash]!=null){\n            Node temp = set[key%hash];\n            if(temp.val==key){\n                set[key%hash]=temp.next;\n                return;\n            }\n            while(temp.next!=null){\n                if(temp.next.val==key){\n                    temp.next = temp.next.next;\n                    return;\n                }\n                temp=temp.next;\n            }\n        }\n    }\n    \n    boolean contains(int key) {\n        if(set[key%hash]!=null){\n            Node temp = set[key%hash];\n            while(temp!=null){\n                if(temp.val==key){\n                    return true;\n                }\n                temp=temp.next;\n            }\n        }\n        return false;\n    }\n}\n```
['Linked List', 'Hash Function', 'Java']