Why Does Java Use 31 as the Multiplier in String's hashCode()?

Delving into the Reasoning behind Java's 31 Multiplier for String's hashCode()

Java's String implementation employs a specific formula to calculate the hash code:

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

where s[i] denotes the i-th character of the string, n represents its length, and ^ signifies exponentiation. However, a pertinent query arises: why is the multiplier set at 31?

This choice stems from the principles outlined in Joshua Bloch's renowned book, "Effective Java, Second Edition." Bloch's rationale centers around two key criteria for the multiplier: it should be a relatively large prime number.

The Benefits of an Odd Prime Multiplier

Bloch highlights that using an odd prime multiplier like 31 ensures that the multiplication operation won't result in information loss due to overflow. If the multiplier were even, overflow might occur, and since multiplication by 2 is analogous to shifting, crucial information could be compromised.

The Subtler Perks of a Prime Multiplier

While the specific advantages of selecting a prime multiplier are less apparent, it aligns with customary practices. Notably, 31 possesses a unique attribute: it allows the multiplication to be efficiently replaced with a shift and a subtraction, leading to improved performance. This optimization is often executed automatically by modern virtual machines (VMs).

The Consensus

In summary, Java's use of 31 as the multiplier for String's hashCode() method stems from its status as an odd prime number. This choice safeguards against information loss due to overflow and enables performance enhancements through the replacement of multiplication with shifting and subtraction.

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