12

编辑： 这个问题与位运算符无关，不能用为什么在 java hashCode() 中经常使用 XOR 而很少使用另一个位运算符来回答？

我已经看到了对象哈希计算的不同方法：

class A {
  public B b;
  public C c;

  @Override
  public boolean equals();
  @Override
  public int hashCode() {
   return c.hashCode() ^ b.hashCode(); //XOR
   return c.hashCode() + prime * b.hashCode(); // SUM
   return Objects.hash(b,c); // LIB
  }
}

LIB方法似乎使用SUM，但为什么它比XOR更好？

尽管这个例子是用 Java 编写的，但这个问题更多的是关于数学和概率。

4

3 回答 3

5

SUM 确保您使用哈希码的所有位来传播您的哈希（在此，一个 int 的 32 位），并且不为此假设 sub hashcode() 实现。

异或只有在 B 和 C 的 hashcode 有的情况下才具有相同的性质，否则只会使用 B 和 C 的 hashcode 中“有用”位数中的最小值，这可能导致更差的分布，更频繁的冲突. 如果 B 和 C 是往往很小的整数，则很容易看出问题，您只会使用前几位（因为 int.hashcode() 是标识函数）。

于 2013-06-25T12:24:08.370 回答
0

这是因为sum提供比 提供更好的分布xor。

例如，如果int a和b的值介于 0 和 7 之间（000和111二进制），那么xor这两个参数的结果将始终介于 0 和 7 之间（因为xor只会更改 3 位）。现在，当您进行乘法和 a 时，sum您将获得更好的分布，因为值不会在 0 和 7 范围内。

于 2013-06-25T12:19:44.063 回答
-1

答案是（一如既往）：“这取决于。 ”这取决于你的班级。

例如，如果您考虑

class X {
    T a, b;
    X(T _a, _b) { a = _a; b = _b }
}

您不会使用对称运算符，例如+,*或^（想象T是int，并且您正在散列X(1,2)和X(2,1)。显然散列码应该不同。所以三个“解决方案”中的第一个（异或散列值）会很糟糕）。

如果T是复杂类型，第三种解决方案 ( Objects.hash()) 也可能不好，因为只考虑引用（相同的对象可能返回不同的哈希码）。

于 2018-05-28T08:09:09.670 回答