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

Question

我正在尝试在 Python 中编写一个函数，它将字符串添加到散列 table 并解决与二次探测的任何冲突，而无需导入数学。

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: list index out of range 我确定问题出在 else 块上，但是我似乎找不到解决方案。感谢任何帮助，谢谢。

Answer 1

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

发生这种情况的原因是因为您实际上使 slot 大于界限，当您：

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

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

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

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

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

String hashing with quadratic probing, in Python

python

hashtable

quadratic-probing