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/excepttrick 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)