Java 为两个可互换的整数覆盖 equals() 和 hashcode()

Question

我正在覆盖两个整数的简单容器对象的 equals 和 hashcode 方法。每个 int 都反射(reflect)了另一个对象的索引(该对象是什么并不重要)。类的要点是表示两个对象之间的连接。

连接的方向无关紧要，因此 equals 方法应该返回 true，而不管两个 int 在对象中的方向如何，例如

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() , 指出

It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hashtables.

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

谢谢!

蒂姆

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

Answer 1

已经提出了三种“有效”的解决方案。 (通过工作，我的意思是它们满足哈希码的基本要求......不同的输入给出不同的输出......并且它们还满足 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ⁱ 和 2^j 的非负数，则输出将小于或等于 2 ^{最大(i，j)}。这可能会使您的哈希表中的“分散”¹ 很差……并且冲突率更高。 (from == to时也有问题!)

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

---

如果对 from 和 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¹⁶-1 范围内，你会得到一个唯一的每个不同(无序)对的哈希码。

---

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