Real Python Solution, no cheating, open addressing
A lot of people don\'t follow the rules and aren\'t interested in learning.  This implementation was based on some data structures concepts and what I\'ve read 
A lot of people don\'t follow the rules and aren\'t interested in learning.  This implementation was based on some data structures concepts and what I\'ve read about Python\'s dict implementation.\n\nThe underlying structure that my hash set uses is a list.  The list simply contains a key at the index the key is hashed to, unless there are multiple keys at the same index (ie a collision). More on that later...\n\nMy hashset is designed to use a limited amount of memory, but expands itself by a factor of 2 when the load factor (size divided by array spots) exceeds 2/3.  This will allow for O(1) operations on average.  The downside to this is that every time the hashset doubles, it has to create a new list and rehash every element which takes O(n) each time.  The average time will be O(1) for each add call as the cost of rehashing the set is *amortized* over the calls.\n\nOpen addressing and chaining each have their own advantages and disadvantages.  I\'m not going to explain the nuances of the methods, but know that chaining hash sets/tables have the head of a linked list of keys in each array spot, while open addressing just moves the key to an empty index.\n\nI used open addressing for this problem.  If we add an element that is hashed to the same index as another key, then we apply a secondary operation on the index until we find an empty spot (or a previously removed spot).  This is called double hashing.  The formula I used is similar to that of the Python dict implementation, but without the perturb part.  This is better than linear probing since the hash function (which just mods the key by the capacity of the list) is likely to fill contiguous array spots and double hashing makes the probability of finding an empty spot more uniform in those cases than linear probing.\n\nFor removing, the removed element is replaced by a tombstone so that the contains function won\'t get messed up when the path to an existing element has an empty spot in it, causing the contains function to return false.  The add function will know that tombstones are able to be replaced by new elements.\n\n```\nclass MyHashSet(object):\n\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.capacity = 8\n        self.size = 0\n        self.s = [None]*8\n        self.lf = float(2)/3\n        \n    def myhash(self, key): # can be modified to hash other hashable objects like built in python hash function\n        return key%self.capacity\n        \n\n    def add(self, key):\n        """\n        :type key: int\n        :rtype: void\n        """\n        if float(self.size)/self.capacity >= self.lf:\n            self.capacity <<= 1\n            ns = [None]*self.capacity\n            for i in range(self.capacity >> 1):\n                if self.s[i] and self.s[i] != "==TOMBSTONE==":\n                    n = self.myhash(self.s[i])\n                    while ns[n] is not None:\n                        n = (5*n+1)%self.capacity\n                    ns[n] = self.s[i]\n            self.s = ns\n        h = self.myhash(key)\n        while self.s[h] is not None:\n            if self.s[h] == key:\n                return\n            h = (5*h + 1) % self.capacity\n            if self.s[h] == "==TOMBSTONE==":\n                break\n        self.s[h] = key\n        self.size += 1\n        \n        \n\n    def remove(self, key):\n        """\n        :type key: int\n        :rtype: void\n        """\n        h = self.myhash(key)\n        while self.s[h]:\n            if self.s[h] == key:\n                self.s[h] = "==TOMBSTONE=="\n                self.size -= 1\n                return\n            h = (5*h+1)%self.capacity\n        \n\n    def contains(self, key):\n        """\n        Returns true if this set contains the specified element\n        :type key: int\n        :rtype: bool\n        """\n        h = self.myhash(key)\n        while self.s[h] is not None:\n            if self.s[h] == key:\n                return True\n            h = (5*h + 1)%self.capacity\n        return False\n```
[]