使用二次探测进行字符串哈希，在 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)

我的问题是我一直得到 IndexError：列出索引超出范围，我确定问题出在 else 块上，但是，我似乎找不到解决方案。任何帮助表示赞赏，谢谢。

Answer 1

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

发生这种情况的原因是，当您执行以下操作时，您实际上使slot大于边界：

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

根据设计，哈希通常是给定的长度，而您只是将其延长，因此超出了您的hashTable范围。

您需要修改整个新插槽以防止其越界。

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