String hashing with quadratic probing, in Python

Question

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.

Answer 1

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)