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

Question

发生冲突时，我当前的二次探测实现会用新项目覆盖存储在当前索引中的项目。我插入了三个 Person 对象，这些对象使用它们的姓氏作为键来存储。为了测试实现的冲突解决方案，它们都具有相同的姓氏，即"风车"。

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

列表大小已设置为 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。您需要将i = (i + h * h++) % M替换为一些基于模运算属性 （https://en.wikipedia.org/wiki/Modulo_operation） 的其他运算：

（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

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

1. 您不检查（多）地图是否已满。在实践中，您需要执行 2 项检查：

   • 检查是否N==M（或者一些较小的阈值，如 90% 的M）
   • 使collisionCount成为局部变量以及何时达到N（不幸的是，为了避免某些病理情况，此检查也是必要的）

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

2. 你没有考虑到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);
}