10

我正在为两个整数的简单容器对象覆盖 equals 和 hashcode 方法。每个 int 都反映了另一个对象的索引（无论该对象是什么）。类的重点是表示两个对象之间的连接。

连接的方向无关紧要，因此无论两个整数在对象中的哪个方向，equals 方法都应该返回 true。

connectionA = new Connection(1,2);
connectionB = new Connection(1,3);
connectionC = new Connection(2,1);

connectionA.equals(connectionB); // returns false
connectionA.equals(connectionC); // returns true

这是我所拥有的（从 Integer 的源代码修改）：

public class Connection {
    // Simple container for two numbers which are connected.
    // Two Connection objects are equal regardless of the order of from and to.

    int from;
    int to;

    public Connection(int from, int to) {
        this.from = from;
        this.to = to;
    }

    // Modifed from Integer source code
    @Override
    public boolean equals(Object obj) {
        if (obj instanceof Connection) {
            Connection connectionObj = (Connection) obj;
            return ((from == connectionObj.from && to == connectionObj.to) || (from == connectionObj.to && to == connectionObj.from));
        }
        return false;
    }

    @Override
    public int hashCode() {
        return from*to;
    }
}

这确实有效，但我的问题是：有没有更好的方法来实现这一目标？

我主要担心的是 hashcode() 方法将为任何两个乘以等于相同数字的整数返回相同的哈希码。例如

3*4 = 12
2*6 = 12 // same!

文档http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Object.html#hashCode()指出

如果根据 equals(java.lang.Object) 方法，如果两个对象不相等，则不需要对两个对象中的每一个调用 hashCode 方法都必须产生不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同的整数结果可能会提高哈希表的性能。

如果有人能看到一种减少匹配哈希码数量的简单方法，那么我将不胜感激。

谢谢！

蒂姆

PS 我知道有一个 java.sql.Connection 可能会导致一些导入烦恼。该对象实际上在我的应用程序中具有更具体的名称，但为简洁起见，我在此处将其缩短为 Connection。

4

5 回答 5

6

已经提出了三种“有效”的解决方案。（通过工作，我的意思是它们满足哈希码的基本要求......不同的输入给出不同的输出......并且它们还满足 OP 的额外“对称”要求。）

这些都是：

   # 1
   return from ^ to;

   # 2
   return to*to+from*from;

   # 3
   int res = 17;
   res = res * 31 + Math.min(from, to);
   res = res * 31 + Math.max(from, to);
   return res;

第一个问题是输出范围受实际输入值范围的限制。因此，例如，如果我们假设输入都是分别小于或等于 2 i和 2 j的非负数，那么输出将小于或等于 2 max(i,j)。这可能会在您的哈希表中给您带来较差的“分散” 1 ......以及更高的冲突率。（也有问题from == to！）

第二个和第三个比第一个好，但是如果from和to很小，您仍然可能会遇到比预期更多的碰撞。

from如果对于和的小值最小化冲突至关重要，我会建议第 4 种选择to。

  #4
  int res = Math.max(from, to);
  res = (res << 16) | (res >>> 16);  // exchange top and bottom 16 bits.
  res = res ^ Math.min(from, to);
  return res;

这样做的好处是，如果from和to都在 0..2 16 -1 范围内，您将获得每个不同（无序）对的唯一哈希码。

1 - 我不知道这是否是正确的技术术语...

于 2013-04-08T12:13:21.233 回答
5

这是被广泛接受的方法：

@Override
public int hashCode() {
    int res = 17;
    res = res * 31 + Math.min(from, to);
    res = res * 31 + Math.max(from, to);
    return res;
}
于 2013-04-08T11:32:38.920 回答
2

我想，像

@Override
public int hashCode() {
    return to*to+from*from;
}

足够好

于 2013-04-08T11:38:40.523 回答
1

通常我使用 XOR 作为哈希码方法。

@Override
public int hashCode() {
    return from ^ to;
}
于 2013-04-08T11:40:44.910 回答
0

我想知道为什么没有人提供通常最好的解决方案：规范化您的数据：

 Connection(int from, int to) {
      this.from = Math.min(from, to);
      this.to = Math.max(from, to);
 }

如果这是不可能的，那么我会建议类似

 27644437 * (from+to) + Math.min(from, to)
  • 通过使用不同于 31 的乘数，您可以避免像这个问题中那样的碰撞。
  • 通过使用大乘数，您可以更好地分散数字。

  • 通过使用奇数乘法器，您可以确保乘法是双射的（即，不会丢失任何信息）。

  • 通过使用素数，您将一无所获，但每个人都这样做并且没有劣势。

于 2014-06-15T14:32:18.030 回答