Java为两个可互换的整数重写equals()和hashcode()

Question

我重写了两个int的简单容器对象的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 here.

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 ^max(i,j).这很可能会给你的哈希表中的"分散" ¹带来较差......以及更高的冲突率.(还有一个问题from == to!)

第二个和第三个比第一个好,但是如果from并且to很小的话,你仍然可能会遇到比所希望的更多的碰撞.

如果它是你最小化的较小值碰撞的关键,我建议第4的替代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 - 我不知道这是否是正确的技术术语...}

Answer 2

这是被广泛接受的方法：

@Override
public int hashCode() {
    int res = 17;
    res = res * 31 + Math.min(from, to);
    res = res * 31 + Math.max(from, to);
    return res;
}