On integer multiplication, overflow, and information loss

Question

I'm reading through Chapter 3 of Joshua Bloch's Effective Java. In Item 8: Always override hashCode when you override equals, the author uses the following combining step in his hashing function:

result = 37 * result + c;

He then explains why 37 was chosen (emphasis added):

The multiplier 37 was chosen because it is an odd prime. If it was even and the multiplication overflowed, information would be lost because multiplication by two is equivalent to shifting. The advantages of using a prime number are less clear, but it is traditional to use primes for this purpose.

My question is why does it matter that the combining factor (37) is odd? Wouldn't multiplication overflow result in a loss of information regardless of whether the factor was odd or even?

Answer 1

Consider what happens when a positive value is repeatedly multiplied by two in a base-2 representation -- all the set bits eventually march off the end, leaving you with zero.

An even multiplier would result in hash codes with less diversity.

Odd numbers, on the other hand, may result in overflow, but without loss of diversity.

Answer 2

The purpose of a hashCode is to have random bits based on the input (especially the lower bits as these are often used more)

When you multiple by 2 the lowest bit can only be 0, which lacks randomness. If you multiple by an odd number the lowest bit can be odd or even.

---

A similar question is what do you get here

public static void main(String... args) {
    System.out.println(factorial(66));
}

public static long factorial(int n) {
    long product = 1;
    for (; n > 1; n--)
        product *= n;
    return product;
}

prints

0

Every second number is an even and every forth a multiple of 4 etc.