双重哈希实现HashMap时陷入无限循环，请求排查数学逻辑问题

问题背景 #

参考维基百科的双重哈希公式：

H(i, k) = (H1(k) + i*H2(k)) % size

其中：

• H1 使用Python内置的hash()函数
• H2 的实现为：

PRIME - (H1(k) % PRIME)

但程序运行后会随机陷入无限循环，无法遍历哈希表所有槽位。以下是极简复现代码（需设置环境变量PYTHONHASHSEED=12）：

EMPTY = object()

class DoubleHashingHashMap:
    def __init__(self):
        self.prime = 7
        self.size = 15
        self.slots = [EMPTY] * self.size

    def __setitem__(self, key, value):
        for idx in self.probing_squence(key):
            slot = self.slots[idx]
            if slot is EMPTY:
                self.slots[idx] = (key, value)
                break
            elif isinstance(slot, tuple):
                k, v = slot
                if k == key:
                    self.slots[idx] = (key, value)
                    break

    def probing_squence(self, key):
        h1 = self.hash_func1(key) % self.size
        h2 = self.hash_func2(key) % self.size
        i = 1
        while True:
            yield (h1 + i*h2) % self.size
            i += 1

    def hash_func1(self, item):
        return hash(item)

    def hash_func2(self, item):
        return self.prime - (self.hash_func1(item) % self.prime)

hashmap = DoubleHashingHashMap()
for i in range(8):
    hashmap[str(i)] = i
print("8 items added.")
print("Going into the infinite loop when adding 9th item(which is 8)...")
hashmap["8"] = 8
print("This line can't be reached.")

核心数学逻辑错误 #

1. 探测序列跳过了初始哈希槽位 #

你的probing_squence方法中，i从1开始，直接跳过了H1(k) % size对应的初始槽位。当这个初始槽位为空时，代码会跳过它去探测后续位置；而当初始槽位已被占用，且后续探测序列陷入循环时，就会无限遍历重复的槽位，永远找不到空槽。

2. H2与哈希表size不保证互质 #

双重哈希的关键要求是：H2(k)必须与哈希表的size互质（即两者的最大公约数GCD为1），这样探测序列才能遍历哈希表的所有槽位。

你的实现中：

• size是15（质因数为3、5）
• H2的计算结果是PRIME - (H1(k) % PRIME)，这里PRIME=7。如果H2的结果是size的因数或倍数（比如假设PRIME选5，可能出现H2=5），就会导致GCD(H2,15)≠1，此时探测序列只能遍历size/GCD个槽位，当这些槽位都被占用时，就会无限循环。

在你的测试用例中，key为"8"时：

• hash("8") %7 = 0，因此H2=7-0=7
• 7和15的GCD是1，理论上可以遍历所有槽位，但因为跳过了初始槽位，而初始槽位已被占用，后续探测序列循环时无法覆盖到剩余的空槽，最终触发无限循环。

修正方案 #

方案1：修正探测序列的起始i值 #

让i从0开始，先返回初始哈希槽位：

def probing_squence(self, key):
    h1 = self.hash_func1(key) % self.size
    h2 = self.hash_func2(key) % self.size
    i = 0
    while True:
        yield (h1 + i*h2) % self.size
        i += 1

方案2：确保H2与size互质 #

可以调整H2的实现，保证其结果与size互质：

import math

def hash_func2(self, item):
    h1_mod = self.hash_func1(item) % self.prime
    h2 = self.prime - h1_mod
    # 确保h2与size互质
    while math.gcd(h2, self.size) != 1:
        h2 += 1
    return h2

另外，哈希表的size最好选择质数，这样更容易保证H2与size互质，比如把size设为17而非15，能减少此类问题的发生。

内容的提问来源于stack exchange，提问作者S.B