I implemented a Python Hash Table using only lists. Here is my implementation:
class HashTable: # Initialize the table with a fixed size of 54 slots def __init__(self): self.Table = [None] * 54 def _get_value(self, key): #This is my hash function. # It finds the hash of every string. total % 54 total = hash(key) return total % 54 def insert(self, key): val = self._get_value(key) col = False #Collision bool index = 0 if self.Table[val] == None: #Empty slot - turn into list of keys to avoid extra cases self.Table[val] = [key] else: #Collision - append self.Table[val].append(key) col = True index = len(self.Table[val]) - 1 return val, col, index def delete(self, key): val = self._get_value(key) if self.Table[val] == None: #Deleting an unexisting element return -1, 0 elif key in self.Table[val]: #This is the O(n) part of the hashtable index = self.Table[val].index(key) self.Table[val].remove(key) return val, index else: # No match was found in list, element does not exist return -1, 0 def lookup(self, key): val = self._get_value(key) if self.Table[val] == None: return -1, 0 else: if key in self.Table[val]: index = self.Table[val].index(key) return val, index # No match was found in list, element does not exist return -1, 0 def clear(self): self.__init__()
I am using and returning some variables to keep track of collision, values, and indexes to print to the user.
I want to understand how I could improve this implementation - still using only lists (no sets for checking). From a time complexity perspective or even code design, how can I make this more efficient? What design choices were poorly made in my code? What can I improve in this to make it better?