采用双重哈希冲突解决的哈希表出现无限循环问题求助

阿华AIGC实验室

2026-5-29

嘿，我找到你这个哈希表无限循环的问题啦！

你的双重哈希实现里，第二个哈希函数返回的步长有时候会和哈希表大小maxsize不互质，导致探测序列只能遍历部分槽位——当这些槽位被占满但表还没满时，插入操作就会陷入死循环，一直在重复访问已占用的位置。

问题根源

举个具体的例子就能明白：
假设maxsize=10（偶数），primeSize=7（小于10的最大质数）。如果某个key的hashVal%primeSize=1（奇数），那step=7-1=6（偶数）。6和10的最大公约数是2，所以探测序列只会访问偶数位置：hash1 → hash1+6 → hash1+2 → hash1+8 → hash1+4 → hash1，无限循环。当所有偶数位置都被占了，但奇数位置还空着时，插入就会卡在这里，永远找不到空槽位。

这就是为什么你插入到一半就停滞的原因——刚好遍历完了步长能覆盖的所有槽位，但表还有剩余空间，却永远访问不到。

修复方案

给你两种可靠的修复方式，选哪种都可以：

方案1：确保步长与maxsize互质

修改myhash2，保证当maxsize是偶数时，步长一定是奇数（奇数和偶数天然互质）：

private int myhash2(string key) {
    int hashVal = key.GetHashCode();
    hashVal %= maxsize;
    if (hashVal < 0) hashVal += maxsize;
    
    int step = primeSize - (hashVal % primeSize);
    
    // 若maxsize是偶数，强制步长为奇数
    if (maxsize % 2 == 0 && step % 2 == 0) {
        step = (step + 1) % maxsize;
        // 防止步长变为0（当前逻辑下step最小为1，加1后不会到0，保险起见加判断）
        if (step == 0) step = 1;
    }
    
    return step;
}

方案2：使用标准双重哈希实现

这是更通用的做法，不需要依赖primeSize，直接让步长满足与maxsize互质的要求：

// 可以删掉getPrime()和primeSize相关的所有代码
private int myhash2(string key) {
    int hashVal = key.GetHashCode();
    hashVal %= maxsize;
    if (hashVal < 0) hashVal += maxsize;
    
    // 标准双重哈希步长：1 + (hashVal % (maxsize - 1))
    // 保证步长与maxsize互质：
    // - 若maxsize是质数，步长范围1~maxsize-1，都与maxsize互质
    // - 若maxsize是2的幂，步长是奇数，与2的幂互质
    return 1 + (hashVal % (maxsize - 1));
}