在Python中使用二次探测的字符串散列

Question

我试图用Python编写一个函数，它将字符串添加到哈希表中，并用二次探测解决任何冲突，而不导入数学。在

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)

我的问题是，我总是得到索引器错误：列表索引超出范围，我确信问题出在else块中，但是我似乎找不到解决方法。感谢任何帮助，谢谢。在

Answer 1

在不了解hashString()函数的内部工作原理的情况下，我假设您正在获取一个字符串并将其转换为给定长度的散列。如果这是真的，else语句将设置一个超出哈希表边界的值（同样，这只是一个猜测，因为您没有给出哈希表的任何内部工作方式）。在

发生这种情况的原因是，当您：

slot = slot + (collisions**2)%len(hashTable)

根据设计，哈希通常是一个给定的长度，而您只是让它变长，因此超出了hashTable的界限。在

你需要修改整个新的槽位以防止它越界。在

slot = (slot + (collisions**2))%len(hashTable)