class Entry:
	
	#Constructor, Time O(1), Space O(1)
    def __init__(self, key, val) :
        self.key = key
        self.value = val
	
    #Check equality of entry, compare value not object, Time O(1), Space O(1)
    def equals(self, entry):
        if str(self.key) != str(entry.key) :
            return False
        return str(self.value) == str(entry.value)
	
    #Override, Time O(1), Space O(1)
    def __str__(self):
        return "(" + str(self.key) + ", " + str(self.value) + ")"
	
class HashTable :

	#Constructor, Time O(1), Space O(1)
    def __init__(self,capacity) :
        self.maxSize = capacity
        self.buckets = [None]*(self.maxSize)	
	
    #Calculate hashcode by key, Time O(1), Space O(1)
    def hashFunc(self, key) :
        return int(key)  % self.maxSize
	
    #Add an entry, Time O(1), Space O(1)
    def put(self, key, value) :
        x = self.hashFunc(key)
        if self.buckets[x] == None :
            self.buckets[x] = []
        list = self.buckets[x]
        entry = Entry(key, value)
        list.append(entry)

	
	#Return value by key, Time O(n), Space O(1), n is max length of list in bucket
    def get(self, key) :
        x = self.hashFunc(key)
        if self.buckets[x] == None : 
            return None
        list = self.buckets[x]
        for entry in list:
            if str(entry.key) == str(key) : 
                return entry.value
        return None		
	
	#Delete all entries by key, Time O(n), Space O(n), n is max length of list in bucket
    def delete(self, key) :
        x = self.hashFunc(key)
        if self.buckets[x] == None:
            return
        list = self.buckets[x]
        list2 = []
        for entry in list:            
            if str(entry.key) != str(key):
                list2.append(entry)
        self.buckets[x] = None if  len(list2) == 0 else list2  

    #Print the whole hash table, Call printList, Time O(m*n), Space O(1), 
    #m is size of buckets, n is max list size 
    def print(self) :
    	for i in range(0 , self.maxSize) :    		
    		list = self.buckets[i]
    		if list != None:
    			self.printList(list)
    	
    #Print list in one bucket, Time O(n), Space O(1), n is list size 
    def printList(self, list) :
        if len(list) == 0:
            return
        for entry in list:
            print(str(entry) , end =" ")
        print()
   
    #Return length of hash table,  Time O(m), space O(1), m is bucket max size
    def size(self) :
        length = 0
        for i in range(0, self.maxSize):    		
            list = self.buckets[i]
            if list != None:
                length += 1
        return length

size = 10
table = HashTable(size)
table.put(1, "1")
table.put(2, "2")
table.put(2, "5")
table.put(4, "23")
table.put("22", "9")
print("The HashTable: ")
table.print()
print("The size: " + str(table.size()))

#Get
key = 22
print("Get value of " + str(key) + ": " + str(table.get(key)))
k1 = 8
print("Get value of " + str(k1) + ": " + str(table.get(k1)))

#update
table.put(3, "4")	
print("After update 3")
table.print()
print("The size: " + str(table.size()))

#Delete
table.delete(key)
print("After delete key " + str(key))
table.print()
print("The size after delete: " + str(table.size()))