Below is my SimpleHashTable
class.
The put(self, key)
method should determines where the key is placed in the hashtable when a collision occurs (i.e., calculates the next available index position). Linear probing will be used for collision resolution. I am to do the the following steps:
Invoke the get_hash_index(key)
to get the original index position.
Use a while loop to get the next available position.
Store the key into the hashtable according to the available index position.
class SimpleHashTable: def __init__(self, size=7): self.size = size self.slots = [None] * self.size def __str__(self): return "{}".format(self.slots) def get_hash_index(self, key): self.key = key self.hkey = key % self.size return self.hkey def new_hash_code(self, index): count = 0 while count < self.size: if self.slots[index] == None: return index index += 1 count += 1 return None def put(self, key): #issue here code = self.get_hash_index(key) if self.slots[code] != None: code = self.new_hash_code(code) self.slots[code] = key def __len__(self): count = 0 for item in self.slots: if item != None: count += 1 return count
Test:
my_hash_table = SimpleHashTable(13) my_hash_table.put(12) my_hash_table.put(24) my_hash_table.put(36) my_hash_table.put(48) my_hash_table.put(31) my_hash_table.put(77) my_hash_table.put(43)
Output getting:
***Error*** Traceback (most recent call last): File "__tester__.python3", line 87, in <module> my_hash_table.put(77) File "__tester__.python3", line 26, in put code = self.new_hash_code(code) File "__tester__.python3", line 17, in new_hash_code if self.slots[index] == None: IndexError: list index out of range
Advertisement
Answer
The error is in the new_hash_code
method. Your current code starts from the current value of index, but increments it without testing it against self.size
. You should simply reset it to 0 when reaching the top:
def new_hash_code(self, index): count = 0 while count < self.size: if index == self.size: # prevent out of range error... index = 0 if self.slots[index] == None: return index index += 1 count += 1 return None