Java重写equals()和hashcode()方法，使得两个可互换的整数能够比较相等。

Question

我正在覆盖简单容器对象的equals和hashcode方法，用于两个整数。每个整数反映另一个对象的索引（该对象是什么并不重要）。该类的目的是表示两个对象之间的连接。

连接的方向无关紧要，因此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方法时会产生不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同的整数结果可能会提高哈希表的性能。

如果有人知道减少匹配哈希码数量的简单方法，我将感激不尽。

谢谢！

Tim

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

- Twice Circled

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较小，则仍然可能出现不理想的冲突率。

如果需要对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 - 我不知道这是否是正确的技术术语...}

- Stephen C

---

你的第四点有一个小问题，就是一些哈希表可能会将哈希码映射到插槽中，以使你分离值的工作失效。我建议计算 bigprime1*(from+to)-bigprime2*min(from,to)。无需计算最大值和最小值，因为 sum-max=min。在哈希中，XOR似乎很受欢迎，但在具有定义溢出语义的语言中，我不知道它是否比加法具有任何有意义的优势。 - supercat

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;
}

- Nikolay Kuznetsov

---

这种情况下这样做是行不通的，因为起始点和终点不一定相等。相反，也许应该先对它们进行排序。 - ddmps

我刚在Excel中尝试了一下。Pescis是正确的，如果你交换数字，它不会给出相同的结果（除非它们相同）。 - Twice Circled

@TwiceCircled，你在问题中指定了那个要求吗？ - Nikolay Kuznetsov

如果您先确定较小的数字，然后将其用于第一行，另一个数字用于第二行呢？ - drone.ah

@Nikolay - 是的，我这样认为，请看第二段。 - Twice Circled

Answer 3

我认为，类似以下这样的东西

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

足够好

- infthi

---

在从1到1000的范围内，对于每个from和其中的两个数，我得到了330159次碰撞。而接受的答案有497477次碰撞。 - infthi

我的解决方案＃4应该在那个范围内产生零碰撞 :-) - Stephen C

Answer 4

通常我使用XOR来进行哈希码方法。

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

- Jayamohan

---

根据数字的大小，特别是to的大小，这不会很快导致溢出吗？ - drone.ah

@drone.ah - 1）不行。2）即使它是，也无关紧要...这只是一个哈希码，而不是有意义的计算。（'^'运算符是异或运算！！） - Stephen C

@StephenC 说得好。然而，仍然存在一个问题，即从^到≠到^从，这是一个要求。 - drone.ah

@drone.ah - 我认为你可能需要检查一下那个“事实”。按位异或是一种对称操作... - Stephen C

所有 from == to 的对象将使用此解决方案生成 hashCode 0，这可能不是期望的结果。 - StuPointerException

@StephenC 我的错。我误解了 ^。 - drone.ah

Answer 5

Java 1.7+有Objects.hash

@Override
public int hashCode() {
    return Objects.hash(from, to);
}

- answer42

Answer 6

我不明白为什么没有人提供通常最好的解决方案：规范化您的数据。

 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的乘数，您可以避免像this question中那样的冲突。
• 通过使用大的乘数，您可以更好地分散数字。

• 通过使用奇数乘数，您可以确保乘法是双射的（即，没有信息丢失）。

• 通过使用质数，您不会获得任何优势，但每个人都这样做，也没有任何劣势。

- maaartinus

---

值得注意的是，对于所有形如(x, x)的一对，您第二个指定的结构在x方面是双射的，并且对于形如(x,x+delta)的一对几乎是双射的。相比之下，将一个值乘以31并加上另一个值的形式，在使用两个相等的值时总会产生32的倍数，使用四个值时为64，使用八个值时为128，使用16个值时为256等。 - supercat

@supercat 27644437 * x + x = 0x1A5D216 * x 这个式子总是偶数，所以它不能是双射的。但是它已经足够好了，因为它不是4的倍数。我一直认为31是一个可怕的乘数，但我没有考虑到 hash(x, x) 是32的倍数。 - maaartinus

最终结果是27644437 *（x + x）+ x，这很奇怪。至于31的优点，如果每个步骤计算31 * prev-x而不是31 * prev + x，那么情况就不会那么糟糕。当然，这将使每个（x，-x）值哈希到32的倍数，但这些可能比（x，x）少得多。真正可怕的是x ^ y。这将每个（x，x）映射为零，并且对于（x，x + 1）几乎与之相同，将其中一半映射为1，四分之一映射为3，八分之一映射为7等等。荒谬的是，x + y通常不比x ^ y更昂贵，但人们对异或有一些奇怪的依恋。顺便说一下，“from + to”可能是一个不错的哈希。 - supercat

我不会说BitSet#hashCode是无害的，因为没有人需要它，但似乎很难导致严重退化的行为。一个百万项的哈希表，其中每个单独的项都与另一个项碰撞，应该被认为是良好哈希的，即使它具有“100％的碰撞率”。其中三分之一的项产生相同的哈希值的哈希表将是劣质的，即使所有其他项都具有不同的哈希值（因此与第一个表中的500,000个不同值相比，它实际上只有666,667个不同值）。 - supercat

我会怀疑在典型的使用情况下，像 BitSet@hashCode 这样的东西会比稍微调整过的算法有更多的碰撞，但我不会期望碰撞会形成大的集群，就像异或在许多实际情况下可能会做的那样，也不会产生完全退化的行为，就像将每个项目映射到相等项目的表所发生的那样。 - supercat