为什么在不覆盖碰撞值时二次探测的实现会失败？

Question

我当前的 Quadratic Probing 实现会在发生碰撞时用新项目覆盖存储在当前索引处的项目。我插入了三个 Person 对象，这些对象通过使用姓氏作为键来存储。为了测试实现的冲突解决方案，它们都具有相同的姓氏 "Windmill"。

我需要实现来保留所有人员对象，但只是将它们移动到不同的索引而不是覆盖它们。

列表大小已设置为7，存储在变量"M"中，用于插入函数中的取模。

插入函数

@Override
public void put(String key, Person value) {
   int tmp = hash(key);
   int i, h = 0;

    for (i = tmp; keys[i] != null; i = (i + h * h++) % M) {
        collisionCount++;

        if (keys[i].equals(key))  { 
            values[i] = value;
            return; 
        } 
    }

    keys[i] = key;
    values[i] = value;
    N++;
}

哈希函数

private int hash(String key) {
    return (key.hashCode() & 0x7fffffff) % M;
}

获取函数

@Override
public List<Person> get(String key) {
    List<Person> results = new ArrayList<>();

    int tmp = hash(key);
    int i = hash(key), h = 0;

    while (keys[i] != null)
    {
        if (keys[i].equals(key))
            results.add(values[i]);

        i = (i + h * h++) % M;
    }   

    return results;
}

当我删除覆盖先前值的代码段时，索引 int 溢出并变成负数，导致程序崩溃。

Answer 1

你会溢出，因为你在对导致溢出的整数进行一些操作后 % M。您需要根据 modulo 操作属性 (https://en.wikipedia.org/wiki/Modulo_operation):

将 i = (i + h * h++) % M 替换为一些额外的操作

(a + b) mod n = [(a mod n) + (b mod n)] mod n.
ab mod n = [(a mod n)(b mod n)] mod n.

Answer 2

我认为您的代码有两个问题：

你没有检查（多）地图是否已满。实际上你想做 2 次检查：
- 检查是否 N==M（或者可能是某个更小的阈值，例如 M 的 90%）
- 使collisionCount成为一个局部变量，当它达到N时（不幸的是，为了避免某些病态情况，此检查也是必要的）

在这两种情况下，您都应该扩展存储区域并将旧数据复制到其中（重新插入）。仅此一项就应该修复 M 的小值的错误，但对于真正大尺寸的地图，您仍然需要下一件事。

您没有考虑 mod (%) 操作在 Java 中的工作方式。特别是对于 a 的负值，a % b 的值也是负的。因此，当您插入大量值并检查下一个索引时，i + h^2 可能会溢出 Integer.MAX_VALUE 并变为负数。要解决此问题，您可以使用如下方法：

static int safeMod(int a, int b) {
     int m = a % b;
     return (m >= 0) ? m : (m+b);
}

为什么在不覆盖碰撞值时二次探测的实现会失败？

Why does this implementation of Quadratic Probing fail when not overriding values on collision?

java

hash

quadratic-probing