Hashtables Python put method showing IndexError

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

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

Advertisement

Answer