Python LinkedList based Hashset
As we are limited by space, we need to bound the array to a fixed size and then try to built a logic that will try to group the keys in some way. For this probl
As we are limited by space, we need to bound the array to a fixed size and then try to built a logic that will try to group the keys in some way. For this problem, let\'s say we will be a simple hash function :\n```\nhash = key % size where key is the value to be inserted and size is the length of array\n```\nI am using prime number as the size of bucket array to reduce the number of hash collisions. As a prime number has only two factors i.e. 1 and itself, it can help reduce number of hash collisions \n\nWe would also need to represent hash group using some efficient data structure. There are two Data structures that I can think of:\n1. LinkedList\n2. Binary Search Tree\n\nIn Java, we have an iterator implementation using an [Entry](https://github.com/openjdk-mirror/jdk7u-jdk/blob/master/src/share/classes/java/util/HashMap.java#L687) class. I wanted to built something in similar lines to that in Python. So for this specific implementation, I chose to go with LinkedList. \n\n\n```\nclass MyHashSet:\n\n    def __init__(self):\n        self.mod = 789\n        self.buckets = [Bucket()] * self.mod\n\n    def __find_id(self, key):\n        return key % self.mod    \n    \n    def add(self, key: int) -> None:\n        id = self.__find_id(key)\n        self.buckets[id].insert(key)\n\n    def remove(self, key: int) -> None:\n        id = self.__find_id(key)\n        self.buckets[id].delete(key)\n\n    def contains(self, key: int) -> bool:\n        id = self.__find_id(key)\n        return bool(self.buckets[id].search(key))\n\nclass Node:\n    def __init__(self, val, next = None):\n        self.val = val\n        self.next = next\n\nclass Bucket:\n    def __init__(self):\n        self.head = Node(-1)        \n    \n    def insert(self, val):        \n        if not self.head.next:\n            self.head.next = Node(val)\n            return self.head.next\n        \n        curr = self.head.next                            \n        prev = self.head\n        while curr:\n            if curr.val == val:\n                return curr\n            prev = curr\n            curr = curr.next\n        \n        prev.next = Node(val)\n        return prev.next\n    \n    def delete(self, val):\n        if not self.head.next:\n            return False\n        \n        curr = self.head        \n        \n        while curr.next:\n            if curr.next.val == val:\n                curr.next = curr.next.next\n                return True\n            curr = curr.next\n        return False\n    \n    def search(self, val):                \n        curr = self.head.next                            \n        while curr:\n            if curr.val == val:\n                return curr\n            curr = curr.next\n        \n        return None\n\n```\n\n**T** = **O(N/K)** - where **N** is the range of values and **K** is the number of buckets\n\n**S** = **O(K + M)** - where **K** is number of buckets and **M** is number of unique keys\n\nThe BST implementation would have a much better Time complexity **O(log N/K)**.\n\n---\n\n***Please upvote if you find it useful***
['Python', 'Python3']