1

当发生碰撞时，我当前的二次探测实现会用新项目覆盖当前索引中存储的项目。我插入三个 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 溢出并变成负数，导致程序崩溃。

4

2 回答 2

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。
于 2019-01-17T19:00:42.170 回答
0

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

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

    • 检查是否N==M（或者可能是一些较小的阈值，例如 90% M）
    • 做collisionCount一个局部变量，当它到达时N（不幸的是，这个检查也是必要的，以避免一些病理情况）

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

  1. 您没有考虑到 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);
}
于 2019-01-18T01:25:52.140 回答