I am trying to write a function in Python, that will add strings to a hash table and resolve any collisions with quadratic probing, without importing math.
def addString(string, hashTable):
collisions = 0
stop = False
slot = (hashString(string, len(hashTable)))
while not stop:
if hashTable[slot] == None:
hashTable[slot] = string
stop = True
else:
slot = slot + (collisions**2)%len(hashTable)
collisions = collisions + 1
print('collisions: ', collisions)
My problem is that I keep getting IndexError: list index out of range and I am certain the problem lies in the else block however, I can't seem to find a solution for it. Any help appreciated, thanks.
Without knowing the inner-workings of your hashString()
function, I assume you are taking a string and converting it into a hash of a given length. If that is true, your else statement sets a value that is out of bounds of your hashTable (again, just a guess since you don't give any inner workings of your hashTable).
The reason why this is happening is because you are actually making slot
larger than the bounds when you:
slot = slot + (collisions**2)%len(hashTable)
By design, hashes are usually a given length, and you are just making it longer, thus out of bounds of your hashTable
.
You need to mod the entire new slot to keep it from going out of bounds.
slot = (slot + (collisions**2))%len(hashTable)