还原哈希码 "sum"

Question

所以，与其每次都计算散列码，我想我可以让一个整数随着所有的变化而更新。想象一下 setter 对属性的贡献哈希码：

public void setFoo(Foo newFoo){
    this.hashCalculator.remove(this.foo.hashCode()); // remove old hash code
    this.hashCalculator.add(newFoo.hashCode()); // add new hash code
    this.foo = newFoo; // set new foo
}

（我希望我没有做傻事）我认为这将是简单的数学运算，但我未能实现它。我认为这与整数溢出有关，但我不确定。显然我错过了一些东西。除法余数应该加回值吧？

这是我的代码。最后结果应该是 1，但这不是我得到的。

class HashCode
{
    public int value = 1;

    public void add(int val){
        // as suggested by effective java
        value = value * 37 + val;
    }

    public void remove(int val){
        value = (value - val) / 37;
    }
}

HashCode o = new HashCode();

for(int a = 0; a < 1000; a++){
    o.add(a);
}

for(int r = 0; r < 1000; r++){
    o.remove(r);
}

System.out.println(o.value); // should be 1

Answer 1

首先：没有办法正确地反转导致整数溢出的操作。基本上，问题是您无法知道在之前的操作中整数溢出是否发生过一次、两次甚至更多。因此，您无法在最后一次哈希计算之前获得原始的 value。

其次：哈希计算取决于应用哈希值的顺序。

((1 * 37 + 0) * 37 + 1) * 37 + 2 = 50692
((1 * 37 + 2) * 37 + 1) * 37 + 0 = 53428
           ^         ^         ^ the hash values.

由于附加最后一个值的散列值变化取决于所有先前的散列值，您不能只更改一个中间散列值，因此没有（表现良好的）方法来消除我的 1 的影响前面的例子对所有未来的计算都有影响。

如果您使用 1、2、3 等而不是 1000 来测试循环，这应该是显而易见的。如果没有整数溢出，您的循环只有在您以与添加它们相反的顺序删除哈希值时才会起作用。这是在 "real-life" 中应用没有意义的限制。 @JB Nizet 在中写的内容在我看来是正确的。

Answer 2

基本上，当用整数计算时，你做算术模 2^32。因此，在溢出的情况下，如果不是除以 37，而是乘以它的模逆 -1857283155，它就会起作用。例如，这给出了结果 1:

    int pInv = -1857283155;
    int v = 1;

    for (int a = 0; a < 1000; a++) {
        v = v * 37 + a;
    }

    for (int r = 999; r >= 0; r--) {
        v = (v - r) * pInv;
    }

    System.out.println(v);

第二个问题是先加a后b时的哈希值与先加b后a时的值不一样。这个哈希函数无法解决这个问题。

还原哈希码 "sum"

Reverting an hash code "sum"

java

math

integer

integer-overflow