java – Why is the number 31 most often used when overriding hashCode?

Question:

Why is the number 31 most often used when overriding hashCode? I heard somewhere that this number was chosen from a mathematical point of view, since it provides an even distribution of the hashCode function, which ensures the minimum probability of collisions.

Answer:

Effective Java by Joshua Bloch states that:

31 was chosen because it is an odd prime.

If the question is why exactly 31, then it is because the multiplication operation can be replaced with shift and subtraction to improve performance: 31 * i == (i << 5) - i . Modern virtual machines do this kind of optimization automatically.

You can also read this :

Of the remaining four, I will probably choose P (31), since it is cheaper to compute it on RISC architectures (because 31 is the difference of two powers of two). P (33) is just as cheap to compute, but its performance is marginally worse, and 33 is composite, which makes me nervous.

Scroll to Top