Had fun today with what looked like perfectly good Java hashCodes, generated by Eclipse. These typically take this form…

public int hashCode() {
  final int prime = 31;
  int result = 1;
  result = prime * result + _field1.hashCode();
  result = prime * result + _field2.hashCode();
  return result;
}

This is a decent hashcode and fast to compute. The issue we encountered was when placing these objects in Sets, for example we have two Sets of two Tuple objects like so:

final Set<Tuple> set1 = ImmutableSet.of(new Tuple(1, 1), new Tuple(2, 2));
final Set<Tuple> set2 = ImmutableSet.of(new Tuple(1, 2), new Tuple(2, 1));

The thing about the hashCode of a Set is that (for obvious reasons) it is order independent. For ImmutableSet if just sums up the hashCodes of all the elements in the Set. The hashCodes we have for the sets above are…

  • Tuple(1, 1): (31 + 1) * 31 + 1 = 993
  • Tuple(2, 2): (31 + 2) * 31 + 2 = 1025
  • Tuple(1, 2): (31 + 1) * 31 + 2 = 994
  • Tuple(2, 1): (31 + 2) * 31 + 1 = 1024

Whoops, we now get the same hashCode for both Sets! Now, we might cross our fingers and hope that real data won’t follow this pattern. On the other hand it is exactly what you might expect from artificially generated test data. And indeed this is what we have, a dataset that causes a vastly elevated number of hash collisions, putting the equals implementation under heavy strain.

What we need is an operation that doesn’t commute with +. My esteemed colleague Chris provided an implementation of the Cantor Pairing Function to generate the Tuple hashCode. This did solve the specific performance problem we were facing, but where should we apply the new (slower) implementation of hashCode?

  • Only where we have observed a problem?
  • Everywhere?
  • Try to guess which things are likely to be used in Sets?

Or would it be better to concentrate on improving the realism of the test data? Of course, a client might be expected to generate test data with exactly the same issue, so there is a strong argument for fixing the problem even if we don’t expect “real” data to trigger it.

As usual, it seems there is no silver bullet!