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

还原哈希代码“sum”

  •  3
  • 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 年前
        1
  •  4
  •   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 在我看来是正确的。

        2
  •  3
  •   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时的值不同。这是无法用此哈希函数解决的。