class MyHashSet:
def __init__(self):
self.capacity = 8
self.size = 0
self.set = [None]*self.capacity
self.lf = 2/3 # load factor
def myhash(self,key):
return key%self.capacity
def add(self, key: int) -> None:
# if size of self.set has reached to load factor of the capacity, double size of set, rehash each key in prev set
if self.size/self.capacity >= self.lf:
self.capacity <<= 1
nset = [None]*self.capacity
for k in self.set:
if k and k != "==TOMBSTONE==":
nhash = self.myhash(k)
while nset[nhash] is not None:
nhash = (nhash *5+1)%self.capacity
nset[nhash] = k
self.set = nset
h = self.myhash(key)
while self.set[h] is not None:
if self.set[h] == key: # when there is key in the set, do nothing
return
h = (h*5+1)%self.capacity
if self.set[h] =="==TOMBSTONE==": # fill out slot that removed before
break
self.set[h] = key
self.size += 1
def remove(self, key: int) -> None: # there is no cases where target key for removal is not existant
h = self.myhash(key)
while self.set[h] is not None:
if self.set[h] == key:
self.set[h] = "==TOMBSTONE=="
self.size -= 1
return
# if self.set[h] == "==TOMBSTONE==":
# return
h = (5*h+1)%self.capacity
def contains(self, key: int) -> bool:
h = self.myhash(key)
while self.set[h] is not None:
if self.set[h] == key:
return True
# if self.set[h] == "==TOMBSTONE==": # note, there can be "==TOMBSTONE==" betweent each key hashing
# return False
h = (h*5+1)%self.capacity
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)
# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)