Java overriding equals() and hashcode() for two interchangeable integers

Question

I'm overriding the equals and hashcode methods for a simple container object for two ints. Each int reflects the index of another object (it doesn't matter what that object is). The point of the class is to represent a connection between the two objects.

The direction of the connection doesn't matter, therefore the equals method should return true regardless of which way round the two ints are in the object E.g.

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

Here is what I have (modified from the source code for 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;
    }
}

This does work however my question is: Is there a better way to achieve this?

My main worry is with the hashcode() method will return the same hashcode for any two integers which multiply to equal the same number. E.g.

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

The documentation, http://docs.oracle.com/javase/1.5.0/docs/api/java/lang/Object.html#hashCode(), states that

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.

If anyone can see a simple way of reducing the number of matching hashcodes then I would be appreciative of an answer.

Thanks!

Tim

PS I'm aware that there is a java.sql.Connection which could cause some import annoyances. The object actually has a more specific name in my application but for brevity I shortened it to Connection here.

Answer 1

This is widely accepted approach:

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

Answer 2

Three solutions that would "work" have been proposed. (By work, I mean that they satisfy the basic requirement of a hashcode ... that different inputs give different outputs ... and they also satisfy the OP's additional "symmetry" requirement.)

These are:

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

The first one has the problem that the range of the output is bounded by the range of the actual input values. So for instance if we assume that the inputs are both non-negative numbers less or equal to 2ⁱ and 2^j respectively, then the output will be less or equal to 2^max(i,j). That is likely to give you poor "dispersion"¹ in your hash table ... and a higher rate of collisions. (There is also a problem when from == to!)

The second and third ones are better than the first, but you are still liable to get more collisions than is desirable if from and to are small.

---

I would suggest a 4th alternative if it is critical that you minimize collisions for small values of from and 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;

This has the advantage that if from and to are both in the range 0..2¹⁶-1, you get a unique hashcode for each distinct (unordered) pair.

---

^{1 - I don't know if this is the correct technical term for this ...}

Answer 3

i think, something like

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

is good enough

Answer 4

Typically I use XOR for hashcode method.

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

Answer 5

I wonder why nobody offered the usually best solution: Normalize your data:

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

If it's impossible, then I'd suggest something like

 27644437 * (from+to) + Math.min(from, to)

• By a using a multiplier different from 31, you avoid collisions like in this question.
• By using a big multiplier you spread the numbers better.

• By using an odd multiplier you ensure that the multiplication is bijective (i.e., no information gets lost).

• By using a prime you gain nothing at all, but everyone does it and it has no disadvantage.