代码之家 › 专栏 › 技术社区 › Wes

还原哈希代码“sum”

integer-overflow integer math java

Wes · 技术社区 · 7 年前

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

2 回复 | 直到 7 年前

luk2302 7 年前

第一:无法正确反转导致整数溢出的操作。基本上,问题是您无法知道整数溢出在前一个操作中是否发生过一次、两次甚至更频繁。因此您无法获得原件 value 在最后一次哈希计算之前存在。

第二:散列计算取决于应用的散列值的顺序。

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

由于追加最后一个值的散列值更改取决于所有以前的散列值,因此您不能只更改一个中间散列值,因此没有(性能良好)的方法来消除 1 在我之前的例子中,对所有未来的计算都有影响。

如果您使用 , 2 , 3 等,而不是 1000 首先。如果没有整数溢出,只有按照与添加哈希值相反的顺序删除哈希值,循环才会起作用。这是一个在“现实生活”中没有意义的限制。@JB Nizet写了什么 his comment 在我看来是正确的。

Henry 7 年前

基本上,当用整数进行计算时,需要进行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时的值不同。这是无法用此哈希函数解决的。