Why Does Java's `hashCode()` for Strings Use 31 as a Multiplier?

Why is 31 Used as a Multiplier in Java's hashCode() Method for Strings?

The Java documentation specifies the calculation of a String object's hash code as follows:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

where s[i] is the ith character of the string, n is the string's length, and ^ represents exponentiation. This formula incorporates a fixed multiplier of 31.

Rationale for Using 31 as a Multiplier

According to Joshua Bloch's esteemed work, "Effective Java," the choice of 31 as the multiplier rests on several factors:

• Odd Prime: Being an odd prime, 31 ensures that if multiplication results in overflow, information is not lost (unlike using an even multiplier, which is equivalent to shifting).
• Tradition: Using a prime as the multiplier is customary.
• Performance Optimization: 31 has a unique property that enables performance improvements: 31 * i can be efficiently replaced by (i << 5) - i. This optimization is commonly applied by modern virtual machines.

The above is the detailed content of Why Does Java's `hashCode()` for Strings Use 31 as a Multiplier?. For more information, please follow other related articles on the PHP Chinese website!