如何将哈希表的线性探测转换为二次探测？Python代码修改求助

嘿，我完全懂你的困扰！你在把线性探测改成二次探测时犯了一个非常典型的错误——二次探测的偏移量是基于原始哈希位置来计算的，而不是每次叠加到当前的position上。

你之前的写法position = (position+(i+1)**2) % self.table_size会让探测路径变成：原始位置 → 原始位置+1 → 原始位置+1+4 → 原始位置+1+4+9... 这完全偏离了二次探测的逻辑（正确路径应该是原始位置+1²、原始位置+2²、原始位置+3²...）。

修正后的__setitem__函数 #

这里是调整后的代码，核心是先保存原始哈希位置，然后每次计算新位置时都基于原始位置加上平方偏移量：

def __setitem__(self, key, value):
    original_pos = self.hash_value(key)  # 保存原始哈希位置
    for i in range(self.table_size):
        # 基于原始位置计算当前探测位置：original_pos + i²（i从0开始，第一次冲突后i=1对应+1²）
        position = (original_pos + i**2) % self.table_size
        if self.array[position] is None:  # 找到空槽位
            self.array[position] = (key, value)
            self.count += 1
            return
        elif self.array[position][0] == key:  # 找到已存在的key，更新值
            self.array[position] = (key, value)
            return
    # 循环结束还没返回，说明表已满
    raise ValueError("Table is Full!")

关键细节解释 #

• 我们先把原始哈希值存在original_pos里，之后所有的探测位置都从这个基准点出发计算。
• 循环变量i从0开始：
  • 当i=0时，就是原始哈希位置，先检查这个位置是否可用；
  • 当i=1时，偏移量是1²，对应二次探测的第一个备选位置；
  • 当i=2时，偏移量是2²，对应第二个备选位置，以此类推。
• 这样就严格遵循了二次探测的规则：依次尝试N+1²、N+2²、N+3²...的位置（N是原始哈希位置）。

另外小提醒：二次探测的哈希表表大小最好是质数或者2的幂，这样能保证探测序列可以覆盖到表中的所有位置，避免出现永远找不到空槽的情况（当然你的代码里已经做了循环table_size次的限制，所以即使表大小不合适，最后也会抛出满表的异常）。

内容的提问来源于stack exchange，提问作者Sook Lim