Why does AutoValue use 1000003 as its prime for hashCode?

[mjustin]

There is a Stack Overflow question asking why AutoValue uses 1000003 as its prime, rather than some other number. The code base, including the initial commit, doesn't appear to give any hints. Java's built-in Object.hash, Arrays.hashCode, and List.hashCode by contrast all use the much smaller number 31 for their hash function.

@Override
public int hashCode() {
  int h = 1;
  h *= 1000003;
  h ^= this.firstName.hashCode();
  h *= 1000003;
  h ^= this.lastName.hashCode();
  h *= 1000003;
  h ^= this.age;
  return h;
}

Is there any particular reason — mathematical or otherwise — that this particular value was chosen for AutoValue? 1000003 is the first prime after one million, so one might guess is that's why it was chosen. Is there some value to using a larger prime like this, over a smaller one like 31?

[eamonnmcmanus]

Possibly @kevinb9n can comment in more detail. I found an internal commit (for Googlers: cl/40155455) where Kevin wrote "use a hash calculation that was found by [another person] to perform far better than *31+". (The other person doesn't work for Google anymore and I don't see them on GitHub.) It sort of makes intuitive sense because if the numbers being contributed to the hash-code are small, 31 will only shift them left 5 bits, while 1000003 will shift them left 20 bits. So for example, if I'm calculating correctly, hashing the numbers 1,2,3 with a multiplier of 31 would produce 28771, while with a multiplier of 1000003 it produces 1303276239.

[kevinb9n]

Although I don't remember the details.... it is kind of exactly like me to shift things over a golden-ratio fraction of the way. Though that might argue for a multiplier of 898,459, so I guess I also thought it should be a nice simple number to the human eye.

But yeah, the idea of making it bigger was just to eat up all those initial zeros more quickly and get the bits to come back around and interfere with each other.

[kevinb9n]

Also: (using Integers for simplicity) with List.of(a, b) and List.of(c, d) you get a collision if b - d happens to be 31 times c - a. And it's just a little easier to imagine real-world circumstances where that might happen to be true than it is with a much larger multiplier. No exact science here, though. Object.hashCode is never exactly going to be a high-quality hash function in any case.

[mjustin]

Thanks, @kevinb9n & @eamonnmcmanus for the super quick answers and internal insight on this.

[kevinb9n]

sure thing! If my whole job was to answer "why" questions it would be the funnest job in the world.