Python Hash Table implemented using lists

Question

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?

Answer 1

Restructuring and micro-optimization

Hard-coded table size 54 is better defined as class constant:

T_SIZE = 54

Encapsulate the crucial list/table at least as protected property self._Table.

Calling self._get_value(key) and the condition if self._Table[val] == None are repeated in most crucial methods. To reduce that noisy repetition an additional method can be defined which will return a tuple of calculated value val and is_empty ("empty slot" flag):

def _check_value(self, key):
 val = self._get_value(key)
 is_empty = self._Table[val] is None
 return val, is_empty

It doesn't make sense to construct if ... else conditional if the 1st if branch return 's immediately.

Both delete and lookup methods, on existing item, will perform 2 access/lookup operations on self._Table[val]:

• key in self._Table[val]
• self._Table[val].index(key)

To reduce access operations there we can apply try/except trick and returning the needed result in each separate block. See the final implementation below:

class HashTable:
 T_SIZE = 54
 # Initialize the table with a fixed size
 def __init__(self):
 self._Table = [None] * HashTable.T_SIZE
 def _get_value(self, key):
 total = hash(key)
 return total % HashTable.T_SIZE
 def _check_value(self, key):
 val = self._get_value(key)
 is_empty = self._Table[val] is None
 return val, is_empty
 def insert(self, key):
 val, is_empty = self._check_value(key)
 col = False # Collision flag
 index = 0
 if is_empty: # Empty slot - turn into list of keys to avoid extra cases
 self._Table[val] = [key]
 else:
 self._Table[val].append(key) # Collision - append
 col = True
 index = len(self._Table[val]) - 1
 return val, col, index
 def delete(self, key):
 val, is_empty = self._check_value(key)
 if is_empty: # Deleting unexisting element
 return -1, 0
 try:
 index = self._Table[val].index(key)
 self._Table[val].remove(key)
 return val, index
 except ValueError: # No match was found in list, element does not exist
 return -1, 0
 def lookup(self, key):
 val, is_empty = self._check_value(key)
 if is_empty:
 return -1, 0
 try:
 index = self._Table[val].index(key)
 return val, index
 except ValueError: # No match was found in list, element does not exist
 return -1, 0
 def clear(self):
 self.__init__()

In case if _get_value method won't be used in standalone context - you may easily inline it into _check_value method.

Sample usage:

h = HashTable()
h.insert('abc')
h.insert('abc')
print(h.lookup('abc'))
print(h.lookup('1abc'))
print(h.delete('abc'))
print(h.delete('abc'))
print(h.delete('abc'))

The output (consecutively):

(8, 0)
(-1, 0)
(8, 0)
(8, 0)
(-1, 0)