Linked List Approach | Python / JS Solution
Hello Tenno Leetcoders,\n\nFor this problem, we want to implement\xA0MyHashSet\xA0class without any built in hash table libraries:\n\n- void add(key)\xA0Inserts
Hello **Tenno Leetcoders**,\n\nFor this problem, we want to implement\xA0`MyHashSet`\xA0class without any built in hash table libraries:\n\n- `void add(key)`\xA0Inserts the value\xA0`key`\xA0into the HashSet.\n- `bool contains(key)`\xA0Returns whether the value\xA0`key`\xA0exists in the HashSet or not.\n- `void remove(key)`\xA0Removes the value\xA0`key`\xA0in the HashSet. If\xA0`key`\xA0does not exist in the HashSet, do nothing.\n\n### Explanation \n\nAs this problem states, we should not use any built in hash tables, so therefore, how can we create `MyHashSet` class as efficient as possible as we also think about handling collisions?\n\n### Collision handling\n\nCollisions occur when two different `keys` maps to the same hash value. Since we are not able to use any built in hash tables, we can use a `fixed-size array` to help use store our `keys`. When the number of `keys` exceeds the size of the array, collisions are bound to happen. So, if thats the case, how can we overcome this issue?\n\nTo avoid and handle collision as much as possible we can implement `Linked list` for each index in our `buckets`.  Using a `linked list` approach allows us to handle collision by `chaining` the `keys` that `map` to the same `hash value`. Thus, instead of overwriting the existing key with new key, we can append the new key to the `linked list` of its corresponding index \n\nAlso, to avoid collision as much as possible, we can set a `prime number` as a starting size for our HashSet. By using a prime number as the current size, we can achieve a more uniform distribution of keys across our `buckets` so that we can reduce the likelihood of collisions happening. Using prime number doesn\'t guarantee collision-free behavior but it can help mitigate collisions. \n\n## `MyHashSet`\xA0class\n\n#### Time Complexity: O(n)\n#### Space Complexity: O(n)\n\n### __init__(self) \n\nInitialize our HashSet by creating a fixed size array with the size of `997`\n\nInitialize a array called `buckets` and set all element to `None` as no keys have yet been inserted\n\n### hash(self, key: int) -> int\n\nA helper method, which takes an integer key, returns the hahs value for that key and determine the index in the array where the key will be stored. Using modulo operator, we can calculate the hash value as `key % self.size`, where `self.size` is the size of our linked list array with a fixed size of `997`\n\n### def get_bucket_and_node(self, key: int)\n\nTake a key as input and returns the index and the bucket at that index and also calculate the index based on the key using the helper method `hash`\n\n### add(self, key: int) -> None\n\n#### Time Complexity: O(1) (average) , O(n) (worse)\n#### Space Complexity: O(1)\n\nAdd keys into the HashSet and also calculate the hash value of the key using the helper method `hash`. \n\nIf the linked list at the calculated index is empty, we have yet inserted any keys in this index position. In this case, a new node with the key will be created and inserted as the head of the linked list for that index\n\nIf the linked list is not empty, we traverse the linked list and check if the key exist. \n\n    - If so, we do not insert it as HashSet should have unique keys\n\n    - If not, createa new node with the key and append it to the end of the linked list\n    \n### remove(self, key: int) -> None\n\n#### Time Complexity: O(1) (average) , O(n) (worse, when collisions happen)\n#### Space Complexity: O(1)\n\nRemove keys from the HashSet and also calculate the hash value of the key using the helper method `hash` \n\nIf the linked list at the calculated index is empty, we have yet inserted any keys in this index position, which represents the key does not exist in the HashSet, Thus, we can return early without performing any other operations \n\nIf the head of the linked list is at the calculated index which contains the key, update the head to skip the first node, removing it from the linked list\n\nIf the head is not found at the head, we traverse the linked list to find the node with the key. Once found:\n\n    - Update the previous node with next pointer to skip the node containing the keys, to remove it from linked list\n\n\n### contains(self, key: int) -> bool\n\n#### Time Complexity: O(1)\n#### Space Complexity: O(1)\n\nCheck if the key exist in HashSet and also calculate the hash value of the key using the helper method `hash`\n\nTraverse the linked list at its calculated index position to search for the key\n\nIf key is found in the linked list, it will return `True`. Else, return `False`\n\n# Code\n\n**Python**\n\n```\nclass ListNode:\n    def __init__(self, key):\n        self.key = key\n        self.next = None\nclass MyHashSet:\n\n    def __init__(self):\n        self.size = 997\n        self.buckets = [None] * self.size\n    \n    def hash(self, key: int) -> int:\n        return key % self.size\n\n    def get_bucket_and_node(self, key: int):\n        index = self.hash(key)\n        bucket = self.buckets[index]\n        return index, bucket\n\n    def add(self, key: int) -> None:\n        index, bucket = self.get_bucket_and_node(key)\n        if not self.buckets[index]:\n            self.buckets[index] = ListNode(key)\n        else: \n            current = bucket\n            while current:\n                if current.key == key: return\n                if not current.next: break\n                current = current.next\n\n            current.next = ListNode(key)\n\n    def remove(self, key: int) -> None:\n        index, bucket = self.get_bucket_and_node(key)\n        if not self.buckets[index]: return\n        if self.buckets[index].key == key:\n            self.buckets[index] = self.buckets[index].next\n            return\n        current = bucket\n        while current.next:\n            if current.next.key == key:\n                current.next = current.next.next\n                return\n            current = current.next\n        \n\n    def contains(self, key: int) -> bool:\n        _, bucket = self.get_bucket_and_node(key)\n        current = bucket\n        while current:\n            if current.key == key:\n                return True\n            current = current.next\n        return False\n```\n\n**JavaScript**\n```\nvar ListNode = function(key) {\n    this.key = key\n    this.next = null\n};\n\nvar MyHashSet = function() {\n    this.size = 997\n    this.buckets = Array(this.size).fill(null)\n    \n};\n\nMyHashSet.prototype.hash = function(key){\n    return key % this.size\n}\n\nMyHashSet.prototype.getBucketAndNode = function(key){\n    let index = this.hash(key)\n    let bucket = this.buckets[index]\n    return {index, bucket}\n}\n\n/** \n * @param {number} key\n * @return {void}\n */\nMyHashSet.prototype.add = function(key) {\n    let {index, bucket} = this.getBucketAndNode(key)\n    if(!bucket){\n        this.buckets[index] = new ListNode(key)\n    }else{\n        let current = bucket\n        while(current){\n            if(current.key === key) return\n            if(!current.next) break\n            current = current.next\n        }\n\n        current.next = new ListNode(key)\n    }\n};\n\n/** \n * @param {number} key\n * @return {void}\n */\nMyHashSet.prototype.remove = function(key) {\n    let {index, bucket} = this.getBucketAndNode(key)\n    if(!bucket) return\n    if(bucket.key === key){\n        this.buckets[index] = bucket.next\n        return\n    }\n    let current = bucket\n    while(current.next){\n        if(current.next.key === key){\n            current.next = current.next.next\n            return\n        }\n\n        current = current.next\n    }\n};\n\n/** \n * @param {number} key\n * @return {boolean}\n */\nMyHashSet.prototype.contains = function(key) {\n    let { bucket} = this.getBucketAndNode(key)\n    let current = bucket\n    while(current){\n        if(current.key === key) return true\n        current = current.next\n    }\n    return false\n};\n\n/** \n * Your MyHashSet object will be instantiated and called as such:\n * var obj = new MyHashSet()\n * obj.add(key)\n * obj.remove(key)\n * var param_3 = obj.contains(key)\n */\n```\n \n***Warframe\'s Darvo wants you to upvote this post  \uD83D\uDE4F\uD83C\uDFFB \u2764\uFE0F\u200D\uD83D\uDD25***\n\n![image](https://assets.leetcode.com/users/images/814f5668-c966-46d7-ba42-e5435c4c1761_1675302761.3081913.gif)
['JavaScript']