Why does this particular hashCode function help decrease collisions?

Question

I just read in Effective Java about the hashCode method:

1. Store some constant nonzero value, say, 17, in an int variable called result.

2. For each significant field f in your object (each field taken into account by the equals method, that is), do the following:

   a. Compute an int hash code c for the field.

   b. Combine the hash code c computed in step 2.a into result as follows: result = 31 * result + c;

A nonzero initial value is used in step 1 so the hash value will be affected by initial fields whose hash value, as computed in step 2.a, is zero.

If zero were used as the initial value in step 1, the overall hash value would be unaffected by any such initial fields, which could increase collisions. The value 17 is arbitrary. The multiplication in step 2.b makes the result depend on the order of the fields, yielding a much better hash function if the class has multiple similar fields.

And that's their implementation of hashCode:

@Override public int hashCode() {
    result = 17;
    result = 31 * result + areaCode;
    result = 31 * result + prefix;
    result = 31 * result + lineNumber;
    hashCode = result;
    return result;
}

My questions are below:

1. How does the initial value 17 help us decrease collisions?
2. How does multiplying by 31 help us decrease collisions?
3. Why do we use 17 and 31? I know they are prime numbers. Is that why we use them?

I tried to come up with an example of a collision using a class with two and three integer fields, but didn't succeed. I'd glad, if you gave me a simple example of a collision.

Answer 1

If the hashed codes are $x_1,\ldots,x_n$ (in that order), then the resulting hash value is $$ x_n + 31 x_{n-1} + 31^2 x_{n-2} + \cdots + 31^{n-1} x_1 + 31^n \cdot 17 \pmod{2^{32}}, $$ assuming int is 32 bits, and ignoring signed/unsigned distinctions. In view of this, the integers 17 and 31 should satisfy the following two properties:

1. 17 should be non-zero. This way, the hash depends on the input length. Otherwise it is completely arbitrary.

2. 31 should be relatively prime to $2^{32}$ (i.e., odd) and have a high order modulo $2^{32}$ (that is, the minimal $m$ such that $31^m \equiv 1 \pmod{2^{32}}$); this way the multiplicands $31,31^2,\ldots$ are all different for the longest time possible. It turns out that the order of $31$ modulo $2^{32}$ is only $2^{27}$, so 31 is not an optimal choice. Its being prime makes no difference – we only care about its oddness and order.

In any case, this hash can be improved on – for example, the python hash function uses XOR instead of addition, thus making the resulting calculation non-algebraic.

Answer 2

In abstract terms, we are looking at a mapping from triples of numbers to integers. If you unfold what they do there, you get

$\qquad\displaystyle f(a,b,c) = 17 \cdot 31^3 + a \cdot 31^2 + b \cdot 31 + c$.

The idea is to encode everything into one number in a surjective way, that is no two triples map to the same number. Since this is impossible in practice because the domains have different sizes, you want to even out values as much as possible.

I don't understand their reasoning about the initial value; shifting all hash values by a constant does not seem to solve any problem I can see. Multiplying the encoded numbers with different powers of a prime makes sure they don't "overlap".

In my opinion, a more reasonable variant would be the rather standard

$\qquad\displaystyle f(a,b,c) = 2^a + 3^b + 5^c \qquad(\!\mod m)$;

here, we use that every number has a unique prime factorisation. Of course, this creates huge numbers (using modulo arithmetic, it's still feasible to compute the values); Cantor's scheme would be the next go-to scheme.